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

Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра. В общем случае этот метод основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от некоторой вершины s к рассматриваемой вершине. Эти пометки постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становится постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от t к рассматриваемой вершине. Рассмотрим подробнее этот алгоритм.

Дан граф G = (X, A, C) со взвешенными дугами, пример которого показан на рис. 9.1 Обозначим L(х_i) пометку вершины х_i. Веса дуг (или ребер) даны матрицей весов (таблица 9.1).

Рис. 9.1. Граф со взвешенными дугами

Рассмотрим алгоритм нахождения кратчайшего пути от вершины s к вершине t графа и более общий случай: от вершины s ко всем вершинам графа.