Aлгоритмы на графах
Страница 3
Теорема. Алгоритм Прима–Краскала получает минимальное остовное дерево.
Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, после проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер и n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину. Пусть {
, 
, …, 
} ребра остовного дерева в том порядке как их выбирал алгоритм, т.е. 
£
. Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.
<<…< (1)
Если полученное дерево не минимально, то существует другое дерево, заданное набором из n-1 ребер {
, 
, …, 
}, такое что сумма длин 
меньше суммы длин . С точностью до обозначений
<<…< (2)
Может быть =, = и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что 
¹
. Поскольку выбиралось по алгоритму самым малым из не образующих цикла с ребрами , , …, 
, то <. Теперь добавим к дереву (2) ребро ; в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра , , …, , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора , …, , причем d>. Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.
Для реализации алгоритма понадобятся:
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 – матрица расстояний.
Опишем алгоритм Дейкстры: