[стр.-49]
у:=хО; {Последняявершина с постоянной меткой) Mark[у]:=TRUE; Dist[у]:=0;
while not Mark[z] do begin
{Обновить временные метки)
for х:=0 to nX do if not Mark[x] and
( Dist[x]>Dist[y]+We[y,x] ) then begin
Dist[x]:=Dist[y]+We[y,x];
Prev[x]:=y; end;
{Поиск вершины с минимальной временной меткой) weight:=$7fffffff;
for x:=0 to nX do if not Markfx] then
if weight>Dist[x] then begin
weight:=Dist[x];
y:=x; end;
Markfy]:=TRUE; end;
Write(f,Вершины пути=);
x:=z;
while xoxO do begin Write(f,x:2); x:=Prev[x];
end;
WriteLn(f,x:2);
WriteLn(f,"Длина пути= \Dist[z]); Close (f); end.
Рассмотрим пример расчета по программе алгоритма поиска кратчайшего пути на графе, показанном на рис. 6.21. Исходные данные графа представляются матрицей весов его ребер в текстовом файле Short.in со следующей структурой:
•в первой строке определяется номер начальной вершины л;
•во второй строке определяется номер конечной вершины пути z,
•в третьей строке указывается количество пХвершин в графе;
•в следующихопределяются строки матрицы весов графа.
о
б
7
07
00
03
00
00
00 000
0 10
0 0
2 6
00
00
Результаты расчетов сохраняются в выходном файле Short.out со следующей структурой:
Вершины пути= Длина пути= 11.
6.10. Потоки в сетях
• Определение. Транспортной сетью называется связный ориентированный граф без петель Г= (X, U, Ф) с выделенной парой вершин ;с0 и z (рис. 6.22). Вершина х0 — начало транспортной сети, из которой дуги только выходят. Вершина z — конец транспортной сети, в которую дуги только входят. На множестве дуг и Uзадана целочисленная функция с(и) > О, где с(и) — пропускная способность дуги.
Рис. 6.22. Транспортная сеть
• Определение. Потоком по транспортной сети называется целочисленная функция0 , заданная на множестве дуг и и обладающая следующими свойствами:
VueU(tfu)uC(u) и £<р(и) = £ф(и),(6.10.1)
где х — внутренняя вершина графа, т.е. х*х$, х
—множество дуг, заходящих в вершину х;
—множество дуг, выходящих из вершины х (рис. 6.22).
0
1
Рис. 6.23. Разрез транспортной сети
С!, i = и) — называется мощностью разреза. Это максимально ueUA возможный поток, входящий в А по дугам разреза.
ф(/1) = ф(н) — поток, входящий в А по дугам разреза. Ясно, что и<=и+А у(А) < С(А), так как V« е U ф(и) < с(и).
• Утверждение 6.10.2. ф) < С(А).
Действительно, из рис. 6.23 видно, что не весь поток, входящий в А, скатывается в z. Часть потока может выходить из А. Значит,нотогда и
На рис. 6.22 напротив каждой дуги стоит дробь, числитель которой — пропускная способность дуги, знаменатель — поток по дуге. Свойство 1) утверждает, что поток, входящий в вершину, равен выходящему потоку (поток в вершинах не скапливается). Обозначим
где поток, входящий в вершину z\ ф(х0) — поток, выходящий из вершины х0.
•Утверждение 6.10.1. ф(г) =ф().
Действительно, сумма ]£[ £ф(н)- ]Гф(и)]=0, таккак V« € U
хеХ uel/*uid/~
величина ф(н) суммируется дважды — со знаками + и -. Здесь
1ГЕфИ-Х>(«И= X Цф<«)-1Ф<«)1+Ф(г)-ф(х0)=0,
xsXu&t <"&iхеХ\{хал) иеУ* ltd/:
где первая часть выражения равна нулю вследствие 6.10.1,
•Определение разреза. Пусть А сХ — множество вершин транспортной сети: л:0 g A, z е А. Обозначим через £Г$ множество дуг, входящих в А. Это множество дуг будем называть разрезом
транспортной сети.
