2.9.1. Задача о кратчайшем пути между двумя вершинами (ориентированного графа

Каждой дуге графа G(X, V) ставиться в соответствие неотрицательное число - l(V) - длина его дуги. Требуется для двух фиксированных вершин Х₀, Х_n найти кратчайший путь, их соединяющий. Если под длиной дуги l(X_i, X_j) понимать стоимость перевозки груза из пункта X_i в пункт X_j, то содержание задачи составит определение пути из Х₀ в Х_n, при котором затраты на перевозки минимальны

2.18

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

Алгоритм решения этой задачи позволяет определить кратчайший путь и его длину за конечное число шагов. Каждая вершина графа получает некоторую числовую метку на первом шаге. Затем метки вершин, вообще говоря, могут меняться, становясь на некотором шаге постоянным числом. Установившаяся метка данной вершины есть кратчайшее рас­стояние от этой вершины до вершины Х₀. Если пути, соединяющего вершины Х₀ и Х_n не существуют, считают длину кратчайшего расстояния между ними +

Алгоритм состоит в выполнении следующих операций:

Шаг 1. Проставить следующие метки: для вершины Х₀ - метку . Для любой другой вершины X_i, - метку

Шаг 2. Найти на графе такую дугу (X_i, X_j), для которой

2.19

Разность считать равной 0. Если такая дуга най­дется, то изменить метку вершины Х_j на

2.20

Если такой дуги нет, то пути, соединяющего Х₀ и Х_n не существует.

Шаг 3. Повторять шаг 2 до тех пор, пока метки вершин не перестанут меняться.

Установившиеся метки обозначим Может быть два случая: 1) . Это значит, что пути, соеди­няющего Х₀ и Х_n не существует. 2) - конечное число. Оно равно кратчайшему расстоянию между Х₀ и Х_n.

Сам путь минимальной длины получим, отмечая вершины, по которым достигается минимум.

На графе-сети между входом и выходом графа путь ми­нимальной длины всегда существует. Его можно определить за один шаг, если пользоваться формулой:

2.21

Пример. Найти кратчайший путь между вершинами Х₀ и X₅. Длины дуг заданы на графе (рис. 2.17).

Рис. 2.17.

Решение. Имеем ориентированный граф без циклов, имеющий одну вершину Х₀ без входящих дуг - вход графа, и одну вершину Х₅ без выходящих дуг - выход графа. Такой граф есть граф-сеть.

Следуя алгоритму, обозначим Далее меняем метки всех вершин, кроме Х₀. Смысл метки -некоторое расстояние от вершины Х_i, до Х₀. Поэтому метка вершины Х₀ не меняется.

Для вершины X₁: Поэтому меняем метку вершины X₁ на

Х₀

Справа отметим вершину, из которой пришли в вершину X₁. Аналогично для вершины Х₂:

Х₀

В вершину Х₃ ведут два пути: из вершины Х₀ и из 'вершины X₁. Поэтому используем формулу 2.21:

Х₀

Справа обозначим вершину, по которой достигается минимум.

Аналогично для вершины Х₄ и Х₅ получаем:

Х₁

Х₄

Полученное значение = 5 есть длина минимального пути из Х₀ в Х₅. Сам путь получим, проходя по отмеченным вершинам из Х₅ в Х₀: Х₅, Х₄, X₁, Х₀, т.е. = {Х₀, X₁, Х₄, Х₅} -искомый путь, а его длина 1( ) = 5.

Задача может иметь не единственное решение.