Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины 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 ко всем вершинам графа.