 |
Пути минимальной длины во взвешенном графе
|
|
|
|
Длиной пути между двумя вершинами во взвешенном графе называется сумма весов ребер, составляющих этот путь. В отличие от невзвешенного графа наличие ребра между двумя вершинами не гарантирует, что кратчайший путь между ними состоит из этого ребра. Зачастую суммарный вес пути, состоящего из двух, трех и более ребер может оказаться меньше веса одного ребра, поэтому даже для полного графа (то есть графа, между каждой из пар вершин которого существует ребро, а в случае ориентированного графа — два ребра, направленных в противоположные стороны) задача поиска кратчайших путей имеет смысл. Понятие кратчайшего пути пока будем рассматривать только для графов, все ребра которых имеют неотрицательный вес.
Наиболее просто найти кратчайший путь между каждой из пар вершин можно с помощью алгоритма Флойда [5 – 7], основанного на той же идее, что и алгоритм Уоршолла. Пусть в элементе матрицы A [ i, j ] хранится длина кратчайший пути из вершины i в вершину j, который проходит через некоторые вершины с номерами, не превосходящими k – 1. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j то таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить. То есть в реализации алгоритма Уоршолла следует заменить операцию and на “+”, а or — на нахождение минимума из двух величин. Для реализации алгоритма массив a первоначально следует заполнить элементами матрицы смежности, обозначая отсутствие ребра между двумя вершинами “бесконечностью” — числом, заведомо превосходящим длину любого пути в рассматриваемом графе, но меньшим, чем максимальное значение используемого типа данных, чтобы было возможно выполнять с ним арифметические операции. В этом случае можно избежать дополнительных проверок.
|
|
|
Если же нам требуется найти сам кратчайший путь, а не его длину, то при каждом улучшении пути между двумя вершинами мы в соответствующем элементе вспомогательного массива (в программе — w) будем запоминать номер той вершины, через которую кратчайший путь проходит, а затем с помощью элегантной рекурсивной процедуры будем его печатать. Идея рекурсии заключается в том, что если мы знаем, что кратчайший путь от вершины i до вершины j проходит через вершину k, то мы можем обратиться к той же самой процедуре с частями пути от i до k и от k до j. Рекурсивный спуск заканчивается, когда на кратчайшем пути между двумя вершинами не окажется промежуточных вершин.
Приведем фрагмент программы, реализующий алгоритм Флойда и печатающий кратчайшие пути между всеми парами вершин графа.
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 (N 2), что окупает некоторые сложности в его реализации. Как и в случае применения “волнового” алгоритма в невзвешенном графе, асимптотическая оценка не изменится если нам потребуется подсчитать длину пути от s до каждой из вершин графа. Поэтому, как и в алгоритме Флойда, длины кратчайших путей между всеми парами вершин могут быть рассчитаны за O (N 3) операций.
Заключение
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.
|
|
|
Литература
1. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.
2. Станкевич А. С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.
3. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.
4. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.
5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
8. Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001.
|
|
|
