Запутался в кратчайшем пути Дейкстры и MST
Предполагается ли, что алгоритм кратчайшего пути Дейкстры возвращает дерево, как это делается в моем учебнике, посвященном алгоритмам? В примерах, которые я вижу в Интернете, он просто показывает кратчайший путь между двумя вершинами. В моем учебнике он возвращает дерево с ребрами, соединенными с каждой вершиной. Я запутался.
Алгоритм Дейкстры возвращает путь или длину пути, а не дерево. Вершины, которые он исследует, образуют дерево, состоящее из кратчайших путей от источника (не MST), но это дерево никак не возвращается. Может быть, это дерево изображено в вашем учебнике.
Ответы 1
Это зависит от учебника, который вы используете: алгоритм Дейкстры решает проблему кратчайшего пути из одного источника, и сохранение предшественника каждой вершины в кратчайшем пути не требует много дополнительной работы, если вы все равно вычисляете эти пути или их длины. Таким образом, в зависимости от источников и приложений вы можете прочитать что-то вроде:
- DijkstraParents(G, s), который возвращает родителя каждой вершины кратчайшего пути от s до любой другой вершины в графе G;
- DijkstraTree(G, s), который может использовать результат DijkstraParents(G, s) для возврата фактического дерева кратчайших путей;
- DijkstraPath(G, s, t), который может использовать результат DijkstraParents(G, s) или DijkstraTree(G, s) для явного возврата кратчайшего пути из s в t;
- ... и так далее, включая вычисление простых длин пути с использованием вышеизложенного.
В конце концов, все эти версии являются небольшими вариациями основного алгоритма, поэтому используйте ту, которая вам больше подходит.
Можете ли вы дать более подробную информацию, например. пример, который вы видите в Интернете