ClirlsKansbura

гз©ло\

Floyd

SI §"70.

Lexington 7

BuenaVfsfa

10®70(

Glasgow 1

Amtosl

17(a>40j

Natural Bridge

11 05 50 \

) Island

32 ©60

21(3 60

Roanoke Г 21 ©SO

Bedford 22<s>40 l6©40 Moneta

39 ©50

Roc1<y Mount f

31@4o

26© SO;

26 ©40

Alfevisla

,30©40 ,29 ©40

Callands

40 ©40

20 ©40,

Martinsville

26 ©60

Gretna 10 ©60 Chatham

\19©60 : Danville

Рис. 6.2.1. 1--»1ДИте «лучший» маршрут от Лексингтона до Дэнвилла.

га-ся к отысканию кратчайшего пути между двумя заданными вершинами.

Задачи о кратчайших путях относятся к самьш фундаментальным задачам комбинаторной оптимизации, так как многие такие задачи можно свести к отысканию кратчайшего пути на сети. Существуют различные типы задач о кратчайшем пути: (1) между двумя заданными вершинами; (2) между данной вершиной и всеми остальными вершинами сети; (3) между каждой парой вершин в сети; (4) между двумя заданными вершинами для путей, проходящих через одну или несколько заданных вершин; (5) первый, второй, третий и т. д. кратчайшие пути в сети.

Есть что-то удивительное в том, что среди десятков алгоритмов для,

АМН BED Bit BVA GLA LYN NBR ROA АМН BED Bit ROA GLA LYIM NBR

to CO co

Nbr.i

Roa.i

Lex,

NBrj

Amh,

Roa,

Lev.

NBr.

Roa.

-1 -1

АМН BED BIL ROA GLA LYN А1ИН BED 81L ROA LYN

34 oo 00 41 16 CO з? » 2?" 41

Рис. 6.2.2. Первые несколько шагов алгоритма Дейкстры для отыскания кратчайшего пути от LEX до BED.

отыскания кратчайшего пути один из лучших (принадлежащий Дейк-стре), по существу, совпадает с (грубым) алгоритмом Прима, находящим остовное дерево минимального веса (см. гл. 4). Алгоритм Дейкстры, определяющий кратчайшее расстояние от данной вершины до конечной, легче пояснить на примере. Рассмотрим часть карты с рис. 6.2.1, показанную на рис. 6.2.2, как сеть, в которой мы хотим найти кратчайший путь от LEX до BED. Мы представим сеть матрицей смежности Л, в которой:

Л(/, /)= длина ребра между вершинами / и J; Л(/, J)=+oa, если между I и J нет ребра; Л(/, /)=0 для всех /=1,2,. . .,М.

Алгоритм Дейкстры состоит из повторяемых выполнений следующих шагов:

1. Он начинает с определения непосредственных расстояний (т. е. длиной в одно ребро) от заданной вершины (LEX) до всех остальных вершин (рис. 6.2.2, с).

2. Затем он отбирает наименьшее из них в качестве «постоянного» наименьшего расстояния (выбирая выделенное ребро между LEX и BVA на рис. 6.2.2, б).

3. Далее алгоритм добавляет это наименьшее расстояние (7) к длинам ребер от новой вершины BVA до всех остальных вершин.

4. Он сравнивает эту сумму с предыдущим расстоянием от LEX до остальных вершин и заменяет прежнее расстояние, если новое меньше.

5. Затем новая вершина BVA удаляется из списка вершин, до которых еще не определены кратчайшие расстояния. В данном примере последняя вершина этого списка (ROA) заменяет вновь определенную вершину BVA и список укорачивается на один элемент (см. списки на рис. 6.2.2, а и 6.2.2, б).

Затем весь этот процесс повторяется, присоединяется новое кратчайшее расстояние к сниску и т. д., пока конечная вершина BED не окажется соедииснной с LEX путем из выделенных ребер.

На вг<-роя итерации расстояние (см. рис. 6.2.2, б) до NBR (10) миР--1йально. Это значение используется для обновления расстояния до ROA (становится 41 вместо оо), а затем NBR удаляется из списка. На третьей итерации (см. рис. 6.2.2. в), расстояние до GLA минимально, что вынуждает нас обновить расстояние до BIL (вместо оо сделать 27). Результирующее множество кратчайших расстояний показано в виде дерева (корневого) кратчайших путей на рис. 6.2.3, где числа в кружочках показывают порядок выбора ребер алгоритмом. Кратчайший путь до данной вершины отыскивается в явном виде прослеживанием пути по этому дереву из корня (LEX) до интересующей нас вершины.

В этом примере вершина BED оказалась последней, достигнутой из LEX. Следовательно, для того чтобы вычислить кратчайшее рас-