Какой есть алгоритм для быстрого поиска пути в графе?

Question

[tmin10]

Подскажите, какие есть алгоритмы быстрого поиска пути от входа до выхода (в графе конечно же нет входов и выходов, нужно найти путь между двумя вершинами)? Все алгоритмы, которые я нашёл, заточены под нахождение оптимального пути, но ни один не заточен на скорость выдачи решения, пусть оно будет не оптимальным.

Comments

[Зелимхан Бельтоев]

Оптимальный == быстрый, или я что-то путаю?

[vaut]

Зелим Бельтоев: имеется ввиду поиск не быстрого пути, а быстрый поиск любого пути.

[tmin10]

Зелим Бельтоев: важно время работы алгоритма, а не стоимость найденного пути

[tmin10]

Денис Карабельщиков: 100 и более вершин в графе

[tmin10]

brainick: обычный ненаправленный граф, вес рёбер значения не имеет, цель: найти путь от одной вершины до другой, потратив на этот поиск наименьшее время.

[tmin10]

brainick: вообще он может быть любым, в данном случае пути может не быть, если он не связный.

[tmin10]

brainick: Я сразу о неём подумал, а также о модификации в виде запуска сразу с двух сторон, но подумал, что может есть что-то более быстрое.

[tmin10]

brainick: да, всё это смотрел, но смущает заточка алгоритмов под поиск минимального пути, а не оптимизация только на скорости. Ведь если алгоритм ищет минимальный путь, то просматривает много подходящих вариантов и отбирает лучший, а мне нужен вообще любой путь, лишь бы быстро.

[Aves]

tmin10: ну по логике вещей, первым найдется минимальный путь

Answer 1

[Mrrl]

Смотрите в сторону A*

Comments

[tmin10]

Он находит решение с наименьшей стоимостью, мне же не нужно это.

Answer 2

[SeptiM]

Если не минимальный, то DFS отработает за O(V + E), в вашем случае за число ребер в компоненте связности. Это время чтения графа. Или вам нужно быстрее?

Answer 3

[GreatRash]

habrahabr.ru/post/162915

Comments

[tmin10]

Насколько я понимаю, он также находит путь с наименьшей стоимостью...

[GreatRash]

tmin10: Тогда посмотрите в сторону алгоритма Флойда.

Answer 4

[Qwk31]

Алгоритм Дейкстры