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

Создается таблица для отслеживания расстояния от исходной (S) вершины. Расстояние до каждой вершины устанавливается равным бесконечности, за исключением самого источника. Другая переменная, π, используется для отслеживания предыдущей вершины, из которой была достигнута указанная вершина.

Алгоритм Дейкстры начинается с источника, S, и ослабляет ребра, которые непосредственно связаны с ним, в алфавитном порядке. Первое ребро, которое нужно ослабить, - это от S до A. Значение для A обновляется с бесконечности до 5, а предшественник обновляется до S. Край S-A также помечен как завершенный.

Далее расслабляется край S-I. Расстояние до I обновляется до 15, а предшественник помечается как S. Край S-I помечен как посещенный. Все исходящие ребра из S были посещены, поэтому S отмечен как завершенный.

Алгоритм Дейкстры перемещается из вершины S в вершину A. Вершина A выбирается, поскольку она является ближайшей посещаемой вершиной к источнику. Тот же процесс повторяется: все непосредственные исходящие вершины посещаются из вершины A. Эти вершины - это C и E. Вершина C посещается первой, поскольку она идет первой по алфавиту. Расстояние до C обновляется до 8, поскольку вершина A может быть достигнута за 5 единиц, а вершина C может быть достигнута за другие 3 единицы. Предшественник установлен на A, а край A-C помечен как посещенный.

Следующей посещается вершина E. Расстояние до вершины E обновляется до 7 (S-A-5 + A-E-2), а предшественник E обновляется до A. Поскольку все исходящие ребра из A были посещены, вершина A помечается как завершенная.

Алгоритм Дейкстры выбирает следующую ближайшую вершину. Вершина I в настоящее время находится на расстоянии 15 единиц от источника, вершина E - на расстоянии 7 единиц, а вершина C - на расстоянии 8 единиц. Вершина E является ближайшей, поэтому выбирается следующей. Поскольку из вершины E нет исходящих ребер, она помечается как завершенная.

Поскольку вершина C находится на расстоянии 8 единиц, а вершина I - на расстоянии 15 единиц, следующей выбирается вершина C. Вершина C имеет 3 исходящих ребра: C-B, C-D и C-H. Вершина B посещается первой, поскольку она следующая по алфавиту в списке. Расстояние до B обновляется до 15 (S-A-C-8 + C-B-7), а предшественник устанавливается как C. Край C-B помечен как посещенный.

Затем алгоритм Дейкстры посещает вершину D. Расстояние до вершины D обновляется до 14 (S-A-C-8 + C-D-6), а предшественник D устанавливается как C. Ребро C-D помечается как посещенное.

Посещается последнее исходящее ребро от C, ребро C-H. Расстояние до вершины H обновляется до 11 (S-A-C-8 + C-H-3), а предшественник H обновляется до C. Поскольку все исходящие ребра были посещены из C, вершина C помечается как завершенная.

Алгоритм Дейкстры выбирает следующую вершину. Вершина I находится на расстоянии 15 единиц от источника, вершина B находится на расстоянии 15 единиц, вершина D находится на расстоянии 14 единиц, а вершина H находится на расстоянии 11 единиц. Поскольку вершина H является ближайшей к источнику, она выбирается следующей. Вершина H имеет два исходящих ребра: H-C и H-D. Вершина C посещается первой. Вершина C уже может быть достигнута за 8 единиц, поэтому нет смысла достигать ее за 20 единиц. Расстояние до вершины C остается неизменным, а ребро H-C помечается как посещенное.

Следующая вершина D посещается через ребро H-D. Поскольку расстояние до вершины D через ребро H-D (12 единиц) короче, чем расстояние до вершины D через ребро C-D (14), расстояние до вершины D обновляется до 12; предшественник вершины D обновляется до H. Ребро H-D помечается как завершенное; так как все исходящие ребра из H были посещены, H помечается как завершенное.

Алгоритм Дейкстры выбирает следующее ближайшее ребро, исследуя все доступные, непосещенные вершины. Вершина I может быть достигнута за 15 единиц, D может быть достигнута за 12 единиц, а B может быть достигнута за 15 единиц. Поскольку D - ближайшая к источнику вершина, выбирается вершина D. Вершина D имеет одно исходящее ребро, D-I. Расстояние до вершины I от D равно 14. Поскольку вершина I может быть достигнута за 14 единиц через ребро D-I, расстояние до вершины I обновляется до 14, а для предшественника устанавливается значение D. Край D-I помечается как посещенный. Все исходящие ребра из вершины D были посещены, и вершина D помечена как завершенная.

Алгоритм Дейкстры проверяет все ребра, которые можно посетить. Вершина I находится на расстоянии 14 единиц, а вершина B - на расстоянии 15 единиц. Поскольку вершина I является ближайшей к источнику, следующей выбирается вершина I.

Вершина I не имеет исходящих ребер, поэтому вершина I помечается как завершенная. Вершина B - единственное другое доступное непосещаемое ребро из источника, поэтому следующей выбирается вершина B.

Вершина B имеет одно исходящее ребро: B-F. Вершину F можно достичь за 19 единиц
(S-A-C-B-15 + B-F-4). Расстояние до F обновляется до 19, а для предшественника устанавливается значение B. Ребро B-F помечается как посещенное, и, поскольку других исходящих ребер из вершины B нет, оно помечается как завершенное.

Вершина F - ближайшая к источнику вершина. Вершина F имеет одно исходящее ребро, F-G. Вершина G может быть достигнута за 21 юнит. Расстояние до G обновляется до 21, а для предшественника G устанавливается значение F. Ребро F-G помечается как посещенное, а поскольку других исходящих ребер из F нет, вершина F помечается как завершенная.

Вершина G - это последняя непосещенная вершина. Вершина G имеет одно исходящее ребро, от G до B. Расстояние до вершины G через ребро G-B составляет 21 единицу. Поскольку расстояние до B через ребро C-B ближе, чем через ребро G-B, расстояние до B сохраняется равным 15. Ребро G-B помечается как посещенное, а поскольку все исходящие ребра из G были посещены, вершина G помечается как завершенная. Все вершины ориентированного графа были посещены, поэтому алгоритм Дейкстры завершен. В списке ниже показан кратчайший путь к каждой вершине от источника.

Если вам понравилось то, что вы прочитали, посмотрите мою книгу Иллюстративное введение в алгоритмы.