Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине. Рассмотрим подробнее этот алгоритм.
Дан граф G = (X, A, C) со взвешенными дугами, пример которого показан на рис. 9.1 Обозначим L(хi) пометку вершины хi . Веса дуг (или ребер) даны матрицей весов (таблица 9.1).
Рис. 9.1. Граф со взвешенными дугами
Таблица 9.1. Матрица весов расстояний
с1
с3
с2
с5
с4
Рассмотрим алгоритм нахождения кратчайшего пути от вершины s к вершине t графа и более общий случай: от вершины s ко всем вершинам графа.