Источник: http://www.algolib.narod.ru/Graph/Path.html
На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве. К сожалению, такие действия не всегда приводят к нужному результату.
Напомним, что алгоритм построения МОД нацелен на поиск дерева с минимальным суммарным весом ребер. Рассмотрим, например, "циклический" граф, то есть такой граф, в котором первая вершина соединена со второй, вторая - с третьей, и так далее, а последняя вершина в свою очередь соединена с первой. Такой граф представляет собой просто кольцо, каждая вершина в котором соединена с двумя другими.
Обратите внимание на то, что вес каждого ребра равен 1 за исключением ребра, соединяющего вершины A и B, вес которого равен 2. Алгоритм построения минимального остовного дерева выберет все ребра веса 1, отбросив единственное ребро веса 2. Это означает, однако, что путь от A к B в минимальном остовном дереве должен проходить через все остальные вершины, а его длина равна 5 (рис. 1 (б)). Ясно, что он не является кратчайшим, поскольку в исходном графе вершины A и B соединены ребром длины 2.
Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра. Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего пути в целом пути из начальной вершины, то мы получим требуемый результат.Точнее говоря, вот измененный алгоритм:
выбрать начальную вершину
создать начальную кайму из вершин, соединенных с начальной
while вершина назначения не достигнута do
выбрать вершину каймы с кратчайшим расстоянием до начальной
добавить эту вершину и ведущее в нее ребро к дереву
изменить кайму путем добавления к ней вершин,
соединенных с вновь добавленной
for всякой вершины каймы do
приписать к ней ребро, соединяющее ее с деревом и
завершающее кратчайший путь к начальной вершине
end for
end while
приведен пример исполнения этого алгоритма. Алгоритм выполняется на том же графе (рис. 2 (а)), что и алгоритм построения минимального остовного дерева, а искать мы будем кратчайший путь от A до G.
В начале пути из вершины A у нас есть четыре возможных ребра. Из этих четырех ребер ребро AB является кратчайшим. Поэтому мы добавляем к дереву вершину B (рис. 2 (в)) и смотрим, как следует обновить набор путей. С уже построенным деревом соединены теперь вершины E и G, поэтому их следует добавить к кайме. Кроме того, мы должны посмотреть на вершину D и сравнить прямой путь из нее в A, длина которого равна 7, с окольным путем через вершину B, длина которого равна 8. Прямой путь короче, поэтому приписанное к D ребро менять не следует. Изучив теперь имеющиеся возможности, мы видим, что кратчайшим является путь из A в C длины 4. Ребро BE короче, однако, мы рассматриваем полную длину пути из A, а такой путь, ведущий в E, имеет длину 5. Теперь к дереву кратчайших путей добавим вершину C (рис. 2 (г)). Посмотрев на граф, мы обнаруживаем, что можем пройти в вершину F через вершину C, однако длина этого пути будет равна 10 - больше, чем у прямого пути из A в F, поэтому изменения в наборе путей не производится.
(г) мы можем выбрать теперь либо путь из A в F, либо путь из A в E, проходящий через вершину B: оба они имеют длину 5. Какой из путей будет выбран при исполнении программы, зависит от способа хранения данных в ней. Мы же, встретившись с необходимостью добавить вершину, будем всегда выбирать вершину, метка которой первая в лексикографическом порядке.
В результате получим ситуацию с(д). Добавление к дереву вершины E не меняет остальных связей, поэтому теперь мы можем добавить вершину F и получим картинку с рис. 2 (е). Обратите внимание на то, что, хотя добавление вершины F и привело к изменению ребра, ведущего из D, если бы мы начали с F, все равно на очередном шаге мы должны были бы добавить E.
(е) видно, что путь в вершину D короче пути в вершину G. Поэтому мы добавляем к дереву вершину D и получаем ситуацию, изображенную на рис. 2 (ж). Осталось добавить только вершину G, и в результате мы получаем дерево кратчайшего пути с рис. 2 (з). Длина кратчайшего пути из A в G равна 10.
На примере с мы имеем дело с полным деревом кратчайших путей, поскольку целевая вершина G была добавлена к дереву последней. Если бы мы добрались до нее раньше, алгоритм бы тотчас завершил свою работу. Могут возникнуть ситуации, в которых нас интересуют кратчайшие пути из данной вершины во все остальные. Если, например, мы имеем дело с небольшой компьютерной сетью, скорости передачи данных между узлами которой приблизительно постоянны, то для каждого из компьютеров сети мы можем выбрать кратчайший путь до каждого из остальных компьютеров. Поэтому при необходимости переслать сообщение единственное, что нам потребуется, это воспользоваться заранее рассчитанным наиболее эффективным путем.