Не знаю как найти простой путь в графе!

  • Автор темы -
  • Дата начала
Статус
Закрыто для дальнейших ответов.

Гость
#1
Вот!!!!Умираю уже!!!Помогите!!!Граф задан структурой Вирта(немодифцированной).Необходимо найти самый длинный простой путь в графе.Как это сделать!!!!Я умираю уже!!!Помогите!Хотя бы опишите алгоритм ;)
 

Гость
#3
По ссылке ничего нет по простым путям МАКСИМАЛЬНОЙ длины к большому моему огорчению!!!!
 
P

Programmer_Hard

Гость
#4
очень грубое описание:

берем первую вершину i
func(i){
1 закидываем ее в стек ,( если она там уже есть то считай что это петля или цикл - выходи из функции)
2 смотрим куда исходят дуги из этой вершины ( for (j=0;j<nver;j++) )
3 и для кождой из них запускай func(j)
} в стеке запом-ся путь

берем след вершину
...



а вообще ище в гугле
поиск в глубину
поиск в ширину
найдешь кучу примеров : )
 

Гость
#5
Так можно найти простой путь,но не простой путь МАКСИМАЛЬНОЙ длины ;)

очень грубое описание:

берем первую вершину i
func(i){
1 закидываем ее в стек ,( если она там уже есть то считай что это петля или цикл - выходи из функции)
2 смотрим куда исходят дуги из этой вершины ( for (j=0;j<nver;j++) )
3 и для кождой из них запускай func(j)
} в стеке запом-ся путь

берем след вершину
...
а вообще ище в гугле
поиск в глубину
поиск в ширину
найдешь кучу примеров : )
Так можно найти простой путь,но не простой путь МАКСИМАЛЬНОЙ длины
 
04.09.2006
2 566
2
#6
Так а чем алгоритм Дейкстры не устраивает? В шаге 4 по ссылке, которую я давал выше заменить нахождение минимума на нахождение максимума
 

Гость
#7
Так а чем алгоритм Дейкстры не устраивает? В шаге 4 по ссылке, которую я давал выше заменить нахождение минимума на нахождение максимума
Так у меня же ребра не взвешенные.И все равны,а тут какой то косяк есть
 

grigsoft

Well-Known Member
15.11.2005
735
0
#8
Ну так назначьте им всем равные веса (1). Алгоритму все равно, они равные или нет.
PS. Кстати, если назначить веса в -1, то, наверное, и алгоритм не надо будет менять :)
 
Статус
Закрыто для дальнейших ответов.