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

[Guest]

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

 

[European]

Ссылка скрыта от гостей

 

[Guest]

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

 

[Programmer_Hard]

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

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

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



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

 

[Guest]

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

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

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

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

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

 

[European]

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

 

[Guest]

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

Так у меня же ребра не взвешенные.И все равны,а тут какой то косяк есть

 

[grigsoft]

Ну так назначьте им всем равные веса (1). Алгоритму все равно, они равные или нет.
PS. Кстати, если назначить веса в -1, то, наверное, и алгоритм не надо будет менять