Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 10

Найдем путь минимальной длины методом Дейкстры.
Алгоритм Дейкстры:
Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.
Все вершины не выделены.
Первая вершина объявляется текущей.
Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.
Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.
Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Переход на шаг 4.
Распишем итерации алгоритма.
Будем использовать обозначения:
– постоянная метка вершины i;
– новая временная метка вершины i;
– старая временная метка вершины i;
– вес ребра, соединяющего вершины i и j .
Новая временная метка вычисляется по формуле:
После этого из всех временных меток выбирается наименьшая, и она становится постоянной меткой. Действия продолжаются, пока не будут найдены постоянные метки для всех вершин графа. Результаты действий на каждом шаге будем заносить в таблицу. В предпоследний столбец заносим вершину, получившую постоянную метку, в последний столбец – величину этой метки (для данного шага).
Шаг 1. Начальная вершина 1, имеет постоянную метку , остальные вершины имеют временную метку ∞.
Шаг 2. Определяем множество последователей вершины . Пересчитываем их временные метки по основной формуле: , , . Берем вершину 5 с минимальной временной меткой 2, присваиваем этой вершине постоянную метку .
Шаг 3. Определяем множество последователей вершины . Вершина 1 имеет постоянную пометку, поэтому ее не рассматриваем. Пересчитываем временные метки по основной формуле: , , , . Берем вершину 2 с минимальной временной меткой 4, присваиваем этой вершине постоянную метку .
Шаг 4