Этап 2. Проводим последовательный поиск дуг кратчайшего пути

Проводим последовательный поиск дуг кратчайшего пути.

Вершине предшествуют вершины . Кратчайшее расстояние получаем при прохождении по дуге .

Вершине предшествуют вершины . Кратчайшее расстояние получаем при прохождении по дуге .

Таким образом, кратчайший путь от вершины x ₁ до вершины x ₇ построен. Его длина (вес) равна 21, т.е. , сам путь образует следующую последовательность дуг .

Ответ: ;