Методы определения кратчайших путей

1. Метод присвоения меток

Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.

Пример. Узел 7 — склад, остальные узлы — строительные площадки компании. Показатели на дугах — расстояния в километрах.

Решение.

Самостоятельно. Компания грузовых перевозок осуществляет услу­ги по перевозке грузов между Воронежем (В) и райцентрами. Если компания получает заказ на обслуживание, она как можно быстрее посылает грузовик в райцентр, из которого поступил заказ. Так как существенны быстрое обслуживание и минимальные транспортные затраты, большое значение приобретает то, что грузовик проследует из Воронежа в соответствующий райцентр по наиболее короткому маршруту. Сеть, представленная на рисунке, отображает сеть дорог. Расстояния указаны в километрах.

Найти кратчайшие маршруты от Воронежа до всех 10 райцентров. Какова длина кратчайшего пути от Воронежа до райцентра 10? Како­ва длина кратчайшего пути от Воронежа до райцентра 8? Проходит ли кратчайший путь от Воронежа до райцентра 9 через райцентр 6?

2. Кратчайший путь между двумя пунктами

Как кратчайшим путем попасть из одной вершины графа в другую? В терминах управления цепями поставок: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной.

Обозначения:

xi - исходный узел;

х_n - узел назначения;

d_ij - расстояние на сети между смежными узлами х_i и х_j.

Uj - кратчайшее расстояние от узла х_i до узла х_j. U₁=0.

Алгоритм нахождения кратчайшего пути состоит в последо­вательном нахождении значений Uj для каждого узла от исходно­го узла до узла назначения. Значение Uj для каждого узла рассчи­тывается по формуле:

Uj = min{ U_i + d_ij }

Процедура заканчивается, когда получено значение U_n для узла назначения.

Кратчайший маршрут от исходного узла до узла назначения определяется, начиная с узла назначения, путем прохождения узлов в обратном направлении по дугам, на которых реализова­лись минимальные значения расстояний на каждом шаге.

Пример. Определить кратчайшее расстояние между узлами x₁ и х₇.

U₁=0;

U₂ = U₁ + d₁₂ = 0 + 2 = 2;

 U₃= U₁ + d₁₃ = 0 + 4 = 4;

U₄= min{ U₁ + d₁₄, U₂+d₂₄, U₃+d₃₄} = min{0 + 10,2 + 11,4 + 3} = 7;

U₅= min{ U₂ + d₂₅, U₄ + d₄₅ } = min{2 + 5, 7 + 8} = 7;

U₆ = min{ U₃ + d₃₆, U₄+d₄₆ } = min{4+ 1, 7 + 7} = 5;

U₇ = min{ U₅ + d₅₇, U₆+d₆₁ } = min{7 + 6, 5 + 9} = 13.

Самостоятельно.

1. Определить кратчайшее расстояние между пунктами 1 и 4.

2. На рисунке изображена транспортная сеть между населенными пунктами. Найдите кратчайшие маршруты между пунктами:

1) x1 и х8;

2) х1 и х6;

3) х4 и х8

4) x2 и х6;

3. На рисунке изображена транспортная сеть между городами. Найдите кратчайшие

маршруты между городами А и В.