Autor : Pavel Janáček , L95295

Dijkstrův algoritmus

V případě, že hledáme nejkratší cesty v grafu s nezápornými cenami hran, můžeme použít Dijkstrův algoritmus. Je založen na prohledávání grafu do hloubky. Klade se v něm důraz na vybrání uzlu, který má co nejlevnější cenu nejkratší cesty z výchozího uzlu. Protože v tomto uzlu se cena nejlevnější cesty již nemůže změnit (díky nezápornosti cen hran), takže v dalších krocích algoritmu nemusíme v tomto vrcholu testovat trojúhelníkovou nerovnost.

Algoritmus:

Použijeme dvě pole Pu a C, do nichž budeme pro každý uzel u[i] ukládat předposlední uzel a cenu nejkratąí cesty z výchozího uzlu do u[i] . Navíc použijeme dvě pomocná pole S a S' , v níchž budou dosažené a dosud nedosažené uzly.

1. Inicializace - Pu[i] := 0 pro všechna i. C[v] := 0 a C[i] := nekonečno pro všechna i různá od v, kde u[v] je výchozí uzel. S je prázdné pole, S' = V (G)

2. Najdeme vrchol u[x] patřící do S' takový, že C[x] = min{C[k] ; u[k] náleží M}. Jestliže C[x] = nekonečno, potom bod 4. Jinak změníme: { u[x] přidáme do S a S' := S' - u[x] }. Jestliže je nyní S' prázdná, potom bod 4.

Pro každý uzel u[i] z množiny S' a zároveň incidentní s uzlem u[x] provedeme: je-li C[i] > C[x]+c[xi], pak {C[i]=C[x]+c[xi] a Pu[i]=u[x]}. Po prozkoumání všech výše specifikovaných uzlú přejdeme k bodu 2.

4. Konec

Pole Pu nebudeme používat, protože nepotřebujeme znát přesný sled hran které tvoří nejkratší cestu (zjišťujeme nejkratší cestu z výchozího uzlu do všech ostatních). Hodnota MAXFLOT je brána jako nekonečno a předpokládá se, že při výpočtu (sčítání, násobení) tato hodnota nebude dosažena. Dále musíme zkontrolovat zad všechny hrany majínezápornou cenu. Rozdělování uzlů do množin je realizováno pomocí pole s[99] kde hodnota na pozici s[i] určuje zda uzel u[i] patří do množiny S nebo S' (je-li v poli hodnota 0 patří uzel do S' jinak do S).
Pole cen je vyplněno hodnotami MAXFLOAT pouze pro počáteční uzel je hodnota 0 . Dále algoritmus pokračuje podle výše uvedeného postupu.

Algoritmus označí všechny uzly dosažitelné z počátečního a vypíše minimálni cenu za kterou je možno se do uzlu dostat.