Для реализации алгоритма понадобятся:

Matrix – матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity – просто большому числу (машинная бесконечность);

Color – массив цветов вершин;

Ribs – в этом массиве запоминаются найденные ребра;

a, b – вершины, соединяемые очередным минимальным ребром

len – длина дерева.

Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке – количество вершин n, а остальные n строк по n чисел в каждой – матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.

Program Algorith_PrimaKrascala;

Uses Crt;

Const MaxSize =100;

Infinity =1000;

Var Matrix: array[1 MaxSize, 1 MaxSize] of integer;

Color: array[1 MaxSize] of integer;

Ribs: array[1 MaxSize] of record

a, b: integer;

end;

n, a, b, k, col, i, len: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, 'INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do read(f, matrix[i, j]);

Readln(f)

End;

For i:=1 to n do color[i]:=i;

len:=0

End;

Procedure Findmin(var a, b: integer);

Var min, i, j: integer;

Begin

min:=infinity;

For i:=1 to n-1 do

For j:=i+1 to n do

If (Matrix[i, j]<min) and (color[i]<>color[j]) then

Begin

min:=Matrix[i, j];

a:=i;

b:=j

End;

len:=len+min

end;

Begin

Clrscr;

Init;

For k:=1 to n-1 do

Begin

Findmin(a, b);

Ribs[k].a:=a;

Ribs[k].b:=b;

col:=Color[b];

For i:=1 to n do

If color[i]=col then color[i]:=color[a];

End;

For i:=1 to n-1 do

Writeln(ribs[i].a, ' –', ribs[i].b);

Writeln('Length= ', len);

Readkey

End.

Для такого входного файла

8

0 23 12 1000 1000 1000 1000 1000

23 0 25 1000 22 1000 1000 35

12 25 0 18 1000 1000 1000 1000

1000 1000 18 0 1000 20 1000 1000

1000 22 1000 1000 0 23 14 1000

1000 1000 1000 20 23 0 24 1000

1000 1000 1000 1000 14 24 0 16

1000 35 1000 1000 1000 1000 16 0

программа напечатает:

1–3

5–7

7–8

3–4

4–6

2–5

1–2

Length= 125.

Алгоритм Дейкстры.

Дана дорожная сеть, где города и развилки будут вершинами, а дороги – ребрами. Требуется найти кратчайший путь между двумя вершинами.

Можно предложить много процедур решения этой задачи, например, физическое моделирование такого рода: на плоской доске рисуется карта местности, в города и в развилки вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются веревками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между кольцом i и кольцом k, нужно взять i в одну руку, взять k в другую и растянуть. Те веревки, которые натянутся и не дадут разводить шире, и образуют кратчайший путь между i и k. Однако, математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще, например, предложенный Дейкстрой еще в 1959 г. Этот алгоритм решает более общую задачу:

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

Алгоритм использует три массива из n чисел каждый. Первый массив Visited содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); второй массив Len содержит расстояния от ­­– текущие кратчайшие расстояния от начальной до соответствующей вершины; третий массив C содержит номера вершин – k-ый элемент C есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю. Используется также Matrix – матрица расстояний.

Опишем алгоритм Дейкстры:

1 (инициализация). В цикле от 1 до n заполнить значением False массив Visited; заполнить числом i массив C (i – номер стартовой вершины); перенести i-ю строку матрицы Matrix в массив Len;

Visited[i]:=True; C[i]:=0;

2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j]£Len[k];

Затем выполнять следующие операции:

Visited[i]:=True;

если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

{Если все Visited[k] отмечены, то длина пути от до равна C[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}.

3 (выдача ответа). {Путь от до выдается в обратном порядке следующей процедурой:}

3.1 z:=C[k];

3.2 Выдать z

3.3 z:=C[z]. Если z =0, то конец,

иначе перейти к 3.2.

Теорема.Алгоритм Дейкстры – корректен.

Доказательство. Теорему докажем по индукции. Рассмотрим 1-й шаг, когда находится min Len[k] (k¹i), пусть минимум достигается на вершине j. Остальные (k¹i, j) пока лишь верхние оценки длин путей из в (они могут уменьшаться в ходе выполнения алгоритма, но Len[j] – окончательная длина пути [… ], совпадающего с дугой [, ]. Если бы существовал путь короче, он бы выглядел [, …], но уже первая его дуга не меньше, чем весь путь [, ], а остальные дуги имеют положительную длину).

Мы разбили все вершины на два класса: С – неотмеченных вершин и С’ – отмеченных вершин. После 1-го общего шага , Î С’, и, очевидно, все кратчайшие пути (пока “все” – означает “один”) из v’ÎС’ не содержат vÎС в качестве промежуточной.