Результатом алгоритма поиска кратчайшего пути является последовательность ребер, соединяющая заданные две вершины и имеющая наименьшую длину среди всех таких последовательностей.
     На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве. К сожалению, такие действия не всегда приводят к нужному результату.
     Напомним, что алгоритм построения МОД нацелен на поиск дерева с минимальным суммарным весом ребер. Рассмотрим, например, "циклический" граф, то есть такой граф, в котором первая вершина соединена со второй, вторая - с третьей, и так далее, а последняя вершина в свою очередь соединена с первой. Такой граф представляет собой просто кольцо, каждая вершина в котором соединена с двумя другими. Пример такого графа с шестью вершинами приведен на рис. 1 (а).


     Обратите внимание на то, что вес каждого ребра равен 1 за исключением ребра, соединяющего вершины A и B, вес которого равен 2. Алгоритм построения минимального остовного дерева выберет все ребра веса 1, отбросив единственное ребро веса 2. Это означает, однако, что путь от A к B в минимальном остовном дереве должен проходить через все остальные вершины, а его длина равна 5 (рис. 1 (б)). Ясно, что он не является кратчайшим, поскольку в исходном графе вершины A и B соединены ребром длины 2.

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

выбрать начальную вершину
создать начальную кайму из вершин, соединенных с начальной
while вершина назначения не достигнута do
	выбрать вершину каймы с кратчайшим расстоянием до начальной
	добавить эту вершину и ведущее в нее ребро к дереву
	изменить кайму путем добавления к ней вершин, 
		соединенных с вновь добавленной
	for всякой вершины каймы do
		приписать к ней ребро, соединяющее ее с деревом и 
			завершающее кратчайший путь к начальной вершине
	end for
end while
			

     На рис. 2 приведен пример исполнения этого алгоритма. Алгоритм выполняется на том же графе (рис. 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, поэтому изменения в наборе путей не производится.
     На рис. 2 (г) мы можем выбрать теперь либо путь из A в F, либо путь из A в E, проходящий через вершину B: оба они имеют длину 5. Какой из путей будет выбран при исполнении программы, зависит от способа хранения данных в ней. Мы же, встретившись с необходимостью добавить вершину, будем всегда выбирать вершину, метка которой первая в лексикографическом порядке.


     В результате получим ситуацию с рис. 2 (д). Добавление к дереву вершины E не меняет остальных связей, поэтому теперь мы можем добавить вершину F и получим картинку с рис. 2 (е). Обратите внимание на то, что, хотя добавление вершины F и привело к изменению ребра, ведущего из D, если бы мы начали с F, все равно на очередном шаге мы должны были бы добавить E.
     На рис. 2 (е) видно, что путь в вершину D короче пути в вершину G. Поэтому мы добавляем к дереву вершину D и получаем ситуацию, изображенную на рис. 2 (ж). Осталось добавить только вершину G, и в результате мы получаем дерево кратчайшего пути с рис. 2 (з). Длина кратчайшего пути из A в G равна 10.


     На примере с рис. 2 мы имеем дело с полным деревом кратчайших путей, поскольку целевая вершина G была добавлена к дереву последней. Если бы мы добрались до нее раньше, алгоритм бы тотчас завершил свою работу. Могут возникнуть ситуации, в которых нас интересуют кратчайшие пути из данной вершины во все остальные. Если, например, мы имеем дело с небольшой компьютерной сетью, скорости передачи данных между узлами которой приблизительно постоянны, то для каждого из компьютеров сети мы можем выбрать кратчайший путь до каждого из остальных компьютеров. Поэтому при необходимости переслать сообщение единственное, что нам потребуется, это воспользоваться заранее рассчитанным наиболее эффективным путем.