Самый длинный путь в графе

vladpo07

Кто-нибудь знает эффективный алгоритм для нахождения самого длинного пути в ориентированном ациклическом графе?

kiritsev

A0:=<множество вершин без входящих рёбер>
A1:=<множество вершин в которые есть ребро из вершины из A0>
...
первое что в голову пришло...

teraskin

Если делать так - то будет кратчайший путь, точнее минимальное количество шагов, за которое можно заведомо дойти из любой вершины до любой достижимой из нее. Хотя, может быть, ты не ясно выразился.
Правильно это выглядит так:
A0=<множестов вершин без входящих ребер>
A1=<множество вершин, все входящие ребра которых идут из мн-ва A0>
A2=<множество вершин, все входящие ребра который идут мн-в A0 и A1>
....
An=<множество вершин, все входящие ребра который идут мн-в A0 и A1 ... An-1>
Реализация примерно такая:

1) Для каждой вершины считаем, сколько ребер в нее входит.
2) В рабочий список заносим те вершины, в которых нет ребер и ставим длину пути 0
3) Теперь извлекая по одной вершине (Пусть это будет вершина A) из рабочего списка делаем следующее:
Для каждого ребра, которое ведет из нее (пусть ребро ведет в вершину B)
a) уменьшаем количество входящих ребер в B
б) если количество входящих ребер >0, переходим к следующему ребру шага 3
в) устанавливаем для вершины B расстояние на 1 больше, чем расстояние для A
г) отмечаем, что в B пришли из A
д) добавляем вершину B в конец рабочего списка
4) После того, как список кончится - для последней рассмотреной вершины будет записана длина
максимального пути в графе, а также по отмеченным вершинам можно будет построить и сам путь
Сложность алгоритма O(V+E где V и E - количество вершин и ребер соответственно
Оставить комментарий
Имя или ник:
Комментарий: