Вот решил выложить сразу чтоб ты не мучался...
Взято из Кормен, Лейзерсон, Ривест - "Алгоритмы: построение и анализ" и переведено на українську мову для моей квалификационной работы. Уж прости...
| Цитата |
Уявимо собі карту автомобільних шляхів України. Як знайти найкоротший шлях із Дніпропетровська в Київ? Можна, звичайно, перебрати всі можливі варіанти і вибрати мінімальний з них. Але тоді ми одержуємо мільйони свідомо невірних операцій (наприклад, навіщо нам їхати з Дніпропетровська в Київ через Донецьк, що знаходиться зовсім в іншому боці). Далі буде розглянутий спосіб ефективного рішення цієї задачі.
Тут буде розглядатися тільки пошук найкоротших шляхів з однієї вершини: даний зважений граф G і початкова вершина s. Потрібно знайти всі найкоротші шляхи з s в усі вершини графу. Алгоритм Дейкстри здатний знайти найкоротший шлях тільки для графів, у яких усі ребра недодатньої ваги.
Багато алгоритмів пошуку найкоротших шляхів використовують особливу техніку - техніку релаксації. І алгоритм Дейскстри - не виключення.
Техніка релаксації полягає в наступному. Для кожного ребра v ми зберігаємо деяке число d[v], яке є верхньою оцінкою ваги найкоротшого шляху з s в v. Початкове значення встановлюється наступною процедурою:
Inintialize-Single-Sourche(s)
1 for (для) всіх вершин v
2 do d[v]= MAX
3 parent[v]=NIL
Релаксація ребра (u,v) полягає в наступному: значення d[v] зменшується до d[u]+w(u,v) (якщо друге значення менше за перше).
Також можно змінити значення parent[v], щоб прослідити шлях, використаний при отриманні вищої оцінки.
Relax(u,v,w)
1 if d[v]> d[u]+w(u,v)
2 then d[v]=d[u]+w(u,v)
3 parent[v]=u
Алгоритм Дейкстри вирішує задачу пошуку найкоротшого шляху з однієї вершини для зваженого орієнтованого графа з початковою вершиною s, в якому ваги всіх ребер невід'ємні. В процесі роботи алгоритму підтримується множина S, що складається з вершин v, для яких знайдений найкоротший шлях. Алгоритм вибирає вершину u з якнайменшим d[u], додає її до множини S і проводить релаксацію всіх ребер, що виходять з u, після чого цикл повторюється.
Dijkstra(G,w,s)
1 Initialize-Single-Sourche(G,s)
2 S=NIL
3 Q=усі вершини графа
4 while Q<>NIL
5 do u=Extract-Min(Q)
6 S=S+{u}
7 for (для) всіх вершин v - нащадків u
8 do Relax(u,v,w)
|
И реализация на паскале... Моя.
| Код |
program dijkstra;
var
G:array[1..100,1..100] of integer; {матричное задание графа с максимум сто вершин, G[i,j] - стоимость переезда из i в j}
Q,W:array[1..100] of byte;
i,j:word;
s:word;
d:array[1..100] of word;
p:array[1..100] of word;
f:text;
n:word;
nQ:word;
nW:word;
min,mI:word;
begin
assign(f,'dijkstra.dat'); reset(f);
for i:=1 to 100 do
for j:=1 to 100 do
G[i,j]:=-1;
read(f,n); readln(f,s);
while not EOF(f) do
begin
read(f,i); read(f,j); readln(f,G[i,j]);
end;
close(f);
for i:=1 to n do
begin
d[i]:=65535;
p[i]:=0;
end;
d[s]:=0;
for i:=1 to n do
Q[i]:=i;
nq:=n; nW:=0;
while nq<>0 do
begin
min:=65535;
for i:=1 to n do
if (Q[i]<>0) and (d[i]<min) then
begin
min:=d[i]; mI:=i;
end;
dec(nQ);
Q[mI]:=0;
inc(nW); W[nW]:=mI;
for j:=1 TO n DO
if G[mi,j]<>-1 then
if d[j]>d[Mi]+G[Mi,j] then
begin
d[j]:=d[mi]+g[mi,j];
p[j]:=mi;
end;
end;
for i:=1 to n do
writeln(d[i]);
end.
|
|
