Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину а с вершиной b.

1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину а с вершиной \( b \).

Решение. Используем известный алгоритм Дейкстры. Приведем его формальное описание.

Рассмотрим случай, когда каждой дуге \( u \) графа \( G=\{X, \Gamma\} \) сопоставлено положительное число \( l(u) \). Это число \( l(u) \) можно назвать длиной дуги. Длиной пути \( \mu \) назовем сумму длин дуг, входящих в путь \( \mu \) :
\[
L[\mu]=\sum_{u \in \mu} l(u) .
\]

Возникает следующая задача. Найти в графе \( G \) путь \( \mu \) кратчайшей длины, соединяющий вершину а с вершиной \( b \).

Алгоритм решения
\( \mathbf{1}^{\circ} \). Перенумеровать вершины графа \( G \) так, чтобы вершина а получила номер 0 . Обозначить вершину а через \( x_{0} \). (При этом вершина \( b \) совпадет с некоторой вершиной \( x_{n} \) ).
\( \mathbf{2}^{\circ} \). Присвоить каждой вершине \( x_{i} \) метку \( \lambda_{i} \) так, чтобы \( \lambda_{0}=0, \lambda_{i}=+\infty \) при \( i>0 \).
\( 3^{\circ} \). Найти такую дугу \( \left(x_{i}, x_{j}\right) \), для которой \( \lambda_{j}-\lambda_{i}>l\left(x_{i}, x_{j}\right) \). (Полагаем, что \( \infty-\infty=0 \).) У вершины \( x_{j} \) заменить метку \( \lambda_{j} \) на новую, меньшую метку \( \lambda_{j}=\lambda_{i}+l\left(x_{i}, x_{j}\right) \).
\( 4^{\circ} \). Применять правило \( 3^{\circ} \) до тех пор, пока для каждой дуги \( \left(x_{i}, x_{j}\right) \) не

станет справедливым неравенство: \( \lambda_{j}-\lambda_{i} \leq l\left(x_{i}, x_{j}\right) \).
\( 5^{\circ} \). Во множестве \( \Gamma^{-1} x_{p_{1}}\left(x_{n}=b\right) \) найти такую вершину \( x_{p_{2}} \), что \( \lambda_{n}=\lambda_{p_{1}}+l\left(x_{p_{1}}, x_{n}\right) \).

Аналогично, во множестве найти такую вершину \( x_{p_{2}} \), чтобы было справедливо равенство \( \lambda_{p_{1}}=\lambda_{p_{2}}+l\left(x_{p_{1}}, x_{p_{2}}\right) \) и т.д.

После некоторого числа шагов вершина \( x_{p_{k}} \) совпадет с вершиной \( x_{0}\left(x_{0}=a\right) \).

Путь \( \mu=\left\lfloor a=x_{P_{k}}, x_{P_{P_{-}}}, \ldots, x_{P_{1}}, b\right\rfloor \) - кратчайший, его длина равна \( L[\mu]=\lambda_{n} \).