Кратчайший путь от одного источника до одного назначения в графе

В моем графе отсутствуют такие ребра, которые соединяют вершину с самим собой. Между двумя вершинами существует только одно ребро. От Wikipedia я узнал о некотором алгоритме, который используется для вычисления кратчайшего пути на основе данных условий. Один из самых известных алгоритмов - Dijkstra's algorithm, который находит кратчайшие пути от исходной вершины ко всем другим вершинам графика.
Но, используя Dijkstra's algorithm, мне не нужно исследовать все вершины, однако моя цель - найти самый короткий путь от одного источника до одного места назначения. Какую стратегию я должен использовать здесь? Так что мне не нужно исследовать все остальные вершины.Кратчайший путь от одного источника до одного назначения в графе

Один из моих подходов - использование bidirectional bfs. К bidirectional bfs Я имею в виду применить два bfs один от source node, еще один от destination node. Как только в первый раз, когда я найду то же самое child в обоих деревах, я могу остановить оба bfs. Теперь путь от источника к этому дочернему пути union от моего ребенка до места назначения будет моим самым коротким путем от источника к месту назначения.

Но из всех подходов, описанных в Википедии, и bidirectional bfs, какой из них лучше всего подходит для моего графика?

источник

2012-04-07 Ravi Joshi

родственный: http://stackoverflow.com/questions/2655880/how-to-optimize-dijkstra-algorithm-for-a-single-shortest-path-between-2-nodes –

@KshitijMehta: Должен ли я примените [алгоритм Дейкстры] (http://stackoverflow.com/questions/2655880/how-to-optimize-dijkstra-algorithm-for-a-single-shortest-path-between-2-nodes) здесь? Это лучший способ для моего графика? –

Вы можете работать с поиском A *, но это включает в себя использование эвристических функций и более основан на «искусственном интеллекте». Помимо этого, Dijkstra - ваш лучший вариант. –

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

варианты:

BFS: в общем случае или если вы не заботитесь о времени вычислений, что много.
Dijkstra (Dijkstra) - это «BFS с приоритетной очередью»: если ваши ребра имеют вес/цены (не отрицательные), и вы заботитесь о времени процессора.
A * (A * "- это" Дейкстра с эвристической функцией - например, расстояние на карте города): если вы хотите, чтобы это было очень быстро в среднем случае, но вы должны обеспечить хорошую эвристическую функцию.

Для некоторых проблем с графами возможно использование динамического программирования или других алгоритмических инструментов. Это зависит от ситуации. Дополнительную информацию можно найти в руководствах от http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index ...

источник

2012-04-07 11:29:47 bubersson

От Введение в алгоритмы (КСПС) второе издание, страница 581:

Найти кратчайший путь от u к v для данной вершины u и v. Если мы решаем проблему с одним источником с исходной вершиной u, мы также решаем эту проблему. Более того, не известны алгоритмы для этой проблемы, которые работают асимптотически быстрее, чем лучшие алгоритмы с одним источником в худшем случае.

Таким образом, придерживаться алгоритма Дейкстры :)

источник

2012-04-07 11:14:29

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

источник

2012-04-07 11:16:15 DerMike

Мой график содержит положительные веса –

Я не понял вашу логику. 'Алгоритм Дейкстры 'всегда выбирает тот край, который является самым коротким. –

Wikipedia статья излагает ответ для вас:

Если мы заинтересованы только в кратчайшем пути между источником вершин и целями, мы можем прекратить поиск в строке 13, если и = целевой.

источник

2013-06-24 12:13:05

Кратчайший путь от одного источника до одного назначения в графе

ответ

Смежные вопросы