На сети дорог указаны стоимости перевозки единиц груза между отдельными пунктами сети. Найти наиболее

На сети дорог указаны стоимости перевозки единиц груза между отдельными пунктами сети. Найти наиболее экономный маршрут доставки груза. Чему равны суммарные затраты по доставке единицы груза оптимальным маршрутом?

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

. На первом шаге алгоритма каждая вершина , для которой существует дуга , получает временную метку (помечается из вершины ). Затем вершина , для которой имеет минимальное значение, получает постоянную метку (если минимум достигается на нескольких вершинах, то берется любая из них). Кратчайший путь из в проходит по ребру .
На втором шаге алгоритма для каждой вершины , которая имеет временную метку и для которой существует дуга , вычисляется сумма и, если эта сумма меньше, чем , то вершина получает новую временную метку
(помечается из вершины ).
Затем среди всех вершин, имеющих временные метки, находится вершина , для которой имеет минимальное значение, и её временная метка делается её постоянной меткой .
Пусть – вершина, получившая на () – ом шаге постоянную метку. Тогда на – ом шаге алгоритма для каждой вершины с временной меткой, для которой существует дуга , вычисляется сумма и, если эта сумма меньше чем , то вершина v получает новую временную метку
(помечается из вершины )