IF(NEXT .EQ. V) RETURN 4»- K-V,1

С ЗАПОМИНАНИЕ КРАТЧАШ1ЕГ0 РАССТОЯНИЯ ЛО НЕОПРЕДЕЛЕННОЙ С ВЕРШИНЫ С

350 к • 1 1 И-1

L«DIST(1) 1 М-1

SO ЧОО 1 -1.NUMUH 1 Н-1

JFIDIST(I) .GE. Ц) GO ТО ЧСО N,C (H-1)(H)/2.G

LaDlSTll) D Н

К « I D Н

, 400 COMTINUE" N (Н-1)(М)/2 С

с ДОБАВЛЕНИЕРЕБРА К ДЕРЕВУ КРАТЧАЙШИХ ПУТЕЙ С

Р5ЕЗ . ЙСЕ8 + 1 1 М-1

FROH(EIIGES) в VERTEX(K) 1 М-1

TO(EDGES) eUNDET(K) 1 «-1

LENGTWEDGES) «U 1 М-1

. NEXT - UNDEKKJ 1 H-1 •

С ДОСТИГЛИ ди ны и с

с ИСКЛЮЧЕНИЕ вновь ОПРЕДЕЛЕННОЕ! ВЕРШИНЫ ИЗ СПИСКА--

с НЕОПРЕДЕЛЕННЫХ

DIST(K) «DIST(NUMUN) i М-2

i)NDET(K) UNDET{NUMUN) 1 W-2

VERTEXlK) e VERTEXtNUHUN) 1 M-2

С ОСТАЛИСЬ ЛИ.НЕОПРЕДЕЛЕННЫЕ ЕЕРШИНЫ С

riUMUN - HUHUN - 1 ! Го

СО то гоо ""

Рис. 6.2.4. Продолжение

стороны, если F=NEXT, то В15Т(У)=В18Т(КЕХТ)+Л (NEXT, V)=m. Это также противоречит нашему предположению, что m<DIST([/).

Теперь предположим, что вершина V выбрана при {п+ 1)-м выполнении шага 4, т. е. что V оказывается (/г-Ь1)-й «определенной» вершиной. Требуется показать, что DIST(V) - длина кратчайшего пути от V0 до V.

Предположим, что это неверно. Тогда должен существовать путь Р от V0 до V, длина которого меньше, чем DIST(V). Из предыдущего мы знаем, что DIST (V) - длина кратчайшего пути от V0 до V, где V - единственная «неопределенная» вершина. Следовательно, путь Р должен содержать по крайней мере еще одну «неопределенную» вер

шину. Пусть и будет первой «неопределенной» вершиной, встреченной при прохождении Р от V0 до V. Из этого следует, что расстояние от V0 до и короче, чем расстояние от V0 до V, более того, подпуть Р от V0 до и содержит только одну «неопределенную» вершину, а именно U. Следовательно, по предположению индукции В15Т(У)<В15Т(1/), что противоречит тому, что V была выбрана на шаге 4. Таким образом, пути Р не существует, а DIST (У) - длина кратчайшего пути otVO до V.

Тот факт, что алгоритм Дейкстры определяет кратчайшее расстояние от V0 до W, следует из того, что алгоритм останавливается при NEXT=iy, когда W становится «определенной». Это должно произойти, так как G - конечная и связная сеть, а следовательно, может произойти самое большее УИ--1 повторений шагов 3 и 4.

Следует отметить, что приведенная реализация алгоритма Дейкстры (рис. 6.2.4), по существу, идентична пооператорной реализации алгоритма Прима (см. гл. 4). В подпрограмме DIJKST мы задаем на входе матрицу смежности Л, число вершин М, начальную и конечную вершины V0 и W. Выходная информация подпрограммы состоит из троек чисел- FROM (/), Т0(/) и LENGTH (/), где (FROM(/), Т0(/)) - ребра дерева кратчайших путей, выбранных алгоритмом при поиске кратчайшего расстояния до вершины W; LENGTH (/) содержит кратчайшее расстояние от V0 до вершины Т0(/).

Вершины (VERTICES), помеченные алгоритмом DIJKSTRA как «неопределенная», запоминаются в массиве UNDET (подпрограмма DIJKST). Вершины, получившие пометку «определенная», удаляются из массива UNDET. Два столбца кратностей вьшолиения операторов, помещенные правее текста операторов, будут далее объяснены при анализе сложности.

Анализ наихудшего случая трудоемкости подпрограммы DIJKST, по существу, совпадает с аналогичным анализом подпрограммы PRIM. Самый правый столбец на рис. 6.2.4 указывает максимально возможную кратность выполнения каждого оператора. Суммируя эти величины и учитывая, что

получим верхнюю границу ЪМЦ-М-7 числа выполнений операторов подпрограммы DIJKST. Таким образом, в наихудшем случае подпрограмма имеет сложность 0{М).

Заметим, что если мы удалим оператор

IF (NEXT .EQ. W) RETURN и заменим оператор GO ТО 200 на

IF (NUMUN .GE. 1) GO TO 200 RETURN

to получившаяся подпрограмма будет вычислять кратчайшее рас-

стояние от VO до всех остальных вершин G. Следовательно, и эта задача о кратчайшем пути имеет в наихудшем случае такую же сложность

Теперь оценим нижнюю границу ожидаемой трудоемкости подпрограммы DIJKST. Алгоритм работает итеративно, и каждая итерация добавляет одну вершину к множеству «определенных». Если на п-й итерации добавляется вершина W, алгоритм завершает работу. Пусть значение L (п) равно наименьшему числу повторений операторов, выполняемых при п итерациях. Нашей целью будет вычислить L(n) для п=1, 2, . . ., М-1, а затем найти среднее этих чисел в предположении, что вершина W добавляется к списку «определенных» с равной вероятностью на любой итерации. При таком предположении нижняя граница получаегся меньшей, чем она могла бы оказаться в действительности, так как для большинства приложений, W может, вероятно, оказаться вершиной, довольно далекой от V0.

Нетрудно убедиться, что если мы прекратим выполнение после точно одной итерации, то L(l)=7/W+14. Если потребуются в точности две итерации, минимальное количество выполненных операторов равно

L (2)=[L (1)-11+5+1+5 (Л1-2)+3-Ь 3 (М-2)+7=Ь (l)+8/W-1. При вычислении L(l) и L(2) вспомни.м, что они означают минимальные значения. Следовательно, мы всегда выполняем операторы GO ТО 300 и GO ТО 400 в циклах DO, оканчивающихся соответственно на метках 300 и 400. Кроме того, отметим, вычисляя L(2), что мы не выполняем оператор RETURN в первой итерации - отсюда возникает член 1(1)-1.

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

L(l)=7/W+14;

L{n)=L(n-l)+8(M~n)+l5 для 2<п<М-1.

Это рекуррентное соотношение непосредственно следует из детального вычисления L(2) в предыдущем абзаце.

Чтобы получить выражение для L(n) в замкнутой форме, не содержащее L(n-1), проделаем следующие вычисления:

L (n)~L (п-1)=8 (М-п)+15; L (м-1)-L (п-2)=8[Л1- (п-1)]+15; L (п-2)-L (п-3)=8[/W- (п-2)]+15;

L(2)-L(l)=8(yW-2)+l5. Теперь сложим все эти п-1 уравнений и убедимся, что в левой части