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

Question

Учитывая график и узел назначения, как найти все кратчайшие пути от всех других вершин до вершины назначения.

Answer 1

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

* PS: Только одна вещь, которую нужно запомнить. Чтобы это сработало, нужно повернуть ребра ПРЕЖДЕ ЧЕМ применять Dijkstra с пунктом назначения в качестве начальной вершины.

Answer 2

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

Все, что связано с dest, имеет расстояние 1. Любое, связывающееся с любым из этих узлов (которые еще не подсчитаны), имеет расстояние 2.Повторяйте, пока не выйдете из узлов.

Даже если бы он не был двунаправленным, вы все равно могли бы сделать это довольно легко, «подделав» его двунаправленность с помощью одного прохода через узлы для начала.

В любом случае это порядок (V + E), где V - это количество узлов, а E - количество ребер.

Answer 3

Только для того, чтобы завершить наиболее полезный ответ выше.

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

Answer 4

Алгоритм Дейкстры хорош, если у вас есть взвешенные ребра и вы хотите минимизировать общую стоимость весов на пути, но в невзвешенном графике (все ребра имеют одинаковую стоимость), простой поиск в ширину сделает свое дело.