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äť:
Dijkstrov algoritmus je grafový algoritmus, ktorý vynašiel holandský vedec E. Dijkstra v roku 1959. Nájde najkratšiu vzdialenosť od jedného z vrcholov grafu ku všetkým ostatným. Algoritmus funguje iba pre grafy bez hrán so zápornou váhou. Algoritmus je široko používaný v programovaní a technológiách, ako je OSPF, ho používa na elimináciu trás spätnej slučky, známych aj ako najkratšia cesta ako prvá.
Dijkstrov algoritmus rieši problém najkratšej cesty s jedným vrcholom pre vážený orientovaný graf G = (V, E) s počiatočnými vrcholmi s, v ktorých sú váhy všetkých hrán nezáporné ((u, v) ? 0 pre všetky (u , v) E). V prípade, že okraje grafu nie sú rovnaké, je vhodné použiť tento algoritmus.
Formulácia úlohy. Existuje graf. Niektoré jeho vrcholy sú označené ako vrchol 1. Je potrebné nájsť minimálne cesty z vrcholu 1 ku každému z vrcholov grafu. Minimálna cesta je cesta s minimálnym súčtom cien pozdĺž cesty. Cena je nezáporné číslo, ktoré je hmotnosťou hrany.
Myšlienka algoritmu. Myšlienka je založená na nasledujúcom zrejmom vyhlásení: Nech minimálna cesta z vrcholu a k vrcholu B. A nech je vrchol B spojený s nejakým počtom vrcholov i . Označme C i náklady na cestu z vrcholu B do vrcholu i. Vyberme minimálnu hodnotu z C i. Potom bude minimálne pokračovanie cesty z bodu B prechádzať zvolenou hodnotou.
Toto vyhlásenie skutočne nevyžaduje dôkaz. A z toho vyplýva veľmi vážny dôsledok. Nech existuje množina vrcholov, cez ktoré už prechádzajú minimálne cesty. Takáto množina zaručene existuje, ide o vrchol 1. Vyššie formulované tvrdenie umožňuje pridať k už existujúcej množine vrcholov (ďalej ich budeme nazývať vybrané) ešte jeden vrchol a keďže počet vrcholov v grafe je konečný, potom sa v konečnom počte krokov vyberú všetky vrcholy grafu a toto bude riešenie.
Podstatou Dijkstrovho algoritmu je postup pridania ďalšieho vrcholu do množiny vybraných. Tento postup pozostáva z dvoch krokov:
1. Zostavíme množinu vrcholov priliehajúcich k vybranému a nájdeme medzi nimi vrchol s najnižšou cenou. Nájdený vrchol sa pridá do množiny vybraných.
2. Zostrojíme množinu vrcholov priliehajúcich k vybranému a určíme pre ne nové ceny. Nová cena vrcholu je minimálna cena cesty z množiny vybraných vrcholov k danému vrcholu. Nová cena je zostavená takto:
a. Pre nevybraný vrchol v množine vybraných vrcholov sa určí podmnožina vrcholov, ktoré s týmto vrcholom spadajú.
b. Pre každý vrchol vybranej podmnožiny sa určí cena cesty k danému.
c. Stanoví sa minimálna cena. Táto cena sa stáva najvyššou cenou.
Algoritmus pracuje s dvoma typmi cien: okrajovou cenou a najvyššou cenou. Okrajové ceny sú konštantné. Ceny špičiek sa neustále prepočítavajú. Význam týchto cien je iný. Náklady na hranu sú náklady na presun z vrcholu do vrcholu spojeného touto hranou. A cena vrcholu je cena minimálnej cesty. Ďalšia dôležitá poznámka sa týka prepočtu predbežných cien. V skutočnosti má zmysel prepočítavať predbežné ceny len pre tie vrcholy, ktoré sú spojené s vrcholom pridaným do množiny vybraných v poslednom kroku, keďže pre ostatné vrcholy nie je dôvod meniť predbežnú cenu.
Je známe, že všetky ceny (napríklad položenie cesty alebo prechodu) sú nezáporné. Nájdite cestu s najnižšou cenou 1->i pre všetky i=1. n v čase O(n2).
Počas činnosti algoritmu sa vyberú niektoré mestá (na začiatku - iba mesto 1, na konci - všetky). kde:
pre každé vybrané mesto i sa uloží najnižšia cena cesty 1->i; zároveň je známe, že minimum sa dosahuje na ceste prechádzajúcej len vybranými mestami;
pre každé nepridelené mesto i je uložená najnižšia cena cesty 1->i, v ktorej sa ako medziľahlé používajú iba vybrané mestá.
Súbor pridelených miest je rozšírený na základe nasledujúcej poznámky: ak zo všetkých nepridelených miest vezmeme to, pre ktoré je uložené číslo minimálne, potom toto číslo predstavuje skutočne najnižšiu cenu. Naozaj, nech existuje kratšia cesta. Zvážte prvé nevybrané mesto na tejto ceste - cesta k nemu je už dlhšia! (Negatívnosť cien je tu nevyhnutná.)
Pridaním vybraného mesta k vybraným musíme opraviť informácie uložené pre nevybrané mestá. V tomto prípade stačí vziať do úvahy len cesty, v ktorých je nové mesto posledným prestupným bodom, a to je jednoduché, keďže už poznáme minimálne náklady na cestu do nového mesta.
Inými slovami, každý vrchol z V je spojený s označením - minimálna známa vzdialenosť od tohto vrcholu k a. Algoritmus pracuje krok za krokom – pri každom kroku „navštívi“ jeden vrchol a snaží sa zmenšiť štítky. Algoritmus končí, keď sú navštívené všetky vrcholy.
Inicializácia. Vrchný štítok a sa má rovnať 0 , označenia zostávajúcich vrcholov sú nekonečné. To odráža vzdialenosť od a na ďalšie vrcholy sú zatiaľ neznáme. Všetky vrcholy grafu sú označené ako nenavštívené.
Krok algoritmu. Ak boli navštívené všetky vrcholy, algoritmus sa ukončí. V opačnom prípade sa vrchol vyberie z vrcholov, ktoré ešte neboli navštívené u S minimálnym štítkom. Zvažujeme všetky možné cesty, v ktorých u je predposledný bod. Vrcholy spojené s vrcholom u hrany, budeme nazývať susedov tohto vrcholu. Pre každého suseda zvážte novú dĺžku cesty rovnajúcu sa súčtu aktuálneho označenia u a dĺžka okrajového spojenia u s týmto susedom. Ak je výsledná dĺžka menšia ako štítok suseda, nahraďte štítok touto dĺžkou. Po zvážení všetkých susedov označíme vrchol u ako ste navštívili a zopakujte krok.
Keďže Dijkstrov algoritmus si zakaždým zvolí spracovanie vrcholu s najmenším odhadom najkratšej cesty, môžeme povedať, že patrí medzi chamtivé algoritmy.
Poďme si podrobnejšie popísať, ako funguje Dijkstrov algoritmus.
Algoritmus používa tri polia N (= počet vrcholov siete) čísel v každom. Prvé pole A obsahuje návestia s dvoma hodnotami: 0 (vrchol ešte nie je uvažovaný) a 1 (vrchol sa už uvažuje); druhé pole B obsahuje vzdialenosti - aktuálne najkratšie vzdialenosti od k príslušnému vrcholu; tretie pole c obsahuje počty vrcholov - k-tý prvok C [k] je číslo predposledného vrcholu na aktuálnej najkratšej ceste z Vi do Vk. Matica vzdialenosti D udáva dĺžku oblúka D; ak takýto oblúk neexistuje, potom D je priradené veľké číslo B, ktoré sa rovná "nekonečnosti stroja".
Teraz môžeme popísať:
1. (inicializácia). V cykle od 1 do N vyplňte pole A nulami; vyplniť pole C číslom i; presuňte i-tý riadok matice D do poľa B, A [i]: =1; C [i]: =0 (i - počiatočné číslo vrcholu)
2. (všeobecný krok). Nájdite minimum medzi neoznačenými (teda tými k, pre ktoré A [k] = 0); minimum nech sa dosiahne pri indexe j, t.j. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , potom (B [k]: =B [j] +D ; C [k]: =j) (Podmienka znamená, že cesta Vi. Vk je dlhšia ako cesta Vi. Vj Vk) . (Ak sú označené všetky A [k], potom sa dĺžka cesty z Vi do Vk rovná B [k]. Teraz musíme) vyčísliť vrcholy zahrnuté v najkratšej ceste).
3. (vydanie odpovede). (Cesta z Vi do Vk sa vráti v opačnom poradí nasledujúcim postupom:)
2. Vydanie z;
3. z:=C[z]. Ak z = 0, potom ukončite, inak prejdite na 3.2.
Na vykonanie algoritmu je potrebné naskenovať pole B z N prvkov N-krát, t.j. Dijkstrov algoritmus má kvadratickú zložitosť: O(n2).
Nižšie je bloková schéma Dijkstrovho algoritmu (pozri obr. 2).
Obr.2. Vývojový diagram Dijkstrovho algoritmu
Na začiatku algoritmu sa predpokladá, že vzdialenosť pre počiatočný vrchol je nula a všetky ostatné vzdialenosti sú vyplnené veľkým kladným číslom (väčším ako je maximálna možná cesta v grafe). Pole príznakov je vyplnené nulami. Potom sa spustí hlavná slučka.
V každom kroku slučky hľadáme vrchol s minimálnou vzdialenosťou a príznakom rovným nule. Potom v ňom nastavíme vlajku na 1 a skontrolujeme všetky priľahlé vrcholy. Ak je vzdialenosť v nej väčšia ako súčet vzdialenosti k aktuálnemu vrcholu a dĺžky hrany, tak ju zmenšíme. Cyklus končí, keď sa príznaky všetkých vrcholov rovnajú 1.
Do každého mesta regiónu (ak sa môžete pohybovať len po cestách).
Možnosť 2. Existuje množstvo letov medzi mestami sveta, pre každé je známa cena. Cena letu z A do B sa nemusí rovnať nákladom na let z B do A. Nájdite trasu s minimálnymi nákladmi (prípadne s prestupmi) z Kodane do Barnaul.
Formálna definícia
Príklad
Zvážte vykonanie algoritmu na príklade grafu znázorneného na obrázku.
Nech sa vyžaduje nájsť najkratšie vzdialenosti od 1. vrcholu ku všetkým ostatným.
Implementácie v programovacích jazykoch
Vyhotovenie v jazyku C (C).
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // matica cesty ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 1 , 2 , 3 , 4 , 5 , 6 ), // horizontálne indexy od bodu { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // vertikálne do bodu, hodnota - váha int d[ VEĽKOSŤ]; // pole nájdených najkratších ciest, indexy - vrcholy grafu void deikstra () ( int v [ SIZE ]; // pole označení int temp , i ; int miniindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // pole ciest inicializovaných do nekonečna v[i] = 1; ) d[0] = 0; robiť ( // spustenie algoritmu minindex = INF ; min = INF; pre (i = 0; i< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( teplota = min + a [ miniindex ][ i ]; if (tepl< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
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 . Spoč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 vždy, 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 jasné, ž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 s neoznačeným). 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 (kvôli samotnému 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.
) beží v čase O(m + n \ln n) a je asymptoticky najrýchlejším známym sekvenčným algoritmom pre túto triedu problémov.
1.2 Matematický popis algoritmu
Nech je daný graf G = (V, E) s váhami hrán f(e) a rozlíšeným zdrojovým vrcholom u . Označme d(v) najkratšiu vzdialenosť od zdroja u k vrcholu v .
Nech sú už vypočítané všetky vzdialenosti nepresahujúce určité číslo r, teda vzdialenosti k vrcholom z množiny V_r = \( v \in V \mid d(v) \le r \). Nechaj
(v, w) \in \arg\min \( d(v) + f(e) \mid v \in V, e = (v, w) \in E \).Potom d(w) = d(v) + f(e), a v leží na najkratšej ceste z u do w .
množstvá d^+(w) = d(v) + f(e), kde v \in V_r , e = (v, w) \in E , sa nazývajú odhadované vzdialenosti a sú hornou hranicou pre skutočné vzdialenosti: d(w) \le d^+(w) .
Dijkstrov algoritmus v každom kroku nájde vrchol s najmenšou odhadovanou vzdialenosťou, označí ho ako navštívený a aktualizuje odhadované vzdialenosti pre všetky koncové body hrán, ktoré z neho vychádzajú.
1.3 Výpočtové jadro algoritmu
Hlavné výpočty súvisia s operáciami v prioritnom fronte:
- extrahovanie minimálneho prvku (delete_min);
- znížiť prioritu prvku (decrease_key).
1.4 Makroštruktúra algoritmu
Pseudokód algoritmu:
Vstupné Data: graf s vrcholmi V, okraje E so šupinami f(e); zdrojový uzol u. Výkon: vzdialenosti d(v) do každého vrcholu v ∈ V z vrchu u. Q := Nový prioritný rad pre každý v ∈ V: ak v = u potom d(v) := 0 inak d(v) := ∞ Q.insert( v, d(v)) zatiaľ čo Q ≠ ∅: v := Q.delete_min() pre každý e = (v, w) ∈ E: ak d(w) > d(v) + f(e): d(w) := d(v) + f(e) Q.decrease_key( w, d(w))1.5 Schéma implementácie sekvenčného algoritmu
Konkrétna implementácia Dijkstrovho algoritmu je určená výberom použitého prioritného algoritmu fronty. V najjednoduchšom prípade to môže byť pole alebo zoznam, pričom hľadanie minima vyžaduje zobrazenie všetkých vrcholov. Efektívnejšie je použiť haldu; najznámejší odhad zložitosti je pre variant využívajúci Fibonacciho haldu.
Možnosť implementácie je možná, keď sú vrcholy pridané do frontu nie vo fáze inicializácie, ale v čase prvej návštevy.
1.6 Sekvenčná zložitosť algoritmu
Sekvenčná zložitosť algoritmu je O(C_1 m + C_2n), kde
- C_1 – počet operácií na zníženie vzdialenosti k vrcholu;
- C_2 je počet operácií na výpočet minima.
Pôvodný Dijkstrov algoritmus používal zoznamy ako vnútornú dátovú štruktúru, pre ktorú C_1 = O(1) , C_2 = O(n) , takže celková zložitosť bola O(n^2) .
Pri použití Fibonacciho haldy sa minimálny čas výpočtu zníži na C_2 = O(\ln n) , takže celková zložitosť je O(m + n \ln n) , čo je asymptoticky najznámejší výsledok pre túto triedu problémov.
1.7 Informačný graf
Pre základnú implementáciu Dijkstrovho algoritmu na zoznamoch alebo poliach je uvedený graf algoritmu.
Obrázok 1. Graf algoritmu bez zobrazenia vstupných a výstupných údajov. n=3. Operácie porovnávania sú označené žltou farbou, operácie zmeny návestí vrcholov sú označené zelenou farbou a označovanie vrcholov modrou farbou.
1.8 Zdroj paralelného algoritmu
Dijkstrov algoritmus umožňuje efektívnu paralelizáciu, priemerný čas chodu O(n^(1/3)\ln n) s výpočtovým objemom O(n \ln n + m) .
Prvý odhad je založený na charakteristike daps, ktorá meria počet prístupov do pamäte (čítanie a zápis) uskutočnených za sekundu. Táto charakteristika je analogická s odhadom flops vo vzťahu k práci s pamäťou a je skôr odhadom výkonu interakcie s pamäťou ako odhadom lokality. Slúži však ako dobrý zdroj informácií vrátane porovnania s výsledkami pre nasledujúcu funkciu cvg.
Obrázok 6 zobrazuje hodnoty daps pre implementácie bežných algoritmov zoradené vo vzostupnom poradí (čím viac daps, tým lepší výkon vo všeobecnosti). Môžete vidieť, že výkon pamäte je dosť nízky. To nie je prekvapujúce, pretože implementácie algoritmov nad grafmi majú takmer vždy nízku efektivitu v dôsledku nepravidelnosti prístupu k údajom, čo sme videli pri analýze profilu prístupu.
Obrázok 6. Porovnanie hodnôt skóre daps
Druhá charakteristika, cvg, má poskytnúť odhad lokality viac nezávislý od stroja. Určuje, ako často potrebuje program sťahovať údaje do vyrovnávacej pamäte. V súlade s tým, čím menšia je hodnota cvg, tým menej často to treba robiť, tým lepšia je lokalita.
Obrázok 7 zobrazuje hodnoty cvg pre rovnakú množinu implementácií zoradené v zostupnom poradí (čím menšie je cvg, tým vyššia je lokalita vo všeobecnosti). Je vidieť, že v tomto prípade hodnota cvg dobre koreluje s výkonnostným skóre a odráža nízku lokalitu, čo je v súlade so zisteniami kvalitatívneho hodnotenia lokality.
Obrázok 7. Porovnanie hodnôt skóre cvg
2.3 Možné metódy a vlastnosti paralelnej implementácie algoritmu
2.4 Škálovateľnosť algoritmu a jeho implementácia
2.4.1 Škálovateľnosť algoritmu
2.4.2 Škálovateľnosť implementácie algoritmu
Pozrime sa na škálovateľnosť paralelnej implementácie algoritmu podľa metodiky. Štúdia bola vykonaná na superpočítači Lomonosov zo superpočítačového komplexu Moskovskej univerzity. Sada a hranice hodnôt premenných parametrov na spustenie implementácie algoritmu:
- počet procesorov s celočíselnými štvorcovými hodnotami;
- veľkosť grafu s krokom 16000.
Nasledujúci obrázok znázorňuje graf výkonnosti vybranej implementácie algoritmu v závislosti od meniteľných parametrov spustenia.
Obrázok 8. Paralelná implementácia algoritmu. Zmena výkonu v závislosti od počtu procesorov a veľkosti plochy.
Vzhľadom na zvláštnosti paralelnej implementácie algoritmu je celkový výkon dosť nízky a pomaly sa zvyšuje s rastom počtu procesov a pri približovaní sa k počtu procesov 128 začína klesať. Vysvetľuje sa to používaním kolektívnych operácií pri každej iterácii algoritmu a skutočnosťou, že náklady na komunikačné výmeny sa výrazne zvyšujú so zvyšujúcim sa počtom použitých procesov. Výpočty každého procesu sú pomerne rýchle, a preto rozklad grafu slabo kompenzuje vplyv nákladov na komunikačné výmeny.
2.5 Dynamický výkon a efektívnosť implementácie algoritmu
Na experimenty bola použitá implementácia Dijkstrovho algoritmu. Všetky výsledky boli získané na superpočítači Lomonosov. Použili sme procesory Intel Xeon X5570 so špičkovým výkonom 94 Gflops, ako aj kompilátor intel 13.1.0. Čísla ukazujú efektivitu implementácie Dijkstrovho algoritmu na 32 procesoch.
Obrázok 9. Graf zaťaženia CPU pri vykonávaní Dijkstrovho algoritmu
Graf zaťaženia procesora ukazuje, že takmer po celú dobu spustenia programu je úroveň zaťaženia približne 50 %. To naznačuje rovnomerné zaťaženie procesorov pri použití 8 procesov na výpočtový uzol a bez použitia Hyper Threading.
Obrázok 10. Graf operácií s pohyblivou rádovou čiarkou za sekundu pri vykonávaní Dijkstrovho algoritmu
Obrázok 10 zobrazuje graf operácií s pohyblivou rádovou čiarkou za sekundu. Graf ukazuje celkovo veľmi slabý výkon okolo 250 kflops na vrchole a okolo 150 kflops v priemere naprieč všetkými uzlami. To znamená, že takmer všetky výpočty v programe sa vykonávajú s celými číslami.
Graf zápisu do pamäte ukazuje podobný vzor výpočtovej nerovnomernosti, pričom iba niekoľko procesov aktívne píše v rovnakom čase. To koreluje s inými plánmi vykonávania. Za zmienku stojí pomerne nízky počet prístupov k zápisu do pamäte. To svedčí o dobrej organizácii výpočtov a pomerne efektívnej práci s pamäťou.
Obrázok 15. Graf prenosovej rýchlosti cez sieť Infiniband v bajtoch/s, keď je spustený Dijkstrov algoritmus
V grafe rýchlosti prenosu dát siete Infiniband je pomerne vysoká rýchlosť prenosu dát v bajtoch za sekundu. To naznačuje, že procesy si navzájom intenzívne a pravdepodobne dosť malé časti údajov vymieňajú, pretože výpočtový výkon je vysoký. Stojí za zmienku, že prenosová rýchlosť sa medzi procesmi líši, čo naznačuje nerovnováhu vo výpočte.
Obrázok 16. Graf prenosovej rýchlosti cez sieť Infiniband v paketoch/s, keď je spustený Dijkstrov algoritmus
V grafe rýchlosti prenosu dát v paketoch za sekundu je extrémne vysoká intenzita prenosu dát. To naznačuje, že procesy si pravdepodobne vymieňajú nie príliš významné množstvá údajov, ale veľmi intenzívne. Kolektívne operácie sa používajú v každom kroku s malými časťami údajov, čo vysvetľuje tento obrázok. Existuje tiež menšia nerovnováha medzi procesmi, ako je vidieť v grafoch využitia pamäte, výpočtov a prenosu dát v bajtoch/s. To naznačuje, že procesy si vymieňajú rovnaký počet paketov podľa algoritmu, ale prijímajú rôzne množstvá dát a vykonávajú nerovnomerné výpočty.
Obrázok 17. Graf počtu procesov čakajúcich na vstup do fázy počítania (Loadavg), keď je spustený Dijkstrov algoritmus
Graf počtu procesov čakajúcich na vstup do fázy počítania (Loadavg) ukazuje, že hodnota tohto parametra je konštantná počas celej činnosti programu a je približne rovná 8. To naznačuje stabilnú prevádzku programu s načítanými výpočtami všetkými uzly. To naznačuje veľmi racionálne a statické zaťaženie hardvérových zdrojov procesmi. A ukazuje pomerne dobrú efektivitu vykonávanej implementácie. Vo všeobecnosti možno podľa systémového monitorovania programu usúdiť, že program fungoval pomerne efektívne a stabilne. Využitie pamäte je veľmi náročné a využitie komunikačných médií mimoriadne intenzívne, pričom objemy prenosu dát nie sú vysoké. To naznačuje náročnosť latencie komunikačného prostredia algoritmickej časti programu. Zdá sa, že nízka efektivita súvisí s pomerne vysokým objemom prenosov v každom procese a intenzívnou výmenou správ.