Реферат: Динамическое программирование, алгоритмы на графах

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);