Dijkstrov algoritmus je grafový algoritmus, ktorý nájde najkratšiu cestu medzi dvoma danými vrcholmi v grafe s nezápornými dĺžkami oblúkov. Často sa kladie aj úloha vypočítať najkratšiu cestu z daného vrcholu ku všetkým ostatným. Algoritmus je široko používaný v programovaní, napríklad ho používajú smerovacie protokoly.
Popis
Vstupom algoritmu je vážený orientovaný graf s oblúkmi nezápornej váhy. Výstupom je množina najkratších ciest z daného vrcholu k ostatným.
Na začiatku sa vzdialenosť pre počiatočný vrchol považuje za nulovú a vzdialenosti ku všetkým ostatným sa považujú za nekonečné. Pole príznakov označujúcich, či bol vrchol odovzdaný, je vyplnené nulami. Potom sa v každom kroku cyklu hľadá vrchol s minimálnou vzdialenosťou od počiatočného a príznakom rovným nule. Nastaví sa mu príznak a skontrolujú sa všetky susedné vrcholy. Ak je predtým vypočítaná vzdialenosť od zdrojového vrcholu k tomu, ktorý sa kontroluje, väčšia ako súčet vzdialenosti k aktuálnemu vrcholu a dĺžky hrany od neho k kontrolovanému vrcholu, potom sa vzdialenosť od kontrolovaného vrcholu rovná vzdialenosť k aktuálnemu + hrana od aktuálneho k kontrolovanému. Cyklus končí, keď sa príznaky všetkých vrcholov stanú rovnými 1, alebo keď je vzdialenosť ku všetkým vrcholom s príznakom 0 nekonečná. Posledný prípad je možný vtedy a len vtedy, ak je graf odpojený.
Dijkstrov algoritmus v pseudokóde
Vstup: OD: pole reálnych – matica dĺžok oblúkov grafu; s je vrchol, z ktorého sa hľadá najkratšia cesta a t je vrchol, do ktorého sa hľadá.
Výstup: vektory T: pole reálnych; a H: pole 0..r. Ak top v leží na najkratšej ceste z s do t, potom T[v]- najkratšia dĺžka cesty od s do y; No] - vrchol bezprostredne predchádzajúci pri na najkratšej ceste.
H je pole, v ktorom vrchol n zodpovedá vrcholu m, predchádzajúcemu na ceste k n od s.
T je pole, v ktorom vrchol n zodpovedá vzdialenosti od neho k s.
X je pole, v ktorom vrchol n zodpovedá 1, ak je známa cesta k nemu, a 0, ak nie.
inicializácia poľa:
pre v od 1 do R robiť
T[v]: = ∞ (neznáma skratka)
X[v]: = 0 (všetky vrcholy nie sú začiarknuté)
H[s]: = 0 ( s nič nepríde skôr)
T[s]:= 0 (najkratšia cesta má dĺžku 0...)
X[s]:= 1 ( ...a je známy ) v : = s (aktuálne top)
M: (aktualizácia poznámok)
pre a ∈ G( a) urobiť
ak X[i] = 0 & T[u]> T[v] + C potom
T[u]: = T[v] + C(našiel som kratšiu cestu z s v a cez v }
h[u]:= v(zapamätaj si to)
m: = ∞
v : = 0
(nájsť koniec najkratšej cesty)
pre a od 1 do p robiť
ak X[u] = 0 &T[u]< t potom
v:= u;
m:= T[u](vrchol v končí najkratšia cesta z s
ak v = 0 potom
zastaviť (žiadna cesta von s v t) koniec Ak
ak v= t potom
zastávka ( nájdená najkratšia cesta z s v t) koniec Ak
X[v]: = 1 ( nájdená najkratšia cesta z s v v ) ísť do M
Odôvodnenie
Na dôkaz správnosti Dijkstrovho algoritmu stačí poznamenať, že pre každé vykonanie tela slučky začínajúceho štítkom M, ako v používa sa vrchol, pre ktorý je známa najkratšia cesta z vrcholu s. Inými slovami, ak X[v] = 1, potom T[v] = d(s,v) , a všetky vrcholy na ceste (s, v) definovanej vektorom H majú rovnakú vlastnosť, t.j.
Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.
Vskutku (indukciou), prvýkrát ako v používa sa vrchol s, pre ktorý je najkratšia cesta prázdna a má dĺžku 0 (neprázdne cesty nemôžu byť kratšie, pretože dĺžky oblúkov sú nezáporné). Nech T[u] = d(s,u) pre všetky predtým označené vrcholy a. Zvážte novo označený vrchol v, ktorý je vybraný z podmienky T[v] = min T[u]. Všimnite si, že ak je známa cesta prechádzajúca označenými vrcholmi, potom je známa najkratšia cesta. Predpokladajme (naopak), že T[v] > d(s, v), teda nájdená cesta vedúca z s v v, nie je najkratšia. Potom musia byť na tejto ceste neoznačené vrcholy. Zvážte prvý vrchol w na tejto ceste tak, že T[w] = 0. Máme: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.
Časová zložitosť
Zložitosť Dijkstrovho algoritmu závisí od toho, ako nájsť nenavštívený vrchol s minimálnou vzdialenosťou od pôvodného, ako uložiť množinu nenavštívených vrcholov a ako aktualizovať štítky. Nech n je počet vrcholov a m je počet hrán v grafe. Potom, v najjednoduchšom prípade, keď sa vyhľadá celá množina vrcholov, aby sa našiel vrchol s minimálnou vzdialenosťou od pôvodného vrcholu, a na uloženie vzdialeností sa použije pole, čas chodu algoritmu je O(n 2) . Hlavná slučka sa vykoná asi n-krát, v každej z nich sa na nájdenie minima vynaloží asi n operácií. Cyklovanie cez susedov každého navštíveného vrcholu si vyžaduje množstvo operácií úmerných počtu hrán m (keďže každá hrana sa v týchto cykloch vyskytuje presne dvakrát a vyžaduje si konštantný počet operácií). Celková doba chodu algoritmu je teda O(n 2 + m), ale keďže m je oveľa menšie ako n (n-1), je to O(n 2).
V prípade riedkych grafov (t. j. tých, pre ktoré je m oveľa menšie ako n²), môžu byť nenavštívené vrcholy uložené v binárnej halde a hodnoty vzdialenosti sa používajú ako kľúč. Keďže cyklus sa vykoná približne n-krát a počet relaxácií (zmeny označenia) nie je väčší ako m, doba trvania takejto implementácie je O(nlogn+mlogn)
Príklad
Výpočet vzdialeností od vrcholu 1 pomocou prechodných vrcholov:
Zvážte príklad hľadania najkratšej cesty. Uvedená je sieť diaľnic spájajúcich regióny mesta. Niektoré cesty sú jednosmerné. Nájdite najkratšie cesty z centra mesta do každého mesta v okolí.
Na vyriešenie tohto problému môžete použiť Dijkstrov algoritmus- algoritmus na grafoch, ktorý v roku 1959 vynašiel holandský vedec E. Dijkstra. Nájde najkratšiu vzdialenosť od jedného z vrcholov grafu k všetkým ostatným. Funguje len pre grafy bez hrán so zápornou váhou.
Nech sa vyžaduje nájsť najkratšie vzdialenosti od 1. vrcholu ku všetkým ostatným.
Kruhy označujú vrcholy, čiary cesty medzi nimi (hrany grafu). Počty vrcholov sú uvedené v krúžkoch, ich hmotnosť je uvedená nad okrajmi - dĺžka cesty. Vedľa každého vrcholu je vyznačený červený štítok - dĺžka najkratšej cesty k tomuto vrcholu z vrcholu 1.
Označenie samotného vrcholu 1 sa považuje za 0, označenia zvyšných vrcholov sú nedosiahnuteľné veľké číslo(v ideálnom prípade - nekonečno). To odráža, že vzdialenosti od vrcholu 1 k iným vrcholom ešte nie sú známe. Všetky vrcholy grafu sú označené ako nenavštívené. 
Prvý krok
Minimálne označenie má vrchol 1. Jeho susedmi sú vrcholy 2, 3 a 6. Susedov vrcholu postupne obchádzame.
Prvým susedom vrcholu 1 je vrchol 2, pretože dĺžka cesty k nemu je minimálna. Dĺžka cesty k nemu cez vrchol 1 sa rovná súčtu najkratšej vzdialenosti k vrcholu 1, hodnote jeho označenia a dĺžke hrany idúcej od 1. do 2., teda 0 + 7 = 7. Toto je menej ako aktuálne označenie vrcholu 2 (10 000), takže nové označenie druhého vrcholu je 7. 
Podobne nájdeme dĺžky ciest pre všetkých ostatných susedov (vrcholy 3 a 6).
Všetci susedia uzla 1 sú skontrolovaní. Aktuálna minimálna vzdialenosť k vrcholu 1 sa považuje za konečnú a nepodlieha revízii. Vertex 1 je označený ako navštívený.
Druhý krok
Krok 1 algoritmu sa opakuje. Opäť nájdeme „najbližší“ z nenavštívených vrcholov. Toto je vrchol 2 označený ako 7.
Opäť sa pokúsime zmenšiť štítky susedov vybraného vrcholu a pokúsime sa cez ne prejsť cez 2. vrchol. Susedmi vrcholu 2 sú vrcholy 1, 3 a 4.
Vertex 1 už bol navštívený. Ďalším susedom vrcholu 2 je vrchol 3, pretože má minimálne označenie vrcholov označených ako nenavštívené. Ak na to pôjdete cez 2, tak dĺžka takejto cesty bude rovná 17 (7 + 10 = 17). Ale aktuálne označenie tretieho vrcholu je 9 a 9< 17, поэтому метка не меняется.
Ďalším susedom vrcholu 2 je vrchol 4. Ak k nemu prejdeme cez 2., tak dĺžka takejto cesty bude rovná 22 (7 + 15 = 22). Od 22<10000, устанавливаем метку вершины 4 равной 22.
Všetci susedia vrcholu 2 boli prezretí, takže ho označíme ako navštívený.
Tretí krok
Krok algoritmu zopakujeme výberom vrcholu 3. Po jeho „spracovaní“ dostaneme nasledovné výsledky. 
Štvrtý krok
Piaty krok
šiesty krok
Teda najkratšia cesta z vrcholu 1 do vrcholu 5 bude cesta cez vrcholy 1 — 3 — 6 — 5
, keďže týmto spôsobom získame váhu minimálne 20.
Poďme sa pozrieť na najkratšiu cestu. Poznáme dĺžku cesty pre každý vrchol a teraz zvážime vrcholy od konca. Zvážte konečný vrchol (v tomto prípade vrchol 5
), a pre všetky vrcholy, s ktorými je spojená, zistíme dĺžku cesty odpočítaním hmotnosti zodpovedajúcej hrany od dĺžky cesty konečného vrcholu.
Áno, top 5
má dĺžku cesty 20
. Je spojená s vrcholom 6
a 4
.
Pre vrchol 6
získať váhu 20 – 9 = 11 (zhoda).
Pre vrchol 4
získať váhu 20 - 6 = 14 (nezhoduje sa).
Ak v dôsledku toho dostaneme hodnotu, ktorá sa zhoduje s dĺžkou cesty príslušného vrcholu (v tomto prípade vrchol 6
), potom sa z neho urobil prechod do konečného vrcholu. Označíme tento vrchol na požadovanej ceste.
Ďalej určíme hranu, cez ktorú sme sa dostali do vrcholu 6
. A tak ďalej, kým sa nedostaneme na začiatok.
Ak v dôsledku takéhoto prechodu máme v určitom kroku rovnaké hodnoty pre niekoľko vrcholov, potom môžeme použiť ktorýkoľvek z nich - niekoľko ciest bude mať rovnakú dĺžku.
Implementácia Dijkstrovho algoritmu
Na uloženie váh grafu sa používa štvorcová matica. Vrcholy grafu sú v hlavičkách riadkov a stĺpcov. A váhy oblúkov grafu sú umiestnené vo vnútorných bunkách tabuľky. Graf neobsahuje slučky, takže hlavná uhlopriečka matice obsahuje nulové hodnoty.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Implementácia v C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define VEĽKOSŤ 6
int main()
{
int a; // matica spojení
int d; // minimálna vzdialenosť
intv; // navštívené vrcholy
int temp, miniindex, min;
int zaciatok_index = 0;
system("chcp 1251" );
system("cls" );
// Inicializácia matice vzťahov
pre (int i = 0; i
a[i][i] = 0;
for (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = teplota;
a[j][i] = teplota;
}
}
// Zobrazenie matice vzťahov
pre (int i = 0; i
pre (int j = 0; j
printf("\n");
}
//Inicializácia vrcholov a vzdialeností
pre (int i = 0; i
d[i] = 10 000;
v[i] = 1;
}
d = 0;
// Krok algoritmu
robiť (
minindex = 10000;
min = 10 000;
pre (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
miniindex=i;
}
}
// Pridajte nájdenú minimálnu hmotnosť
// na aktuálnu váhu vrcholu
// a porovnajte s aktuálnou minimálnou váhou vrcholu
if (minindex != 10000)
{
pre (int i = 0; i
ak (a[i] > 0)
{
teplota = min + a[i];
ak (tepl< d[i])
{
d[i] = teplota;
}
}
}
v = 0;
}
) zatiaľ čo (minindex< 10000);
// Zobrazenie najkratších vzdialeností k vrcholom
printf( "\nNajkratšie vzdialenosti k vrcholom: \n");
pre (int i = 0; i
// Obnoviť cestu
intver; // pole navštívených vrcholov
int end = 4; // index konca vrcholu = 5 - 1
ver = koniec + 1; // počiatočný prvok - koncový vrchol
int k = 1; // index predchádzajúceho vrcholu
int hmotnosť = d; // hmotnosť koncového vrcholu
while (end != begin_index) // kým nedosiahneme počiatočný vrchol
{
pre (int i = 0; i
ak (a[i] != 0) // ak existuje spojenie
{
int temp = hmotnosť - a[i]; // určí váhu cesty z predchádzajúceho vrcholu
if (teplota == d[i]) // ak sa hmotnosť zhoduje s vypočítanou
{ // to znamená, že došlo k prechodu z tohto vrcholu
hmotnosť = teplota; // uloženie novej hmotnosti
koniec = i; // uloženie predchádzajúceho vrcholu
ver[k] = i + 1; // a zapíšte ho do poľa
k++;
}
}
}
// Zobrazenie cesty (začiatočný vrchol je na konci poľa k prvkov)
printf( "\nNajkratšia cesta výstupu\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
návrat 0;
}
Výsledok popravy
Späť:
Daný je orientovaný alebo neorientovaný vážený graf s vrcholmi a hranami. Váhy všetkých hrán sú nezáporné. Je zadaný nejaký počiatočný vrchol. Je potrebné nájsť dĺžky najkratších ciest z vrcholu do všetkých ostatných vrcholov a tiež poskytnúť spôsob, ako vytlačiť samotné najkratšie cesty.
Tento problém sa nazýva problém s najkratšími cestami z jedného zdroja.
Algoritmus
Toto popisuje algoritmus navrhnutý holandským výskumníkom Dijkstra(Dijkstra) v roku 1959
Dostaneme pole, do ktorého pre každý vrchol uložíme aktuálnu dĺžku najkratšej cesty od do . Na začiatku a pre všetky ostatné vrcholy sa táto dĺžka rovná nekonečnu (pri implementácii na počítači sa zvyčajne zvolí dostatočne veľké číslo ako nekonečno, samozrejme väčšie ako možná dĺžka cesty):
Okrem toho pre každý vrchol uložíme, či je ešte označený alebo nie, t.j. získajme boolovské pole. Spočiatku sú všetky vrcholy neoznačené, t.j.
Samotný Dijkstrov algoritmus pozostáva z iterácií. V ďalšej iterácii sa vyberie vrchol s najmenšou hodnotou spomedzi tých, ktoré ešte neboli označené, t.j.:
(Je jasné, že pri prvej iterácii sa vyberie počiatočný vrchol.)
Takto vybraný vrchol sa označí ako označený. Ďalej, pri súčasnej iterácii, z vrcholu, relaxácia: všetky hrany vychádzajúce z vrcholu sú prehliadnuté a pre každý takýto vrchol sa algoritmus snaží zlepšiť hodnotu . Nech je dĺžka aktuálnej hrany , potom vo forme kódu relax vyzerá takto:
Tu aktuálna iterácia končí, algoritmus pokračuje k ďalšej iterácii (opäť sa vyberie vrchol s najmenšou hodnotou, z neho sa vykonajú relaxácie atď.). V tomto prípade sa nakoniec po iteráciách označia všetky vrcholy grafu a algoritmus dokončí svoju prácu. Tvrdí sa, že nájdené hodnoty sú požadované dĺžky najkratších ciest od do .
Stojí za zmienku, že ak nie sú všetky vrcholy grafu dosiahnuteľné z vrcholu, hodnoty pre ne zostanú nekonečné. Je jasné, že niekoľko posledných iterácií algoritmu vyberie len tieto vrcholy, ale tieto iterácie neprinesú žiadnu užitočnú prácu (keďže nekonečná vzdialenosť nemôže uvoľniť iné, dokonca nekonečné vzdialenosti). Preto je možné algoritmus okamžite zastaviť, akonáhle sa za zvolený vrchol považuje vrchol s nekonečnou vzdialenosťou.
Obnova cesty. Samozrejme, človek zvyčajne potrebuje poznať nielen dĺžky najkratších ciest, ale aj samotné cesty. Ukážme si, ako uložiť informácie dostatočné na následnú rekonštrukciu najkratšej cesty z akéhokoľvek vrcholu. Na to slúži tzv pole predkov: pole, ktoré obsahuje pre každý vrchol číslo vrcholu, ktorý je predposledný na najkratšej ceste k vrcholu. Toto využíva skutočnosť, že ak ideme najkratšou cestou k nejakému vrcholu a potom z tejto cesty odstránime posledný vrchol, dostaneme cestu končiacu v nejakom vrchole a táto cesta bude pre vrchol najkratšia. Takže, ak máme toto pole predkov, potom sa z neho dá obnoviť najkratšia cesta, jednoducho zakaždým, keď vezmeme predka z aktuálneho vrcholu, až kým sa nedostaneme do počiatočného vrcholu - takto dostaneme požadovanú najkratšiu cestu, ale zapísanú v opačné poradie. Takže najkratšia cesta na vrchol je:
Zostáva pochopiť, ako vybudovať toto pole predkov. To sa však robí veľmi jednoducho: pri každej úspešnej relaxácii, t.j. keď od vybraného vrcholu dôjde k zlepšeniu vzdialenosti k nejakému vrcholu, napíšeme, že predkom vrcholu je vrchol:
Dôkaz
Hlavné vyhlásenie, na ktorom je založená správnosť Dijkstrovho algoritmu, je nasledovná. Uvádza sa, že po označení akéhokoľvek vrcholu je aktuálna vzdialenosť k nemu už najkratšia, a preto sa už nebude meniť.
Dôkaz budeme vyrábať indukciou. Pre prvú iteráciu je jej platnosť zrejmá – pre vrchol máme , čo je dĺžka najkratšej cesty k nemu. Teraz nech toto tvrdenie platí pre všetky predchádzajúce iterácie, t.j. všetky už označené vrcholy; dokážme, že po vykonaní aktuálnej iterácie nie je porušená. Nech je vybraný vrchol pri aktuálnej iterácii, t.j. vrchol, ktorý algoritmus označí. Dokážme, že sa skutočne rovná dĺžke najkratšej cesty k nej (túto dĺžku označujeme ).
Zvážte najkratšiu cestu na vrchol. Je zrejmé, že túto cestu možno rozdeliť na dve cesty: pozostávajúcu iba z označených vrcholov (aspoň počiatočný vrchol bude v tejto ceste) a zvyšok cesty (môže zahŕňať aj označené vrcholy, ale vždy začína znakom neoznačený). Označte prvým vrcholom cesty a posledným vrcholom cesty.
Najprv dokážme naše tvrdenie pre vrchol , t.j. dokážme rovnosť. To je však takmer zrejmé: koniec koncov, pri jednej z predchádzajúcich iterácií sme si vybrali vrchol a vykonali z neho relaxáciu. Keďže (na základe samotného výberu vrcholu ) sa najkratšia cesta k rovná najkratšej ceste k plus hrana , potom keď sa vykoná relaxácia od, hodnota bude skutočne nastavená na požadovanú hodnotu.
Vzhľadom na nezápornosť nákladov hrán, dĺžka najkratšej cesty (ktorá sa podľa práve dokázaného rovná ) nepresahuje dĺžku najkratšej cesty k vrcholu . Ak vezmeme do úvahy, že (napokon Dijkstrov algoritmus nemohol nájsť kratšiu cestu, ako je všeobecne možné), v dôsledku toho dostaneme nasledujúce vzťahy:
Na druhej strane, keďže oba a a sú neoznačené vrcholy, keďže to bol vrchol, ktorý bol vybraný v aktuálnej iterácii, a nie vrchol , získame ďalšiu nerovnosť:
Z týchto dvoch nerovností vyvodíme rovnosť a potom z vyššie zistených vzťahov získame a:
Q.E.D.
Implementácia
Dijkstrov algoritmus teda pozostáva z iterácií, pri každej z nich sa vyberie neoznačený vrchol s najmenšou hodnotou, tento vrchol sa označí a potom sa prezrú všetky hrany vychádzajúce z tohto vrcholu a pozdĺž každej hrany sa urobí pokus o zlepšenie hodnotu na druhom konci okraja.
Doba chodu algoritmu je súčet:
Pri najjednoduchšej implementácii týchto operácií budú operácie vynaložené na nájdenie vrcholu a operácie na jednej relaxácii a konečnej asymptotiká algoritmus je:
Implementácia:
const int INF = 1000000000 ; int main() ( int n; ... čítať n ... vektor< vector < pair< int ,int >> > g(n); ... čítanie grafu... int s = ...; // počiatočný vrchol vektor< int >d(n, INF), p(n); d[s] = 0; vektor< char >u(n); pre (int i= 0; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }Tu je graf uložený vo forme zoznamov susediacich: pre každý vrchol obsahuje zoznam zoznam hrán vychádzajúcich z tohto vrcholu, t.j. zoznam dvojíc >, kde prvý prvok dvojice je vrchol, ku ktorému vedie hrana, a druhý prvok je váha hrany.
5.4.3. Problém najkratšej cesty a Dijkstrov algoritmus na jeho riešenie
Nech je uvedený digraf G(V,
E), ktorej každý oblúk má priradené číslo 
volal dĺžka oblúka.
Definícia. Dĺžka cesta je súčet dĺžok oblúkov, ktoré tvoria túto cestu. Problém najkratšej cesty dať takto.
Možnosť 1. Nájdite dĺžky najkratších ciest (cesty s minimálnou dĺžkou) a samotné cesty z pevného vrcholu s na všetky ostatné vrcholy grafu.
Možnosť 2. Nájdite dĺžky najkratších ciest a samotné cesty medzi všetkými pármi vrcholov v danom grafe.
Ak má graf oblúky zápornej dĺžky, problém nemusí mať riešenia (stratí svoj význam). Je to spôsobené tým, že graf môže obsahovať obrys zápornej dĺžky. Prítomnosť obrysov zápornej dĺžky znamená, že dĺžka cesty sa môže rovnať 
. A ak neexistujú žiadne obrysy zápornej dĺžky, potom existujú najkratšie cesty a každá najkratšia cesta je jednoduchý reťazec.
Všimnite si, že ak existuje najkratšia cesta, potom ktorákoľvek z jej čiastkových ciest je zároveň najkratšou cestou medzi zodpovedajúcimi vrcholmi.
Dijkstrov algoritmus na riešenie problému najkratšej cesty.
Algoritmus pracuje s oblúkmi kladnej dĺžky a určuje najkratšie cesty z pevného vrcholu s na všetky ostatné vrcholy grafu. Označme tieto vrcholy v 1 , v 2 ,…, v n .
Definícia. Nazvime vrchol u ležiace bližšie k vrcholu s než top v ak je dĺžka najkratšej cesty z s predtým u menšia ako je dĺžka najkratšej cesty z s predtým v. Povieme, že vrcholy u a v v rovnakej vzdialenosti z vrchu s, ak sú dĺžky najkratších ciest z s predtým u a od s predtým v zápas.
Dijkstrov algoritmus postupne zoraďuje vrcholy grafu z hľadiska blízkosti k vrcholu s a je založená na nasledujúcich základných princípoch.
Ak sú dĺžky oblúkov kladné čísla, potom
najbližšie k s vrchol je ona sama. Dĺžka najkratšej cesty z s predtým s je 0;
najbližšie k s vrchol iný ako s, klame z s vo vzdialenosti jedného oblúka - najkratší zo všetkých oblúkov vychádzajúcich z vrcholu s;
akýkoľvek stredný vrchol najkratšej cesty z s až po nejaký vrchol v leží bližšie s než koncový vrchol v;
najkratšia cesta k ďalšiemu usporiadanému vrcholu môže prechádzať len cez už usporiadané vrcholy.
Nech už algoritmus usporiadal vrcholy v 1 ,
v 2 …
v k .
Označiť podľa 
,
dĺžka najkratšej cesty na vrchol v i .
Zvážte všetky oblúky pôvodného grafu, ktoré začínajú v jednom z vrcholov množiny 
a končí v ešte neusporiadaných vrcholoch. Za každý takýto oblúk napr 
, vypočítajte súčet 
. Tento súčet sa rovná dĺžke cesty z s
v r, v ktorom je vrchol v i je predposledný vrchol a cesta z s
v v i je najkratšia zo všetkých spojovacích ciest s
a v i .
To určuje dĺžky všetkých ciest z s do ešte neusporiadaných vrcholov, v ktorých sú iba vrcholy spomedzi medziľahlých vrcholov k najbližšie k s. Najkratšia z týchto ciest nech končí hore w. Potom w a jesť 
blízko s vrchol.
Technicky sa akcie podľa Dijkstrovho algoritmu vykonávajú pomocou aparátu značiek vrcholov. Vertex Label v označené ako 
. Každý štítok je číslo, ktoré sa rovná dĺžke nejakej cesty z s
predtým v. Štítky sa delia na dočasné a trvalé. V každom kroku sa iba jeden štítok stane trvalým. To znamená, že jeho hodnota sa rovná dĺžke najkratšej cesty k príslušnému vrcholu a tento samotný vrchol je usporiadaný. Číslo nasledujúceho usporiadaného vrcholu je označené písmenom R.
Popis algoritmu.
Krok 1. (počiatočné nastavenie). Dajte 
a toto označenie považovať za trvalé. Dajte 
,
a považovať tieto označenia za dočasné. Dajte 
.
Krok 2 (všeobecný krok). Opakuje sa n krát, kým nie sú zoradené všetky vrcholy grafu.
Prepočítať časovú pečiatku 
akýkoľvek neusporiadaný vrchol v i, ktorý zahŕňa oblúk opúšťajúci vrchol R, podľa pravidla
Vyberte vrchol s minimálnou časovou pečiatkou. Ak existuje niekoľko takýchto vrcholov, vyberte ľubovoľný.
Nechaj w-
vrchol s minimálnou časovou značkou. Prečítajte si štítok 
konštantný a dať 
.
Je vhodné usporiadať kroky Dijkstrovho algoritmu do tabuľky, ktorej každý stĺpec zodpovedá vrcholu grafu. Riadky tabuľky zodpovedajú opakovaniu spoločného kroku.
Príklad.
Pre graf na obr. 4. nájdite najkratšie cesty z vrcholov 
na všetky ostatné vrcholy grafu. Hrany znamenajú dva rôzne smerované oblúky rovnakej dĺžky.
Riešenie. V tabuľke. V každom kroku sa zapíše 1 štítok vrcholov. Trvalé značky sú označené znamienkom „+“. Poďme si podrobne popísať, ako sa počítajú štítky vrcholov.
Z vrcholu 1 vychádzajú oblúky do vrcholov 2, 5, 6. Prepočítajte označenia týchto vrcholov a vyplňte druhý riadok tabuľky.
Vertex label 6 sa stáva trvalým, 
.
Od vrcholu 6 smerujú oblúky k stále neusporiadaným vrcholom 2, 5, 8, 9. Prepočítajte ich časové značky
Vyplňte riadok 3 tabuľky. Minimálny počet časových pečiatok je 3 (vertex label 9), 
.
Z vrcholu 9 vychádzajú oblúky do ešte neusporiadaných vrcholov 5, 8, 11, 12. Potom
Vyplňte štvrtý riadok tabuľky. V tomto riadku majú dva vrcholy - 2 a 12 minimálne časové značky rovné 4. Najprv zoraďme napríklad vrchol 2. Potom v ďalšom kroku zoradí vrchol 12.
stôl 1
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
.
Z vrcholu 2 idú oblúky do ešte neusporiadaných vrcholov 3, 4, 5. Prepočítajte časové značky týchto vrcholov
Vyplňte riadok 5 tabuľky. Minimálny počet časových pečiatok je 4 (vertex label 12), 
.
Vyplňte riadok 6 tabuľky. Minimálny počet časových pečiatok je 5 (vertex label 5), 
.
Vyplňte riadok 7 tabuľky. Vertex label 8 sa stane konštantným (rovná sa 5), 
.
Vertex 11 je objednaný.
Z vrcholu 11 idú oblúky do neusporiadaných vrcholov 7, 10. Prepočítajte časové značky týchto vrcholov
Vertex 4 dostane trvalé označenie.
Z vrcholu 4 vychádzajú oblúky do neusporiadaných vrcholov 3, 7. Prepočítať časové značky
Usporiadať horné 3.
Vyplňte riadok 12 tabuľky. V tomto kroku zoradíme posledný neusporiadaný vrchol 10.
Stavanie stromu najkratších ciest.
Strom najkratšej cesty je nasmerovaný strom zakorenený vo vrchole. S . Všetky cesty v tomto strome sú najkratšie cesty pre tento graf.
Strom najkratšej cesty je zostavený podľa tabuľky, vrchol po vrchole je v ňom zahrnutý v poradí, v akom dostali trvalé štítky. Koreň je prvým uzlom zahrnutým do stromu. S .
Postavme si strom najkratších ciest pre náš príklad.
Najprv do stromu zahrnieme koreň, vrchol 1. Potom je do stromu zahrnutý oblúk (1,6). Ďalej bol zoradený vrchol 9, ktorého dĺžka najkratšej cesty sa rovná 3. Prvýkrát sa číslo 3 objavilo v treťom rade, ktorý bol vyplnený 
. Preto je vrchol 6 predposledným vrcholom najkratšej cesty k vrcholu 9. Oblúk (6,9) dĺžky 1 zahrnieme do stromu.
Potom bol vrchol 2 zoradený s najkratšou dĺžkou cesty rovnajúcou sa 4. Toto číslo sa prvýkrát objavilo v treťom riadku, ktorý bol vyplnený 
. Následne najkratšia cesta k druhému vrcholu prechádza pozdĺž oblúka (6,2). Oblúk (6,2) dĺžky 2 zahrnieme do stromu.
Ďalej bol objednaný vrchol 12, 
. Prvýkrát sa vo štvrtom riadku objaví číslo 4, ktoré bolo vyplnené kedy 
. V strome je zahrnutý oblúk (9,12) dĺžky 1. Kompletný strom najkratších ciest je znázornený na obr. 5.
Dijkstrov algoritmus môže zlyhať, ak má graf oblúky zápornej dĺžky. Takže hľadať najkratšie cesty z vrcholu s =1 pre graf na obr. 6, algoritmus najprv usporiada uzol 3, potom uzol 2 a skončí. Navyše táto najkratšia cesta k vrcholu 3 je z pohľadu Dijkstrovho algoritmu oblúk (1,3) dĺžky 3.
V skutočnosti najkratšia cesta k vrcholu 3 pozostáva z oblúkov (1,2) a (2,3), dĺžka tejto cesty je 5+(-3)=2.
V dôsledku prítomnosti oblúka (2,3) zápornej dĺžky –3 boli porušené tieto základné princípy:
najbližšie k s vrchol leží vo vzdialenosti dvoch oblúkov od neho a nie jedného;
stredný vrchol najkratšej cesty 1-2-3 (vrchol 2) leží ďalej od vrcholu 1 (vzdialenosť 5) ako konečný vrchol cesty 3.
Prítomnosť oblúkov zápornej dĺžky preto komplikuje riešenie problému s najkratšou cestou a vyžaduje použitie zložitejších algoritmov ako je Dijkstrov algoritmus.
Z množstva algoritmov na nájdenie najkratších trás v grafe som na Habrém našiel len popis Floyd-Warshallovho algoritmu. Tento algoritmus nájde najkratšie cesty medzi všetkými vrcholmi grafu a ich dĺžku. V tomto článku popíšem princíp fungovania Dijkstrovho algoritmu, ktorý nájde optimálne trasy a ich dĺžku medzi jedným konkrétnym vrcholom (zdrojom) a všetkými ostatnými vrcholmi grafu. Nevýhodou tohto algoritmu je, že nebude fungovať správne, ak má graf oblúky so zápornou hmotnosťou.
Vezmime si napríklad nasledujúci orientovaný graf G:
Tento graf môžeme znázorniť ako maticu C:
Zoberme si ako zdroj vrchol 1. To znamená, že budeme hľadať najkratšie cesty z vrcholu 1 k vrcholom 2, 3, 4 a 5.
Tento algoritmus krok za krokom iteruje cez všetky vrcholy grafu a priraďuje im označenia, ktoré predstavujú známu minimálnu vzdialenosť od zdrojového vrcholu ku konkrétnemu vrcholu. Pozrime sa na tento algoritmus na príklade.
Priraďme 1. vrcholu označenie rovné 0, pretože tento vrchol je zdrojom. Zvyšným vrcholom budú priradené štítky rovné nekonečnu.
Ďalej si vyberieme vrchol W, ktorý má minimálnu značku (teraz je to vrchol 1) a zvážime všetky vrcholy, ku ktorým z vrcholu W vedie cesta, ktorá neobsahuje vrcholy mediátora. Každému z uvažovaných vrcholov priradíme označenie rovnajúce sa súčtu označenia W a dĺžky ciest z W k uvažovanému vrcholu, ale iba ak je výsledný súčet menší ako predchádzajúca hodnota označenia. Ak množstvo nie je menšie, tak predchádzajúci štítok necháme nezmenený.
Po zvážení všetkých vrcholov, ku ktorým vedie priama cesta z W, označíme vrchol W ako navštívený a z tých ešte nenavštívených vyberieme ten, ktorý má minimálnu hodnotu označenia, bude to nasledujúci vrchol W. V v tomto prípade ide o vrchol 2 alebo 5. Ak existuje niekoľko vrcholov s rovnakými štítkami, potom nezáleží na tom, ktorý z nich zvolíme ako W.
Vyberieme si vrchol 2. Ale nevedie z neho žiadna odchádzajúca cesta, takže tento vrchol hneď označíme ako navštívený a prejdeme na ďalší vrchol s minimálnou značkou. Tentoraz má minimálny štítok iba vrchol 5. Zvážte všetky vrcholy, ku ktorým vedú priame cesty z 5, ale ktoré ešte neboli označené ako navštívené. Opäť nájdeme súčet označenia vrcholu W a hmotnosti hrany od W k aktuálnemu vrcholu a ak je tento súčet menší ako predchádzajúci štítok, nahradíme hodnotu označenia výsledným súčtom.
Na základe obrázku vidíme, že štítky 3. a 4. vrcholu sa zmenšili, to znamená, že k týmto vrcholom sa našla kratšia cesta zo zdrojového vrcholu. Ďalej označte 5. vrchol ako navštívený a vyberte ďalší vrchol, ktorý má označenie minima. Všetky vyššie uvedené akcie opakujeme, pokiaľ existujú nenavštívené vrcholy.
Po dokončení všetkých krokov dostaneme nasledujúci výsledok:
Nechýba ani vektor P, na základe ktorého sa dajú postaviť najkratšie trasy. Počtom prvkov sa tento vektor rovná počtu vrcholov v grafe. Každý prvok obsahuje posledný stredný vrchol na najkratšej ceste medzi zdrojovým vrcholom a konečným vrcholom. Na začiatku algoritmu sú všetky prvky vektora P rovné zdrojovému vrcholu (v našom prípade P = (1, 1, 1, 1, 1)). Ďalej, v štádiu prepočítavania hodnoty návestia pre uvažovaný vrchol, ak sa návestie uvažovaného vrcholu zmení na menšie, zapíšeme do poľa P hodnotu aktuálneho vrcholu W. Napríklad: 3. vrchol mal štítok s hodnotou "30", s W=1. Ďalej pri W=5 sa označenie 3. vrcholu zmenilo na "20", preto hodnotu zapíšeme do vektora P - P=5. Taktiež pri W=5 sa zmenila hodnota označenia na 4. vrchole (bolo to „50“, zmenilo sa na „40“), takže hodnotu W – P=5 musíte priradiť 4. prvku vektor P. V dôsledku toho dostaneme vektor Р = (1, 1, 5, 5, 1).
Keď vieme, že každý prvok vektora P obsahuje posledný stredný vrchol na ceste medzi zdrojom a konečným vrcholom, môžeme získať samotnú najkratšiu cestu.