Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 10. На рис. показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами. Определить маршрут доставки груза, которому соответствуют наименьшие затраты.

Найдем путь минимальной длины методом Дейкстры.

Алгоритм Дейкстры:

1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине 0.

2. Все вершины не выделены.

3. Первая вершина объявляется текущей.

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

5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности,...