Задача нахождения кратчайшего пути

Рассмотрим решение задачи нахождения кратчайшего пути методом «волны».

Пример

Допустим, в п. 1 находится склад, а в остальных пунктах – строительные площадки компании (рис. 8.6).

П оказатели на дугах – расстояния в километрах. Надо найти кратчайшие расстояния от склада до каждой строительной площадки.

Рис. 8.6.

Первый пункт является стартовым и ему присваивается постоянная метка.

Постоянная метка присваивается тем пунктам, если для них определено кратчайшее расстояние.

1) рассмотрим каждый пункт, в который можно попасть непосредственно из пункта 1.

Д о п. 2 расстояние в 3 км, до п. 3 – 8 км. Т.о. пунктам 2 и 3 присвоены временные метки [3,1] и [8,1] соответственно (рис. 8.7). Первое число в метке обозначает расстояние от п.1, второе число – это номер пункта, из которого непосредственно «пришли» в рассматриваемый пункт. Далее рассматриваются все временные метки на предмет нахождения метки с минимальным расстоянием. На данный момент это метка [3,1]. Пункту 2 присваиваем постоянную метку и фиксируем дугу из п.1 в п.2 (рис. 8.9).

Рис. 8.7

Рис. 8.9.

2 ) теперь рассматриваются все пункты, которые ещё не имеют постоянных меток и непосредственно связаны с пунктом 2, т.е. мы рассматриваем п. 4 и п. 5. Достичь п. 4 можно, преодолев 3+2=5 км., а п. 5 – преодолев 3+5=8 км. Т.о. п. 4 и п. 5 присваиваются временные метки [5,2] и [8,2] соответственно (рис.8.10). Теперь снова рассматриваем временные метки и выбираем из них ту, которая имеет в своём обозначении кратчайшее расстояние, т.е. метку [5,2] для п.4. Эта метка теперь получает статус постоянной и фиксируем дугу из п.2 в п.4 (рис.8.11).

Рис. 8.10.

Рис. 8.11.

3) следующий этап начинается в п. 4, последнем, помеченном постоянной меткой. Как и раньше, рассматриваем каждый пункт без постоянной метки, в который можно попасть непосредственно из п. 4. В этом случае, это единственный п. 6. Для того, чтобы достичь

п . 6 надо преодолеть 5+7=12 км.

Временная метка пункта 6 будет иметь вид [12,4] (рис. 8.12). Среди всех временных метках, которые имеются на данный момент, выбираем ту, которой соответствует наименьшее количество километров. Таких пунктов два: п. 5 и п. 3 ( до каждого из них длина равна 8 км.). Выбираем любой из этих пунктов, например, п. 5. Эта метка

Рис.8.12. фиксируется как и путь из п. 2 в п. 5 (рис. 8.13).

Рис. 8.13.

4 ) теперь рассмотрим пункты, в которые можно попасть из п. 5. Таковым является только п. 6, имеющий уже временную метку. Добавляем к этой временной метке ещё одну, относящуюся к п. 5 (рис. 8.14).

Из имеющихся трёх временных меток опять выбираем ту, в которой указано минимальная длина пути от п. 1 до данного пункта. Таковой меткой является

Рис. 8.14 метка [8,1] для п. 3. Эти пункт и метка получают статус стационарных и путь из п. 1 в п. 3 фиксируется (рис. 8.15).

Рис. 8.15.

5 ) из фиксированного п. 3 можно попасть в п. 6, у которого уже есть две временные метки, но нет постоянной. Добавляем п. 6 ещё одну временную метку [17,3] (рис. 8.16). Т. о. п. 6 имеет три временные метки, т. е. до п. 6 можно пройти тремя путями различной длины. Выбираем наикратчайший путь. Таких пути два: через п. 5 и через п. 6. Выбираем любой, потому что длина их одинаковая. Пусть это будет путь,

проходящий через п. 4. Тогда фиксируем

Рис. 8.16 метку [12,4], п. 6 и путь из п. 4 в п. 6 (рис.8.17).

Рис. 8.17.

Теперь можно использовать информацию в постоянных метках для нахождения кратчайшего пути из п. 1 в любой другой пункт. Например, кратчайший путь из п. 1 в п. 4 есть путь 1 – 2 – 4 и длина его 5 км. Используя этот подход, можно определить кратчайшие пути применительно ко всей сети компании, состоящей из её строительных площадок.

Таблица 8.4.

Пункт	Кратчайший путь из п.1	Расстояние, км.
2 3 4 5 6	1 – 2 1 – 3 1 – 2 – 4 1 – 2 – 5 1 – 2 – 4 – 6	3 8 5 8 12