Лекция: Алгоритм поиска кратчайшего пути

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

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

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

выбрать начальную вершину

создать начальную кайму из вершин, соединенных с начальной