procedure way(i,j:integer);
{печатает путь между вершинами i и j}
begin
if w[i,j]=0 then write(' ',j)
{печатаем только вершину j,
чтобы избежать повторов}
else
begin
way(i,w[i,j]); way(w[i,j],j)
end
end;
begin
…{заполняем матрицу смежности}
for k:=1 to nn do
for i:=1 to nn do
for j:=1 to nn do
if a[i,k]+a[k,j]<a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
w[i,j]:=k
end;
for i:=1 to nn do
for j:=1 to nn do
begin
write(i);
if i<>j then way(i,j);
writeln
end
end.
Алгоритм Флойда хорош всем, кроме одного: он требует хранить матрицу смежности, а это не всегда возможно. Кроме того, для определения длины кратчайшего пути между двумя конкретными вершинами, его упростить невозможно (то есть все равно придется считать пути между всеми парами вершин). Если вес любого ребра в графе вычисляется по некоторой формуле (например, как расстояние между двумя точками на плоскости, если таковыми являются вершины нашего графа), то матрицу смежности можно не создавать вообще, а в процессе выполнения программы обращаться к функции вычисления веса ребра, соединяющего вершины i и j: a(i, j).
В этом случае для определение кратчайшего пути между вершинами s и t используют алгоритм Дейкстры [5 – 7]. Все вершины в процессе работы этого алгоритма разбиты на два множества: те, до которых кратчайший путь из вершины s уже известен (в программе они помечены значениями true одномерного булевского массива b) и все остальные. Cначала в первом множестве находится только вершина s. На каждом шаге к нему добавляется одна из вершин, текущее известное расстояние до которой минимально среди всех вершин из второго множества, обозначим ее p. Первоначально текущие расстояния (в программе они хранятся в одномерном массиве l) от s до остальных вершин равны ¥, а расстояние до s равно 0, p также равна s. На очередном же шаге мы пытаемся улучшить длину пути до каждой из вершин второго множества, сравнивая выражения l[p]+a(p,i) и l[i]. Нужно показать, почему минимальное из значений l, рассматриваемых на текущем шаге, является длиной кратчайшего пути до соответствующей вершины, а, следовательно, этот путь содержит только вершины из первого множества. Если это не так, то есть кратчайший путь до этой вершины содержит и вершины из второго множества, то минимальной оказалась бы длина пути от s до одной из этих вершин. Значит кратчайший путь до вершины p проходит только через вершины первого множества и больше его пересчитывать не нужно.
Приведем схему программы, реализующей этот алгоритм (функцию a(i, j) и значение “бесконечности” определять не будем):
for i:=1 to nn do
begin
l[i]= ¥;
b[i]:=false
end;
p:=s; l[s]:=0;
b[s]:=true;
f:=true;{cтоит ли искать дальше}
while (p<>t) and f do
begin
f:=false;
for i:=1 to nn do
if not b[i] then
if l[p]+a(p,i)<l[i] then l[i]:=l[p]+a(p,i);
min:=t;{важно, что b[t]=false}
for i:=1 to n do
if (not b[i])and(l[i]<l[min]) then min:=i;
if l[min]< ¥ then
begin
p:=min; b[p]:=true; f:=true
end
end;
Несложно подсчитать, что трудоемкость алгоритма составляет O(N2), что окупает некоторые сложности в его реализации. Как и в случае применения “волнового” алгоритма в невзвешенном графе, асимптотическая оценка не изменится если нам потребуется подсчитать длину пути от s до каждой из вершин графа. Поэтому, как и в алгоритме Флойда, длины кратчайших путей между всеми парами вершин могут быть рассчитаны за O(N3) операций.
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.
1. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.
2. Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.
3. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.
4. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.
5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
8. Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001.