Алгоритмы поиска маршрута в графе

← →
Александр Иванов © (2006-06-15 08:26) [0]

Посоветуйте алгоритм. Задача простая - поиск маршрута в направленном, не взвешенном графе. Однако усложняется размером графа - от миллиона вершин и выше.

← →
Vlad Oshin © (2006-06-15 08:28) [1]

волновой самый простой

← →
Александр Иванов © (2006-06-15 08:52) [2]

Волновой метод требует большого объема памяти, а при большом графе это первый критерий выбора алгоритма.

← →
wicked © (2006-06-15 09:58) [3]

метод Дийкстры, "с потенциалами"....
добавочная память - по integer-у на вершину....
время работы в худшем случае - n^2,
в лучшем - стремится к n....
поскольку граф не взвешенный, то среднее время будет тяготеть к лучшему результату....

хотя, послушаем еще Гуру.... они придут.... :)

← →
Desdechado © (2006-06-15 11:17) [4]

> поиск маршрута
какие требования к маршруту?

← →
Alx2 © (2006-06-15 11:33) [5]

http://algolist.manual.ru/maths/graphs/index.php

← →
TUser © (2006-06-15 11:49) [6]

Какого-такого маршрута? Самого длинного, самого короткого, проходящего через все вершины, из А в Б? Кроме того, важно знать про граф - есть ли в нем циклы? В зависимости от ответов решение будет существоенно различаться.

Почитай тут, правда качество скана не очень.
http://monkey.belozersky.msu.ru/~evgeniy/cormen_algo.rar (3,7М)

← →
Александр Иванов © (2006-06-15 11:55) [7]

TUser © (15.06.06 11:49) [6]

Если сформулировать точно, то кратчайший маршрут с пропускной способностью не ниже заданной.

← →
MBo © (2006-06-15 11:59) [8]

>Александр Иванов © (15.06.06 11:55) [7]
Хм...
Как согласуется "с пропускной способностью " и невзвешенный граф, как сказано в заглавном посте?

← →
Александр Иванов © (2006-06-15 12:08) [9]

MBo © (15.06.06 11:59) [8]

Скорее всего путаю формулировки, но я считал, что поиск во взвешенном предусматривает нахождения оптимального не по длине, а по сумме весовых коэффициентов. Если не так, то прошу прощения :)

← →
MBo © (2006-06-15 12:46) [10]

>Александр Иванов © (15.06.06 12:08) [9]
взвешенный граф имеет некие неодинаковые характеристики ребер - это их вес, в качестве которого, насколько я понимаю, может выступать стоимость проезда, длина ребра, пропускная способность и т.д.

← →
TUser © (2006-06-15 13:05) [11]

Вес каждого ребра равен 1. Пропускная способность маршрута - вес минимального разреза. Таким образом надо найи поток в графе, пропускная способность которого выше порога Min, а длина самого длинного пути в данном потоке - минимальна. Так я понял?

← →
Александр Иванов © (2006-06-15 13:23) [12]

TUser © (15.06.06 13:05) [11]

Да, абсолютно верно.

← →
Александр Иванов © (2006-06-15 13:26) [13]

И совет, который мне нужен заключается в определении алгоритма с минимальными затратами по времени и объему памяти.

1. Находим крайтчайший путь из s в t, добавляем его в поток.
2. Если пропускная способность потока выше порога - exit.
3. Ищем дополняющий путь, который увеличивает длину потока (в штуках ребер) на наименьшую величину, добавляем его в поток.
4. goto 2.

Алгоритм для п. 3
31. Все першины потока стянуть в одну.
32. Применить адгоритм Дейкстры для поиска кратчайшего пути из этой новой вершины в нее саму или в t.
33. return найденный путь.

> 31. Все першины потока стянуть в одну.

Все, кроме s и t.

> с минимальными затратами по времени и объему памяти
это противоречивые требования
выигрывая в одном, теряем в другом

TUser © (15.06.06 14:00) [14]

Спасибо. Но основной интерес представляет как раз алгоритм поиска, т.е. алгоритм Дейкстры и т.д.

http://www.caravan.ru/~alexch/graphs/

> алгоритм Дейкстры и т.д.

Смотри по приведенной ссылке, например.

Алгоритмы поиска маршрута в графе Найти похожие ветки