Zvažte příklad hledání nejkratší cesty. Je uvedena síť dálnic spojujících regiony města. Některé silnice jsou jednosměrné. Najděte nejkratší cesty z centra města do každého města v oblasti.
Chcete-li tento problém vyřešit, můžete použít Dijkstrův algoritmus- algoritmus na grafech, vynalezený holandským vědcem E. Dijkstrou v roce 1959. Najde nejkratší vzdálenost od jednoho z vrcholů grafu ke všem ostatním. Funguje pouze pro grafy bez hran se zápornou váhou.
Nechť je požadováno najít nejkratší vzdálenosti od 1. vrcholu ke všem ostatním.
Kružnice označují vrcholy, čáry cesty mezi nimi (hrany grafu). V kroužcích jsou uvedeny počty vrcholů, nad hranami je uvedena jejich váha - délka dráhy. U každého vrcholu je označen červený štítek - délka nejkratší cesty k tomuto vrcholu z vrcholu 1.
Předpokládá se, že štítek samotného vrcholu 1 je 0, štítky zbývajících vrcholů jsou nedosažitelné velké číslo(ideálně - nekonečno). To odráží, že vzdálenosti od vrcholu 1 k ostatním vrcholům ještě nejsou známy. Všechny vrcholy grafu jsou označeny jako nenavštívené. 
První krok
Minimální označení má vrchol 1. Jeho sousedy jsou vrcholy 2, 3 a 6. Sousedy vrcholu postupně obcházíme.
Prvním sousedem vrcholu 1 je vrchol 2, protože délka cesty k němu je minimální. Délka cesty k němu přes vrchol 1 se rovná součtu nejkratší vzdálenosti k vrcholu 1, hodnotě jeho štítku a délce hrany od 1. do 2., tedy 0 + 7 = 7. To je méně než aktuální štítek vrcholu 2 (10000), takže nový štítek druhého vrcholu je 7. 
Podobně najdeme délky cest pro všechny ostatní sousedy (vrcholy 3 a 6).
Všichni sousedé uzlu 1 jsou zkontrolováni. Aktuální minimální vzdálenost k vrcholu 1 je považována za konečnou a nepodléhá revizi. Vertex 1 je označen jako navštívený.
Druhý krok
Krok 1 algoritmu se opakuje. Opět najdeme „nejbližší“ z nenavštívených vrcholů. Toto je vrchol 2 označený 7.
Opět se pokusíme zmenšit popisky sousedů vybraného vrcholu a pokusíme se jimi projít přes 2. vrchol. Sousedy vrcholu 2 jsou vrcholy 1, 3 a 4.
Vertex 1 již byl navštíven. Dalším sousedem vrcholu 2 je vrchol 3, protože má minimální označení vrcholů označených jako nenavštívené. Pokud k němu půjdete přes 2, pak bude délka takové cesty rovna 17 (7 + 10 = 17). Ale aktuální označení třetího vrcholu je 9 a 9< 17, поэтому метка не меняется.
Dalším sousedem vrcholu 2 je vrchol 4. Pokud k němu půjdeme přes 2., pak bude délka takové cesty rovna 22 (7 + 15 = 22). Od 22<10000, устанавливаем метку вершины 4 равной 22.
Všichni sousedé vrcholu 2 byli prohlédnuti, takže jej označíme jako navštívený.
Třetí krok
Krok algoritmu zopakujeme výběrem vrcholu 3. Po jeho „zpracování“ dostaneme následující výsledky. 
Čtvrtý krok
Pátý krok
šestý krok
Nejkratší cesta z vrcholu 1 do vrcholu 5 bude tedy cesta přes vrcholy 1 — 3 — 6 — 5
, protože tímto způsobem získáme minimální váhu 20.
Pojďme se podívat na nejkratší cestu. Známe délku cesty pro každý vrchol a nyní budeme uvažovat vrcholy od konce. Zvažte konečný vrchol (v tomto případě vrchol 5
), a pro všechny vrcholy, se kterými je spojen, zjistíme délku cesty odečtením hmotnosti odpovídající hrany od délky cesty konečného vrcholu.
Ano, nahoře 5
má délku cesty 20
. Je spojena s vrcholem 6
a 4
.
Pro vrchol 6
získat váhu 20 – 9 = 11 (shoda).
Pro vrchol 4
získat váhu 20 - 6 = 14 (neodpovídající).
Pokud ve výsledku dostaneme hodnotu, která odpovídá délce cesty příslušného vrcholu (v tomto případě vrcholu 6
), pak právě z něj byl proveden přechod do finálního vrcholu. Tento vrchol označíme na požadované cestě.
Dále určíme hranu, přes kterou jsme se dostali do vrcholu 6
. A tak dále, dokud se nedostaneme na začátek.
Pokud v důsledku takového procházení máme v některém kroku stejné hodnoty pro několik vrcholů, pak můžeme vzít kterýkoli z nich - několik cest bude mít stejnou délku.
Implementace Dijkstrova algoritmu
K uložení vah grafu se používá čtvercová matice. Vrcholy grafu jsou v záhlaví řádků a sloupců. A váhy oblouků grafu jsou umístěny ve vnitřních buňkách tabulky. Graf neobsahuje smyčky, takže hlavní úhlopříč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 |
Implementace 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
#zahrnout
#zahrnout
#definujte VELIKOST 6
int main()
{
int a; // matice spojení
int d; // minimální vzdálenost
intv; // navštívené vrcholy
int temp, miniindex, min;
int počáteční_index = 0;
system("chcp 1251" );
system("cls" );
// Inicializace matice vztahů
for (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;
}
}
// Zobrazí matici vztahů
for (int i = 0; i
for (int j = 0; j
printf("\n");
}
//Inicializuje vrcholy a vzdálenosti
for (int i = 0; i
d[i] = 10 000;
v[i] = 1;
}
d=0;
// Krok algoritmu
dělat(
minindex = 10000;
min = 10 000;
for (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
miniindex=i;
}
}
// Přidejte nalezenou minimální hmotnost
// na aktuální váhu vrcholu
// a porovnejte s aktuální minimální vahou vrcholu
if (minindex != 10000)
{
for (int i = 0; i
pokud (a[i] > 0)
{
teplota = min + a[i];
pokud (tepl< d[i])
{
d[i] = teplota;
}
}
}
v = 0;
}
) zatímco (minindex< 10000);
// Zobrazí nejkratší vzdálenosti k vrcholům
printf( "\nNejkratší vzdálenosti k vrcholům: \n");
for (int i = 0; i
// Obnovení cesty
intver; // pole navštívených vrcholů
int end = 4; // index koncového vrcholu = 5 - 1
ver = konec + 1; // počáteční prvek - koncový vrchol
int k = 1; // index předchozího vrcholu
int hmotnost = d; // váha koncového vrcholu
while (end != begin_index) // dokud nedosáhneme počátečního vrcholu
{
for (int i = 0; i
jestliže (a[i] != 0) // pokud existuje spojení
{
int temp = hmotnost - a[i]; // určí váhu cesty z předchozího vrcholu
if (teplota == d[i]) // pokud se váha shoduje s vypočítanou
{ // znamená to, že došlo k přechodu z tohoto vrcholu
hmotnost = teplota; // uložení nové hmotnosti
konec = i; // uložení předchozího vrcholu
ver[k] = i + 1; // a zapište jej do pole
k++;
}
}
}
// Zobrazení cesty (počáteční vrchol je na konci pole k prvků)
printf( "\nNejkratší cesta výstupu\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
návrat 0;
}
Výsledek provedení
Zadní:
Dijkstrův algoritmus je grafový algoritmus, který vynalezl nizozemský vědec E. Dijkstra v roce 1959. Zjistí nejkratší vzdálenost od jednoho z vrcholů grafu ke všem ostatním.Algoritmus funguje pouze pro grafy bez hran se zápornou váhou.Algoritmus je široce používané v programování a technologiích, jako je použití protokolu OSPF k odstranění tras zpětné smyčky. Také známý jako nejkratší cesta jako první.
Dijkstrův algoritmus řeší problém nejkratší cesty jedním vrcholem pro vážený orientovaný graf G = (V, E) s počátečními vrcholy s, ve kterých jsou váhy všech hran nezáporné ((u, v) ? 0 pro všechny (u , v) E). V případě, že okraje grafu nejsou stejné, je vhodné použít tento algoritmus.
Formulace úkolu. Je tam graf. Některé jeho vrcholy jsou označeny jako vrchol 1. Je nutné najít minimální cesty z vrcholu 1 ke každému z vrcholů grafu. Minimální cesta je cesta s minimálním součtem cen podél cesty. Cena je nezáporné číslo, které je hmotností hrany.
Myšlenka algoritmu. Myšlenka je založena na následujícím zřejmém tvrzení: Nechť minimální cestu z vrcholu A k vrcholu B. A nechť je vrchol B připojen k nějakému počtu vrcholů i . Označme C i náklady na cestu z vrcholu B do vrcholu i. Z C i zvolíme minimální hodnotu. Poté bude minimální pokračování cesty z bodu B procházet zvolenou hodnotou.
Toto tvrzení opravdu nevyžaduje důkaz. A z toho plyne velmi závažný důsledek. Nechť existuje množina vrcholů, kterými již prochází minimální cesty. Taková množina zaručeně existuje, jedná se o vrchol 1. Výše formulovaný výrok umožňuje přidat k již existující množině vrcholů (dále je budeme nazývat vybrané) ještě jeden vrchol, a protože počet vrcholů v grafu je konečný, pak v konečném počtu kroků budou vybrány všechny vrcholy grafu a toto bude řešení.
Podstatou Dijkstrova algoritmu je postup přidání dalšího vrcholu do množiny vybraných. Tento postup se skládá ze dvou kroků:
1. Sestavíme sadu vrcholů spadajících do vybraného a najdeme mezi nimi vrchol s nejnižší cenou. Nalezený vrchol se přidá do množiny vybraných.
2. Sestrojíme množinu vrcholů spadajících do vybraného a určíme pro ně nové ceny. Nová cena vertexu je minimální cena cesty z množiny vybraných vertexů k danému vertexu. Nová cena je sestavena takto:
A. Pro nevybraný vrchol v množině vybraných vrcholů se určí podmnožina vrcholů s tímto vrcholem.
b. Pro každý vrchol vybrané podmnožiny se určí cena cesty k danému.
C. Je stanovena minimální cena. Tato cena se stává cenou nejvyšší.
Algoritmus pracuje se dvěma typy cen: okrajovou cenou a nejvyšší cenou. Okrajové ceny jsou konstantní. Ceny špiček se neustále přepočítávají. Význam těchto cen je jiný. Náklady na hranu jsou náklady na přesun z vrcholu do vrcholu spojeného touto hranou. A cena vrcholu je cenou minimální cesty. Další důležitá poznámka se týká přepočtu předběžných cen. Ve skutečnosti má smysl přepočítávat předběžné ceny pouze pro ty vrcholy, které jsou spojeny s vrcholem přidaným do množiny vybraných v posledním kroku, protože u ostatních vrcholů není důvod ke změně předběžné ceny.
Je známo, že všechny ceny (například pokládka cesty nebo průchodu) jsou nezáporné. Najděte cestu s nejnižšími náklady 1->i pro všechna i=1. n v čase O(n2).
Během činnosti algoritmu budou vybrána některá města (na začátku - pouze město 1, na konci - všechna). kde:
pro každé vybrané město i je uložena nejnižší cena cesty 1->i; přitom je známo, že minima je dosaženo na cestě procházející pouze vybranými městy;
pro každé nepřidělené město i je uložena nejnižší cena cesty 1->i, ve které jsou jako mezilehlá použita pouze vybraná města.
Množina přidělených měst je rozšířena na základě následující poznámky: pokud mezi všemi nepřidělenými městy vezmeme to, pro které je uložený počet minimální, pak toto číslo představuje skutečně nejnižší cenu. Opravdu, ať existuje kratší cesta. Zvažte první nevybrané město na této cestě - cesta k němu je již delší! (Negativa cen je zde zásadní.)
Přidáním vybraného města k vybraným musíme opravit informace uložené pro nevybraná města. V tomto případě stačí vzít v úvahu pouze cesty, ve kterých je nové město posledním přestupním bodem, a to je snadné, protože již známe minimální náklady na cestu do nového města.
Jinými slovy, každý vrchol z V je spojen se štítkem - minimální známá vzdálenost od tohoto vrcholu k a. Algoritmus pracuje krok za krokem – v každém kroku „navštíví“ jeden vrchol a snaží se zmenšit popisky. Algoritmus končí, když byly navštíveny všechny vrcholy.
Inicializace. Horní štítek A se má rovnat 0 , popisky zbývajících vrcholů jsou nekonečno. To odráží vzdálenost od A na další vrcholy jsou zatím neznámé. Všechny vrcholy grafu jsou označeny jako nenavštívené.
Krok algoritmu. Pokud byly navštíveny všechny vrcholy, algoritmus se ukončí. V opačném případě je vrchol vybrán z dosud nenavštívených vrcholů u S minimálním štítkem. Zvažujeme všechny možné cesty, ve kterých u je předposlední bod. Vrcholy spojené s vrcholem u hrany, budeme nazývat sousedy tohoto vrcholu. Pro každého souseda zvažte novou délku cesty rovnou součtu aktuálního štítku u a délka spojování hran u s tímto sousedem. Pokud je výsledná délka menší než štítek souseda, nahraďte štítek touto délkou. Po zvážení všech sousedů označíme vrchol u jako navštívený a opakujte krok.
Protože Dijkstrův algoritmus pokaždé zvolí zpracování vrcholu s nejmenším odhadem nejkratší cesty, můžeme říci, že patří mezi chamtivé algoritmy.
Popišme podrobněji, jak funguje Dijkstrův algoritmus.
Algoritmus používá tři pole N (= počet vrcholů sítě) čísel každé. První pole A obsahuje popisky se dvěma hodnotami: 0 (vrchol ještě není uvažován) a 1 (vrchol již uvažován); druhé pole B obsahuje vzdálenosti - aktuální nejkratší vzdálenosti od odpovídajícího vrcholu; třetí pole c obsahuje počty vrcholů - k-tý prvek C [k] je číslo předposledního vrcholu na aktuální nejkratší cestě z Vi do Vk. Matice vzdálenosti D určuje délku oblouku D; pokud takový oblouk neexistuje, pak D je přiřazeno velké číslo B, rovné „nekonečnu stroje“.
Nyní můžeme popsat:
1. (inicializace). V cyklu od 1 do N vyplňte pole A nulami; vyplnit pole C číslem i; přesunout i-tý řádek matice D do pole B, A [i]: =1; C [i]: =0 (i - počáteční číslo vrcholu)
2. (obecný krok). Najděte minimum mezi neoznačenými (tedy těmi k, pro které A [k] =0); minima nechť je dosaženo u indexu j, tzn. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , pak (B [k]: =B [j] +D ; C [k]: =j) (Podmínka znamená, že cesta Vi. Vk je delší než cesta Vi. Vj Vk) . (Pokud jsou označena všechna A [k], pak je délka cesty z Vi do Vk rovna B [k]. Nyní musíme) vyjmenovat vrcholy zahrnuté v nejkratší cestě).
3. (vydání odpovědi). (Cesta z Vi do Vk je vrácena v opačném pořadí následujícím postupem:)
2. Vydání z;
3. z:=C[z]. Pokud z = 0, pak konec, jinak přejděte na 3.2.
Pro provedení algoritmu je nutné Nkrát naskenovat pole B N prvků, tzn. Dijkstrův algoritmus má kvadratickou složitost: O(n2).
Níže je blokové schéma Dijkstrova algoritmu (viz obr. 2).
Obr.2. Vývojový diagram Dijkstrova algoritmu
Na začátku algoritmu je vzdálenost pro počáteční vrchol nastavena na nulu a všechny ostatní vzdálenosti jsou vyplněny velkým kladným číslem (větším, než je maximální možná cesta v grafu). Pole flags je vyplněno nulami. Poté začne hlavní smyčka.
V každém kroku smyčky hledáme vrchol s minimální vzdáleností a příznakem rovným nule. Pak v něm nastavíme příznak na 1 a zkontrolujeme všechny vrcholy, které k němu přiléhají. Pokud je v něm vzdálenost větší než součet vzdálenosti k aktuálnímu vrcholu a délky hrany, tak ji zmenšíme. Smyčka končí, když se příznaky všech vrcholů stanou roven 1.
Do každého města regionu (pokud se můžete pohybovat pouze po silnicích).
Možnost 2. Mezi světovými městy existuje řada letů, u každého je známa cena. Cena letu z A do B se nemusí rovnat ceně letu z B do A. Najděte trasu s minimálními náklady (případně s přestupy) z Kodaně do Barnaul.
Formální definice
Příklad
Zvažte provedení algoritmu na příkladu grafu zobrazeného na obrázku.
Nechť je požadováno najít nejkratší vzdálenosti od 1. vrcholu ke všem ostatním.
Implementace v programovacích jazycích
Provedení v jazyce C (C).
#define SIZE 6 #define INF 1000000000 int a [ VELIKOST ][ VELIKOST ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // matice cesty ( 1 , 2 , 3 , 4 , 5 , 6 ), ( 1 , 2 , 3 , 4 , 5 , 6 ), // horizontální indexy od bodu { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // svisle do bodu, hodnota - váha int d[ VELIKOST]; // pole nalezených nejkratších cest, indexy - vrcholy grafu void deikstra () ( int v [ VELIKOST ]; // pole štítků int temp , i ; int miniindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // pole cest inicializovaných do nekonečna v[i] = 1; ) d[0] = 0; dělat( // provedení algoritmu minindex = INF ; min = INF; pro (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 ); }
Je dán orientovaný nebo neorientovaný vážený graf s vrcholy a hranami. Váhy všech hran jsou nezáporné. Je zadán nějaký počáteční vrchol. Je nutné najít délky nejkratších cest z vrcholu do všech ostatních vrcholů a také poskytnout způsob, jak vytisknout samotné nejkratší cesty.
Tento problém se nazývá problém s nejkratšími cestami z jednoho zdroje.
Algoritmus
To popisuje algoritmus navržený holandským výzkumníkem Dijkstra(Dijkstra) v roce 1959
Pořiďme si pole, do kterého pro každý vrchol uložíme aktuální délku nejkratší cesty od do . Zpočátku a pro všechny ostatní vrcholy je tato délka rovna nekonečnu (při implementaci na počítači je obvykle vybráno dostatečně velké číslo jako nekonečno, samozřejmě větší než možná délka cesty):
Navíc u každého vrcholu uložíme, zda je ještě označený nebo ne, tzn. získáme booleovské pole. Zpočátku jsou všechny vrcholy neoznačené, tzn.
Samotný Dijkstrův algoritmus se skládá z iterací. V další iteraci je vybrán vrchol s nejmenší hodnotou mezi těmi, které ještě nebyly označeny, tj.:
(Je jasné, že při první iteraci bude vybrán počáteční vrchol.)
Takto vybraný vrchol je označen jako označený. Dále, v aktuální iteraci, z vrcholu, relaxace: všechny hrany vycházející z vrcholu jsou prohlédnuty a pro každý takový vrchol se algoritmus snaží zlepšit hodnotu . Nechť je délka aktuální hrany , pak ve formě kódu relaxace vypadá takto:
Zde aktuální iterace končí, algoritmus pokračuje k další iteraci (opět se vybere vrchol s nejmenší hodnotou, provedou se z něj relaxace atd.). V tomto případě se nakonec po iteracích označí všechny vrcholy grafu a algoritmus dokončí svou práci. Tvrdí se, že nalezené hodnoty jsou požadované délky nejkratších cest od do .
Stojí za zmínku, že pokud nejsou všechny vrcholy grafu dosažitelné z vrcholu, pak hodnoty pro ně zůstanou nekonečné. Je jasné, že několik posledních iterací algoritmu pouze vybere tyto vrcholy, ale tyto iterace nepřinesou žádnou užitečnou práci (protože nekonečná vzdálenost nemůže uvolnit jiné, dokonce nekonečné vzdálenosti). Algoritmus lze tedy okamžitě zastavit, jakmile je jako vybraný vrchol považován vrchol s nekonečnou vzdáleností.
Obnova cesty. Samozřejmě člověk většinou potřebuje znát nejen délky nejkratších cest, ale i cesty samotné. Ukažme si, jak uložit informace dostatečné pro následnou rekonstrukci nejkratší cesty z libovolného vrcholu. K tomu slouží tzv pole předků: pole, které pro každý vrchol obsahuje číslo vrcholu, který je předposlední v nejkratší cestě k vrcholu. To využívá skutečnosti, že pokud vezmeme nejkratší cestu k nějakému vrcholu a poté z této cesty odstraníme poslední vrchol, dostaneme cestu končící v nějakém vrcholu a tato cesta bude pro vrchol nejkratší. Pokud tedy máme toto pole předků, pak z něj lze obnovit nejkratší cestu, jednoduše pokaždé, když vezmeme předka z aktuálního vrcholu, dokud se nedostaneme do počátečního vrcholu - tímto způsobem získáme požadovanou nejkratší cestu, ale zapsanou v obrácené pořadí. Takže nejkratší cesta na vrchol je:
Zbývá pochopit, jak vybudovat toto pole předků. To se však děje velmi jednoduše: při každé úspěšné relaxaci, tzn. když od vybraného vrcholu dojde ke zlepšení vzdálenosti k nějakému vrcholu, napíšeme, že předkem vrcholu je vrchol:
Důkaz
Hlavní prohlášení, na kterém je založena správnost Dijkstrova algoritmu, je následující. Uvádí se, že poté, co se označí jakýkoli vrchol, aktuální vzdálenost k němu je již nejkratší, a proto se již nebude měnit.
Důkaz budeme vyrábět indukcí. U první iterace je její platnost zřejmá – pro vrchol máme , což je délka nejkratší cesty k němu. Nyní nechte toto tvrzení platit pro všechny předchozí iterace, tj. všechny již označené vrcholy; dokažme, že po provedení aktuální iterace není porušena. Nechť je vybraný vrchol v aktuální iteraci, tj. vrchol, který algoritmus označí. Dokažme, že se skutečně rovná délce nejkratší cesty k němu (tuto délku označíme ).
Zvažte nejkratší cestu na vrchol. Je zřejmé, že tuto cestu lze rozdělit na dvě cesty: , skládající se pouze z označených vrcholů (alespoň počáteční vrchol bude v této cestě) a zbytek cesty (může zahrnovat i označené vrcholy, ale vždy začíná znakem neoznačený). Označte prvním vrcholem cesty a posledním vrcholem cesty.
Nejprve dokažme naše tvrzení pro vrchol, tj. dokažme tu rovnost. To je však téměř zřejmé: vždyť v jedné z předchozích iterací jsme si vybrali vrchol a provedli z něj relaxaci. Vzhledem k tomu, že (díky samotnému výběru vrcholu ) je nejkratší cesta k rovna nejkratší cestě k plus hraně , pak při provedení relaxace od bude hodnota skutečně nastavena na požadovanou hodnotu.
Vzhledem k nezápornosti nákladů hran nepřesahuje délka nejkratší cesty (která se podle právě dokázaného rovná ) délku nejkratší cesty k vrcholu . Vzhledem k tomu, že (ostatně Dijkstrův algoritmus nemohl najít kratší cestu, než je obecně možné), dostáváme ve výsledku následující vztahy:
Na druhou stranu, protože oba a a jsou neoznačené vrcholy, protože to byl vrchol, který byl vybrán v aktuální iteraci, a ne vrchol , získáme další nerovnost:
Z těchto dvou nerovností usuzujeme na rovnost a poté z výše nalezených vztahů získáme a:
Q.E.D.
Implementace
Dijkstrův algoritmus se tedy skládá z iterací, z nichž se v každé vybere neoznačený vrchol s nejmenší hodnotou, tento vrchol se označí a poté se prohlédnou všechny hrany vycházející z tohoto vrcholu a podél každé hrany se pokusí vylepšit hodnotu na druhém konci hrany.
Doba běhu algoritmu je součet:
Při nejjednodušší implementaci těchto operací budou operace vynaloženy na nalezení vrcholu a operace na jedné relaxaci a konečné asymptotické algoritmus je:
Implementace:
const int INF = 1000000000 ; int main() ( int n; ... přečti n ... vektor< vector < pair< int ,int >> > g(n); ... čtení grafu... int s = ...; // počáteční vrchol vektor< int >d(n, INF), p(n); d[s] = 0; vektor< char >u(n); for (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; } } } }Zde je graf uložen ve formě seznamů sousedství: pro každý vrchol seznam obsahuje seznam hran vycházejících z tohoto vrcholu, tzn. seznam dvojic >, kde první prvek dvojice je vrchol, ke kterému hrana vede, a druhý prvek je váha hrany.
) běží v čase O(m + n \ln n) a je asymptoticky nejrychlejším známým sekvenčním algoritmem pro tuto třídu problémů.
1.2 Matematický popis algoritmu
Nechť je dán graf G = (V, E) s vahami hran f(e) a rozlišeným zdrojovým vrcholem u . Označme d(v) nejkratší vzdálenost od zdroje u k vrcholu v .
Nechť jsou již spočítány všechny vzdálenosti nepřesahující určité číslo r, tedy vzdálenosti k vrcholům z množiny V_r = \( v \in V \mid d(v) \le r \). Nechat
(v, w) \in \arg\min \( d(v) + f(e) \mid v \in V, e = (v, w) \in E \).Pak d(w) = d(v) + f(e), a v leží na nejkratší cestě z u do w .
Množství d^+(w) = d(v) + f(e), kde v \in V_r , e = (v, w) \in E , jsou volány odhadované vzdálenosti a jsou horní mez pro skutečné vzdálenosti: d(w) \le d^+(w) .
Dijkstrův algoritmus v každém kroku najde vrchol s nejmenší odhadovanou vzdáleností, označí jej jako navštívený a aktualizuje odhadované vzdálenosti pro všechny koncové body hran, které z něj vycházejí.
1.3 Výpočtové jádro algoritmu
Hlavní výpočty se týkají operací na prioritní frontě:
- extrahování minimálního prvku (delete_min);
- snížit prioritu prvku (decrease_key).
1.4 Makrostruktura algoritmu
Pseudokód algoritmu:
Vstupní data: graf s vrcholy PROTI, okraje E s váhami F(E); zdrojový uzel u. Výstup: vzdálenosti d(proti) do každého vrcholu proti ∈ PROTI z vrchu u. Q := Nový prioritní fronta pro každého proti ∈ PROTI: -li proti = u pak d(proti) := 0 jiný d(proti) := ∞ Q.vložit( proti, d(proti)) zatímco Q ≠ ∅: proti := Q.delete_min() pro každého E = (proti, w) ∈ E: -li d(w) > d(proti) + F(E): d(w) := d(proti) + F(E) Q.decrease_key( w, d(w))1.5 Schéma implementace sekvenčního algoritmu
Konkrétní implementace Dijkstrova algoritmu je určena volbou použitého prioritního algoritmu fronty. V nejjednodušším případě to může být pole nebo seznam, přičemž hledání minima vyžaduje zobrazení všech vrcholů. Efektivnější je použít haldu; nejznámější odhad složitosti je pro variantu využívající Fibonacciho haldu.
Možnost implementace je možná, když se vrcholy nepřidávají do fronty ve fázi inicializace, ale v době první návštěvy.
1.6 Sekvenční složitost algoritmu
Sekvenční složitost algoritmu je O(C_1 m + C_2n), kde
- C_1 – počet operací ke snížení vzdálenosti k vrcholu;
- C_2 je počet operací pro výpočet minima.
Původní Dijkstrův algoritmus používal jako vnitřní datovou strukturu seznamy, pro které C_1 = O(1) , C_2 = O(n) , takže celková složitost byla O(n^2) .
Při použití Fibonacciho haldy se minimální doba výpočtu zkrátí na C_2 = O(\ln n) , takže celková složitost je O(m + n \ln n) , což je asymptoticky nejznámější výsledek pro tuto třídu problémů.
1.7 Informační graf
Pro základní implementaci Dijkstrova algoritmu na seznamech nebo polích je uveden graf algoritmu.
Obrázek 1. Graf algoritmu bez zobrazení vstupních a výstupních dat. n=3. Operace porovnání jsou označeny žlutě, operace změny označení vrcholů jsou označeny zeleně a označení vrcholů je označeno modře.
1.8 Zdroj paralelního algoritmu
Dijkstrův algoritmus umožňuje efektivní paralelizaci, průměrnou dobu běhu O(n^(1/3)\ln n) s výpočetním objemem O(n \ln n + m) .
První odhad je založen na charakteristice daps, která měří počet přístupů do paměti (čtení a zápisy) provedených za sekundu. Tato charakteristika je analogická s odhadem flopů ve vztahu k práci s pamětí a je spíše odhadem výkonu interakce s pamětí než odhadem lokality. Slouží však jako dobrý zdroj informací, včetně porovnání s výsledky pro následující funkci cvg.
Obrázek 6 ukazuje hodnoty daps pro implementace běžných algoritmů seřazené ve vzestupném pořadí (čím více daps, tím lepší výkon obecně). Můžete vidět, že výkon paměti je poměrně nízký. To není překvapivé, protože implementace algoritmů nad grafy mají téměř vždy nízkou efektivitu kvůli nepravidelnosti přístupu k datům, což jsme viděli při analýze přístupového profilu.
Obrázek 6. Porovnání hodnot skóre daps
Druhá charakteristika, cvg, má poskytnout odhad lokality více nezávislý na stroji. Určuje, jak často potřebuje program stahovat data do mezipaměti. V souladu s tím platí, že čím menší je hodnota cvg, tím méně často je třeba to provádět, tím lepší je lokalita.
Obrázek 7 ukazuje hodnoty cvg pro stejnou sadu implementací seřazené v sestupném pořadí (čím menší cvg, tím vyšší je obecně lokalita). Je vidět, že v tomto případě hodnota cvg dobře koreluje s výkonnostním skóre a odráží nízkou lokalitu, což je v souladu se zjištěními kvalitativního hodnocení lokality.
Obrázek 7. Porovnání hodnot skóre cvg
2.3 Možné metody a vlastnosti paralelní implementace algoritmu
2.4 Škálovatelnost algoritmu a jeho implementace
2.4.1 Škálovatelnost algoritmu
2.4.2 Škálovatelnost implementace algoritmu
Prozkoumejme škálovatelnost paralelní implementace algoritmu podle metodiky. Studie byla provedena na superpočítači Lomonosov ze superpočítačového komplexu Moskevské univerzity. Sada a hranice hodnot parametrů proměnných pro spuštění implementace algoritmu:
- počet procesorů s celočíselnými čtvercovými hodnotami;
- velikost grafu s krokem 16000.
Následující obrázek ukazuje graf výkonu zvolené implementace algoritmu v závislosti na měnitelných parametrech spouštění.
Obrázek 8. Paralelní implementace algoritmu. Změna výkonu v závislosti na počtu procesorů a velikosti oblasti.
Vzhledem ke zvláštnostem paralelní implementace algoritmu je celkový výkon poměrně nízký a s růstem počtu procesů se pomalu zvyšuje a při přibližování se počtu procesů 128 začíná klesat. To je vysvětleno používáním kolektivních operací při každé iteraci algoritmu a skutečností, že náklady na komunikační výměny výrazně rostou s rostoucím počtem použitých procesů. Výpočty na každý proces jsou poměrně rychlé, a proto rozklad grafu slabě kompenzuje vliv nákladů na komunikační výměny.
2.5 Dynamický výkon a efektivita implementace algoritmu
Pro experimenty byla použita implementace Dijkstrova algoritmu. Všechny výsledky byly získány na superpočítači Lomonosov. Použili jsme procesory Intel Xeon X5570 se špičkovým výkonem 94 Gflops a také kompilátor intel 13.1.0. Čísla ukazují efektivitu implementace Dijkstrova algoritmu na 32 procesech.
Obrázek 9. Graf zatížení CPU při provádění Dijkstrova algoritmu
Graf zatížení procesoru ukazuje, že téměř po celou dobu běhu programu je úroveň zatížení cca 50 %. To ukazuje na rovnoměrné zatížení procesorů při použití 8 procesů na výpočetní uzel a bez použití Hyper Threading.
Obrázek 10. Graf operací s pohyblivou řádovou čárkou za sekundu při provádění Dijkstrova algoritmu
Obrázek 10 ukazuje graf operací s pohyblivou řádovou čárkou za sekundu. Graf ukazuje celkově velmi špatný výkon asi 250 kflops na vrcholu a asi 150 kflops v průměru napříč všemi uzly. To znamená, že téměř všechny výpočty v programu jsou prováděny s celými čísly.
Graf zápisu do paměti ukazuje podobný vzorec výpočetní nerovnoměrnosti, přičemž pouze několik procesů aktivně zapisuje současně. To koreluje s jinými plány provádění. Za zmínku stojí poměrně nízký počet přístupů pro zápis do paměti. To svědčí o dobré organizaci výpočtů a celkem efektivní práci s pamětí.
Obrázek 15. Graf přenosové rychlosti v síti Infiniband v bajtech/s, když je spuštěn Dijkstrův algoritmus
V grafu rychlosti přenosu dat sítě Infiniband je poměrně vysoká rychlost přenosu dat v bajtech za sekundu. To naznačuje, že procesy si mezi sebou intenzivně vyměňují a pravděpodobně spíše malé části dat, protože výpočetní výkon je vysoký. Stojí za zmínku, že přenosová rychlost se mezi procesy liší, což ukazuje na výpočetní nerovnováhu.
Obrázek 16. Graf přenosové rychlosti v síti Infiniband v paketech/s, když je spuštěn Dijkstrův algoritmus
V grafu rychlosti přenosu dat v paketech za sekundu je extrémně vysoká intenzita přenosu dat. To naznačuje, že si procesy pravděpodobně vyměňují nepříliš významná množství dat, ale velmi intenzivně. Kolektivní operace se používají v každém kroku s malými částmi dat, což vysvětluje tento obrázek. Mezi procesy je také menší nerovnováha, než je vidět v grafech paměti, výpočtu a bajtů/s. To znamená, že procesy si vyměňují stejný počet paketů podle algoritmu, ale přijímají různé množství dat a provádějí nerovnoměrné výpočty.
Obrázek 17. Graf počtu procesů čekajících na vstup do fáze počítání (Loadavg), když je spuštěn Dijkstrův algoritmus
Na grafu počtu procesů čekajících na vstup do fáze počítání (Loadavg) je vidět, že hodnota tohoto parametru je konstantní po celou dobu chodu programu a přibližně se rovná 8. To ukazuje na stabilní chod programu s načteným výpočty všemi uzly. To svědčí o velmi racionálním a statickém zatěžování hardwarových prostředků procesy. A ukazuje docela dobrou efektivitu prováděné implementace. Obecně lze podle systémového monitorování programu usoudit, že program fungoval poměrně efektivně a stabilně. Využití paměti je velmi intenzivní a využití komunikačních médií extrémně intenzivní, přičemž objemy přenosu dat nejsou vysoké. To svědčí o náročnosti latence komunikačního prostředí algoritmické části programu. Zdá se, že nízká efektivita souvisí s poměrně vysokým objemem přenosů na každém procesu a intenzivní výměnou zpráv.