Решение задачи о кратчайшем пути матрица смежности 0, 1, 0, 1, 0, 0, 0, 0,

Решение задачи о кратчайшем пути матрица смежности 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, Матрица инцидентности 1, 0, 0, 0, 0, 0, 0, -1, 1 -1, 1, 1, -1, 0, 0, 0, 0, 0 0, 0, 0, 1, -1, 0, 0, 0, 0 0, -1, 0, 0, 1, -1, 0, 0, -1 0, 0, -1, 0, 0, 1, 1, 0, 0 0, 0, 0, 0, 0, 0, -1, 1, 0 Рис. 1. Исходные данные к задаче в виде взвешенного орграфа Необходимо найти кратчайший путь между вершинами 1 и 2.

Введем обозначение: С(Т) – длина кратчайшего пути из вершины 1 в вершину Т.
Оставленная задача состоит в вычислении С(2) и указании пути с минимальной стоимостью проезда.
Рассмотрим подробнее взвешенный орграф, представленный на рисунке 1.
В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 1, либо из вершины 3, пройдя путь, равный 2, либо из вершины 5, пройдя путь, равный 1. Поэтому справедливо соотношение
Необходимо найти кратчайший путь между вершинами 1 и 3.
В вершину 3 можно попасть либо из вершины 2, пройдя путь, равный 1, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение
QUOTE C5=minC3+2;C6+3
Поскольку очевидно, что С(5) – положительное число, то из последнего соотношения вытекает, что 2<С(5)+2, то есть вычислять значение С(5) на данном этапе не имеет смысла.
Необходимо найти кратчайший путь между вершинами 1 и 4.
В вершину 4 можно попасть только из вершины 3, пройдя путь, равный 5. Поэтому
QUOTE C5=minC3+2;C6+3
Необходимо найти кратчайший путь между вершинами 1 и 5.
В вершину 5 можно попасть либо из вершины 4, пройдя путь, равный 3, либо из вершины 6, пройдя путь, равный 4, либо из вершины 7, пройдя путь, равный 1. Поэтому справедливо соотношение
QUOTE C5=minC3+2;C6+3
В вершину 6 можно попасть либо из вершины 1, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 12

. Поэтому справедливо соотношение
В вершину 7 можно попасть либо из вершины 4, пройдя путь, равный 8, либо из вершины 6, пройдя путь, равный 4. Поэтому справедливо соотношение
Возвращаемся к вычислению С(5):
Ответ. В вершину 2 можно попасть из вершины 1. Кратчайший путь таков: 1→2. Длина кратчайшего пути равна 1.
В вершину 3 можно попасть из вершины 1. Кратчайший путь таков: 1→2→3. Длина кратчайшего пути равна 2.
В вершину 4 можно попасть из вершины 1. Кратчайший путь таков: 1→2→3→4. Длина кратчайшего пути равна 7.
В вершину 5 можно попасть из вершины 1. Кратчайший путь таков: 1→6→5. Длина кратчайшего пути равна 8.
В вершину 6 можно попасть из вершины 1. Кратчайший путь таков: 1→6. Длина кратчайшего пути равна 4.
В вершину 7 можно попасть из вершины 1. Кратчайший путь таков: 1→6→7. Длина кратчайшего пути равна 8.
Задача о кратчайшем пути для исходных данных полностью решена.

Рисунок 6.1
В качестве начального взять нулевой поток, когда все zij = 0.
Найти какой-нибудь путь из X0 в X10, например, μ1={ X1, X3, Х5, X7, Х10}.
По этому пути можно пропустить поток величиной не более
θ1 = min{ c13, с35 , c57, с710 } = min {9, 6, 7, 9} = 6.
Пропустить поток величины 6 единицы по указанному пути