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

Тема в разделе "Общие вопросы по С и С++", создана пользователем -, 9 апр 2007.

Статус темы:
Закрыта.
  1. Гость

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
  3. Гость

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

    Programmer_Hard Гость

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

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

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



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

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

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

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Так а чем алгоритм Дейкстры не устраивает? В шаге 4 по ссылке, которую я давал выше заменить нахождение минимума на нахождение максимума
     
  7. Гость

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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Ну так назначьте им всем равные веса (1). Алгоритму все равно, они равные или нет.
    PS. Кстати, если назначить веса в -1, то, наверное, и алгоритм не надо будет менять :)
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей