Запутался насчет кратчайшего пути Дейкстры и MST

Question

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

Answer 1

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

• DijkstraParents (G, s), который возвращает родителя каждой вершины в кратчайшем пути из s в любую другую вершину графаG;
• DijkstraTree (G, s), который может использовать результат DijkstraParents (G, s) для возврата фактического дерева кратчайшего пути;
• DijkstraPath (G, s, t),который может использовать результат DijkstraParents (G, s) или DijkstraTree (G, s), чтобы явно возвращать кратчайший путь от s до t;
• ... и т. д., включая вычисление простых длин путииспользуя вышеупомянутое.

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