Dijkstrův algoritmus je grafový algoritmus, který najde nejkratší cestu mezi dvěma danými vrcholy v grafu s nezápornými délkami oblouků. Často je také kladen úkol vypočítat nejkratší cestu z daného vrcholu ke všem ostatním. Algoritmus je široce používán v programování, například jej používají směrovací protokoly.

Popis

Vstupem algoritmu je vážený orientovaný graf s oblouky nezáporné váhy. Výstupem je sada nejkratších cest z daného vrcholu k ostatním.

Na začátku se předpokládá, že vzdálenost pro počáteční vrchol je nulová a vzdálenosti ke všem ostatním jsou považovány za nekonečné. Pole příznaků indikujících, zda byl vrchol předán, je vyplněno nulami. Poté se v každém kroku smyčky hledá vrchol s minimální vzdáleností od počátečního a příznakem rovným nule. Nastaví se mu příznak a zkontrolují se všechny sousední vrcholy. Pokud je dříve vypočítaná vzdálenost od zdrojového vrcholu k tomu, který je kontrolován, větší než součet vzdálenosti k aktuálnímu vrcholu a délky hrany od něj ke kontrolovanému vrcholu, pak se vzdálenost ke kontrolovanému vrcholu rovná vzdálenost k aktuálnímu + hrana od aktuálního ke kontrolovanému. Smyčka končí, když se příznaky všech vrcholů stanou rovnými 1, nebo když je vzdálenost ke všem vrcholům s příznakem 0 nekonečná. Druhý případ je možný tehdy a pouze tehdy, když je graf odpojen.

Dijkstrův algoritmus v pseudokódu

Vchod: Z: pole reálných – matice délek oblouků grafu; s je vrchol, ze kterého se hledá nejkratší cesta, a t je vrchol, do kterého se hledá.

Výstup: vektory T: pole reálných; a H: pole 0..r. Pokud je nahoře proti leží na nejkratší cestě z s na t, pak Televize]- nejkratší délka cesty od s na y; Studna] - vrchol bezprostředně předcházející v na nejkratší cestě.

H je pole, ve kterém vrchol n odpovídá vrcholu m, předchozímu na cestě k n od s.

T je pole, ve kterém vrchol n odpovídá vzdálenosti od něj k s.

X je pole, ve kterém vrchol n odpovídá 1, pokud je známa cesta k němu, a 0, pokud ne.

inicializace pole:

pro proti od 1 do R dělat

T[proti]: = ∞ (zkratka neznámá)

X[v]: = 0 (všechny vrcholy nejsou zaškrtnuté)

H[s]: = 0 ( s nic nepřijde dřív)

T[s]:= 0 (nejkratší cesta má délku 0...)

X[s]:= 1 ( ...a on je známý ) proti : = s (aktuální top)

M: (aktualizace poznámek)

pro a ∈ G( a) dělat

-li X[i] = 0 & T[u]> Televize] + C pak

T[u]: = Televize] + C(našel kratší cestu z s v a přes proti }

h[u]:= proti(Pamatuj si to)

m: = ∞

proti : = 0

(najít konec nejkratší cesty)

pro a od 1 do p dělat

-li X[u] = 0 &T[u]< t pak

proti:= u;

m:= T[u]( horní proti končí nejkratší cesta z s

-li proti = 0 pak

zastavit (není cesta ven s v t) konec pokud

-li proti= t pak

zastávka ( nalezena nejkratší cesta z s v t) konec pokud

X[v]: = 1 (nalezena nejkratší cesta z s v proti ) jít do M

Odůvodnění

K prokázání správnosti Dijkstrova algoritmu stačí poznamenat, že pro každé provedení těla smyčky začínající štítkem M, jako proti používá se vrchol, pro který je známa nejkratší cesta z vrcholu s. Jinými slovy, pokud X[v] = 1, pak T[v] = d(s,v) , a všechny vrcholy na cestě (s, v) definované vektorem H mají stejnou vlastnost, tzn.

Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.

Ve skutečnosti (indukcí), poprvé jako proti používá se vrchol s, pro který je nejkratší cesta prázdná a má délku 0 (neprázdné cesty nemohou být kratší, protože délky oblouků jsou nezáporné). Nechť T[u] = d(s,u) pro všechny dříve označené vrcholy a. Zvažte nově označený vrchol proti, který je vybrán z podmínky T[v] = min T[u]. Všimněte si, že pokud je známá cesta procházející označenými vrcholy, pak je známa nejkratší cesta. Předpokládejme (naopak), že T[v] > d(s, v), tedy nalezená cesta vedoucí z s v proti, není nejkratší. Pak na této cestě musí být neoznačené vrcholy. Zvažte první vrchol w na této cestě tak, že T[w] = 0. Máme: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.

Časová složitost

Složitost Dijkstrova algoritmu závisí na tom, jak najít nenavštívený vrchol s minimální vzdáleností od původního, jak uložit sadu nenavštívených vrcholů a jak aktualizovat štítky. Nechť n je počet vrcholů a m je počet hran v grafu. Potom, v nejjednodušším případě, když je prohledána celá sada vrcholů, aby se našel vrchol s minimální vzdáleností od původního vrcholu, a k uložení vzdáleností se použije pole, doba běhu algoritmu je O(n 2) . Hlavní smyčka je provedena asi nkrát, v každé z nich je vynaloženo asi n operací na nalezení minima. Cyklování sousedy každého navštíveného vrcholu vyžaduje počet operací úměrných počtu hran m (protože každá hrana se v těchto cyklech vyskytuje přesně dvakrát a vyžaduje konstantní počet operací). Celková doba běhu algoritmu je tedy O(n 2 + m), ale protože m je mnohem menší než n (n-1), je to nakonec O(n 2).

U řídkých grafů (tj. těch, pro které je m mnohem menší než n²), lze nenavštívené vrcholy uložit do binární hromady a hodnoty vzdálenosti se používají jako klíč. Protože se smyčka provede asi nkrát a počet relaxací (změn štítků) není větší než m, je doba běhu takové implementace O(nlogn+mlogn)

Příklad

Výpočet vzdáleností od vrcholu 1 pomocí prostupných vrcholů:

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 printf( "Zadejte vzdálenost %d - %d: " i + 1, j + 1);
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("%5d " , a[i][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 { // Pokud vrchol ještě nebyl navštíven a váha je menší než min
if ((v[i] == 1) && (d[i] { // Změna přiřazení hodnot
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;
}
) while (minindex< 10000);
// Zobrazí nejkratší vzdálenosti k vrcholům
printf( "\nNejkratší vzdálenosti k vrcholům: \n");
for (int i = 0; i printf("%5d" , d[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 // podívejte se na všechny vrcholy
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
{ // to znamená, ž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í:

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 hrana , 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.

5.4.3. Problém nejkratší cesty a Dijkstrův algoritmus pro jeho řešení

Nechť je uveden digraf G(PROTI, E), jehož každému oblouku je přiřazeno číslo
volala délka oblouku.

Definice. Délka cesta je součet délek oblouků, které tvoří tuto cestu. Problém nejkratší cesty dát takhle.

Možnost 1. Najděte délky nejkratších cest (cesty minimální délky) a samotné cesty z pevného vrcholu s do všech ostatních vrcholů grafu.

Možnost 2. Najděte délky nejkratších cest a samotné cesty mezi všemi dvojicemi vrcholů v daném grafu.

Pokud má graf oblouky záporné délky, problém nemusí mít řešení (ztratí smysl). To je způsobeno skutečností, že graf může obsahovat obrys záporné délky. Přítomnost obrysů záporné délky znamená, že délka cesty může být rovna
. A pokud neexistují žádné obrysy záporné délky, pak existují nejkratší cesty a každá nejkratší cesta je jednoduchý řetězec.

Všimněte si, že pokud existuje nejkratší cesta, pak kterákoli z jejích dílčích cest je také nejkratší cestou mezi odpovídajícími vrcholy.

Dijkstrův algoritmus pro řešení problému nejkratší cesty.

Algoritmus pracuje s oblouky kladné délky a určuje nejkratší cesty z pevného vrcholu s do všech ostatních vrcholů grafu. Označme tyto vrcholy proti 1 , proti 2 ,…, proti n .

Definice. Zavolejme vrchol u ležící blíže k vrcholu s než nahoře proti je-li délka nejkratší cesty z s před u menší než délka nejkratší cesty z s před proti. Řekneme, že vrcholy u a proti stejně vzdálený z vrchu s, jsou-li délky nejkratších cest od s před u a od s před proti zápas.

Dijkstrův algoritmus postupně seřadí vrcholy grafu podle blízkosti k vrcholu s a je založen na následujících základních principech.

Pokud jsou délky oblouku kladná čísla, pak

nejblíže k s vrchol je ona sama. Délka nejkratší cesty z s před s je 0;

nejblíže k s jiný vrchol než s, lže z s ve vzdálenosti jednoho oblouku - nejkratší ze všech oblouků vycházejících z vrcholu s;

jakýkoli mezilehlý vrchol nejkratší cesty z s až k nějakému vrcholu proti leží blíž s než koncový vrchol proti;

nejkratší cesta k dalšímu uspořádanému vrcholu může procházet pouze již uspořádanými vrcholy.

Nechť algoritmus již seřadil vrcholy proti 1 , proti 2 … proti k . Označit podle
,
délka nejkratší cesty na vrchol proti i .

Uvažujme všechny oblouky původního grafu, které začínají v jednom z vrcholů množiny
a končí v dosud neuspořádaných vrcholech. Za každý takový oblouk kupř
, vypočítejte součet
. Tento součet se rovná délce cesty z s v y, ve kterém je vrchol proti i je předposlední vrchol a cesta od s v proti i je nejkratší ze všech spojujících cest s a proti i .

To určuje délky všech cest od s k dosud neuspořádaným vrcholům, ve kterých jsou pouze vrcholy z mezilehlých vrcholů k nejblíže k s. Nechte nejkratší z těchto cest končit nahoře w. Pak w a jíst
blízko k s vrchol.

Technicky jsou akce podle Dijkstrova algoritmu prováděny pomocí aparátu vertex labels. Štítek Vertex proti označený jako
. Každý štítek je číslo rovné délce nějaké cesty od s před proti. Štítky se dělí na dočasné a trvalé. V každém kroku se pouze jeden štítek stane trvalým. To znamená, že jeho hodnota je rovna délce nejkratší cesty k příslušnému vrcholu a tento vrchol sám o sobě je uspořádán. Číslo dalšího uspořádaného vrcholu je označeno písmenem R.

Popis algoritmu.

Krok 1. (počáteční nastavení). Dát
a považovat toto označení za trvalé. Dát
,
a považovat tyto štítky za dočasné. Dát
.

Krok 2 (obecný krok). Opakuje se n krát, dokud nebudou seřazeny všechny vrcholy grafu.

Přepočítat časové razítko
jakýkoli neuspořádaný vrchol proti i, která zahrnuje oblouk opouštějící vrchol R, podle pravidla

Vyberte vrchol s minimálním časovým razítkem. Pokud existuje několik takových vrcholů, vyberte libovolný.

Nechat w- vrchol s minimálním časovým razítkem. Značka čtení
konstantní a dát
.

Je vhodné uspořádat kroky Dijkstrova algoritmu do tabulky, jejíž každý sloupec odpovídá vrcholu grafu. Řádky tabulky odpovídají opakování společného kroku.

Příklad. Pro graf na Obr. 4. najděte nejkratší cesty z vrcholů
do všech ostatních vrcholů grafu. Hrany znamenají dva různě vedené oblouky stejné délky.

Řešení. V tabulce. V každém kroku se zapíše 1 štítek vrcholů. Trvalé značky jsou označeny znaménkem „+“. Pojďme si podrobně popsat, jak se počítají štítky vrcholů.

Z vrcholu 1 vycházejí oblouky k vrcholům 2, 5, 6. Přepočítejte popisky těchto vrcholů a vyplňte druhý řádek tabulky.

Vertex label 6 se stává trvalým,
.

Od vrcholu 6 jdou oblouky k dosud neuspořádaným vrcholům 2, 5, 8, 9. Přepočítejte jejich časová razítka

Vyplňte řádek 3 tabulky. Minimální počet časových razítek je 3 (vertex label 9),
.

Z vrcholu 9 vycházejí oblouky do dosud neuspořádaných vrcholů 5, 8, 11, 12.

Vyplňte čtvrtý řádek tabulky. V tomto řádku mají dva vrcholy - 2 a 12 minimální časová razítka rovnající se 4. Nejprve seřaďme například vrchol 2. V dalším kroku pak bude uspořádán vrchol 12.

stůl 1

Tak,
.

Z vrcholu 2 jdou oblouky k dosud neuspořádaným vrcholům 3, 4, 5. Přepočítejte časová razítka těchto vrcholů

Vyplňte řádek 5 tabulky. Minimální počet časových razítek je 4 (vertex label 12),
.

Vyplňte řádek 6 tabulky. Minimální počet časových razítek je 5 (vertex label 5),
.

Vyplňte řádek 7 tabulky. Vertex label 8 se stane konstantní (je roven 5),
.

Vertex 11 je objednán.

Z vrcholu 11 vycházejí oblouky do neuspořádaných vrcholů 7, 10. Přepočítejte časová razítka těchto vrcholů

Vertex 4 dostane trvalé označení.

Z vrcholu 4 vycházejí oblouky do neuspořádaných vrcholů 3, 7. Přepočítat časová razítka

Uspořádat horní 3.

Vyplňte řádek 12 tabulky. V tomto kroku objednáme poslední neuspořádaný vrchol 10.

Stavění stromu nejkratších cest.

Strom nejkratší cesty je řízený strom zakořeněný ve vrcholu. S . Všechny cesty v tomto stromu jsou nejkratšími cestami pro tento graf.

Strom nejkratší cesty je postaven podle tabulky, vrchol po vrcholu je do něj zařazen v pořadí, v jakém obdržely trvalé popisky. Kořen je první uzel, který bude zahrnut do stromu. S .

Postavme pro náš příklad strom nejkratších cest.

Nejprve do stromu zahrneme kořen, vrchol 1. Poté je do stromu zahrnut oblouk (1,6). Jako další byl objednán vrchol 9, jehož délka nejkratší cesty je rovna 3. Poprvé se číslo 3 objevilo ve třetí řadě, která byla vyplněna
. Vrchol 6 je tedy předposledním vrcholem nejkratší cesty k vrcholu 9. Oblouk (6,9) délky 1 zařadíme do stromu.

Poté byl vrchol 2 uspořádán s nejkratší délkou cesty rovnou 4. Toto číslo se poprvé objevilo ve třetím řádku, který byl vyplněn
. V důsledku toho nejkratší cesta k druhému vrcholu prochází podél oblouku (6,2). Oblouk (6,2) délky 2 zahrneme do stromu.

Dále byl objednán vrchol 12,
. Poprvé se ve čtvrtém řádku objeví číslo 4, které bylo vyplněno kdy
. Ve stromu je zahrnut oblouk (9,12) délky 1. Kompletní strom nejkratších cest je znázorněn na obr. 5.

Dijkstrův algoritmus může selhat, pokud má graf oblouky záporné délky. Takže hledat nejkratší cesty z vrcholu s =1 pro graf na obr. 6, algoritmus nejprve seřadí uzel 3, potom uzel 2 a skončí. Navíc tato nejkratší cesta k vrcholu 3 je z pohledu Dijkstrova algoritmu oblouk (1,3) délky 3.

Ve skutečnosti se nejkratší cesta k vrcholu 3 skládá z oblouků (1,2) a (2,3), délka této cesty je 5+(-3)=2.

Kvůli přítomnosti oblouku (2,3) záporné délky –3 byly porušeny následující základní principy:

nejblíže k s vrchol leží ve vzdálenosti dvou oblouků od něj a ne jednoho;

mezilehlý vrchol nejkratší cesty 1-2-3 (vrchol 2) leží dále od vrcholu 1 (vzdálenost 5) než konečný vrchol cesty 3.

Přítomnost oblouků záporné délky proto komplikuje řešení problému nejkratší cesty a vyžaduje použití složitějších algoritmů než Dijkstrův algoritmus.

Z mnoha algoritmů pro nalezení nejkratších tras v grafu jsem na Habrého našel pouze popis Floyd-Warshallova algoritmu. Tento algoritmus najde nejkratší cesty mezi všemi vrcholy grafu a jejich délku. V tomto článku popíšu princip fungování Dijkstrova algoritmu, který najde optimální trasy a jejich délku mezi jedním konkrétním vrcholem (zdrojem) a všemi ostatními vrcholy grafu. Nevýhodou tohoto algoritmu je, že nebude správně fungovat, pokud má graf oblouky se zápornou váhou.

Vezměme například následující orientovaný graf G:

Tento graf můžeme znázornit jako matici C:

Jako zdroj vezměme vrchol 1. To znamená, že budeme hledat nejkratší cesty z vrcholu 1 k vrcholům 2, 3, 4 a 5.
Tento algoritmus krok za krokem prochází všechny vrcholy grafu a přiřazuje jim popisky, které jsou známou minimální vzdáleností od zdrojového vrcholu ke konkrétnímu vrcholu. Podívejme se na tento algoritmus na příkladu.

Přiřaďme 1. vrcholu štítek rovný 0, protože tento vrchol je zdrojem. Zbývajícím vrcholům budou přiřazeny štítky rovné nekonečnu.

Dále vybereme vrchol W, který má minimální označení (nyní je to vrchol 1) a vezmeme v úvahu všechny vrcholy, ke kterým z vrcholu W vede cesta, která neobsahuje vrcholy mediátoru. Každému z uvažovaných vrcholů přiřadíme štítek rovný součtu štítku W a délce cest z W k uvažovanému vrcholu, ale pouze v případě, že výsledný součet je menší než předchozí hodnota štítku. Pokud množství není menší, pak ponecháme předchozí štítek beze změny.

Poté, co zvážíme všechny vrcholy, ke kterým vede přímá cesta z W, označíme vrchol W jako navštívený a z dosud nenavštívených vybereme ten, který má minimální hodnotu popisku, bude to další vrchol W. V v tomto případě je to vrchol 2 nebo 5. Pokud existuje několik vrcholů se stejnými štítky, pak je jedno, který z nich zvolíme jako W.

Zvolíme vrchol 2. Z něj ale nevede žádná odchozí cesta, takže tento vrchol okamžitě označíme jako navštívený a přejdeme k dalšímu vrcholu s minimálním označením. Tentokrát má minimální označení pouze vrchol 5. Uvažujme všechny vrcholy, ke kterým vedou přímé cesty z 5, ale které ještě nebyly označeny jako navštívené. Opět najdeme součet štítku vrcholu W a váhy hrany od W k ​​aktuálnímu vrcholu, a pokud je tento součet menší než předchozí štítek, nahradíme hodnotu štítku výsledným součtem.

Na základě obrázku vidíme, že popisky 3. a 4. vrcholu se zmenšily, to znamená, že k těmto vrcholům byla nalezena kratší cesta ze zdrojového vrcholu. Dále označte 5. vrchol jako navštívený a vyberte další vrchol, který má minimální označení. Všechny výše uvedené akce opakujeme tak dlouho, dokud existují nenavštívené vrcholy.

Po dokončení všech kroků dostaneme následující výsledek:

Nechybí ani vektor P, na základě kterého můžete postavit nejkratší trasy. Počtem prvků je tento vektor roven počtu vrcholů v grafu Každý prvek obsahuje poslední mezilehlý vrchol na nejkratší cestě mezi zdrojovým vrcholem a konečným vrcholem. Na začátku algoritmu jsou všechny prvky vektoru P rovny zdrojovému vrcholu (v našem případě P = (1, 1, 1, 1, 1)). Dále ve fázi přepočítávání hodnoty štítku pro uvažovaný vrchol, pokud se štítek uvažovaného vrcholu změní na menší, zapíšeme hodnotu aktuálního vrcholu W do pole P. Například: 3. vrchol měl štítek s hodnotou "30", s W=1. Dále při W=5 se označení 3. vrcholu změnilo na "20", proto hodnotu zapíšeme do vektoru P - P=5. Také při W=5 se změnila hodnota štítku ve 4. vrcholu (bylo to "50", stalo se "40"), což znamená, že 4. prvku vektoru P by měla být přiřazena hodnota W - P =5. V důsledku toho dostaneme vektor Р = (1, 1, 5, 5, 1).

S vědomím, že každý prvek vektoru P obsahuje poslední mezilehlý vrchol na cestě mezi zdrojem a konečným vrcholem, můžeme získat nejkratší cestu samotnou.