Dijkstrův algoritmus
Z Wikipedie, otevřené encyklopedie
Dijkstrův algoritmus slouží k nalezení nejkratší cesty v grafu. Patří mezi grafové algoritmy. Lze o něm říci, že je konečný, protože v každém průchodu jeho cyklem se do množiny navštívených uzlů přidá právě jeden uzel. Průchodů cyklem je nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno převést), v grafu se však nesmí vyskytnout záporné hodnoty.
Jeho autorem byl nizozemský informatik Edsger Dijkstra.
[editovat] Popis algoritmu
Mějme graf G, v němž hledáme nejkratší cestu. Řekněme, že V je množina všech vrcholů grafu G a množina E obsahuje všechny hrany grafu G. Algoritmus pracuje tak, že si pro každý vrchol v z V pamatuje délku nejkratší cesty, kterou se k němu dá dostat. Označme tuto hodnotu jako d[v]. Na začátku mají všechny vrcholy v hodnotu d[v]=∞, kromě počátečního vrcholu s, který má d[s]=0. Nekonečno symbolizuje, že neznáme cestu k vrcholu.
Dále si algoritmus udržuje množiny Z a N, kde Z obsahuje už navštívené vrcholy a N dosud nenavštívené. Algoritmus pracuje v cyklu tak dlouho, dokud N není prázdná. V každém průchodu cyklu se přidá jeden vrchol vmin z N do Z, a to takový, který má nejmenší hodnotu d[v] ze všech vrcholů v z N.
Pro každý vrchol u, do kterého vede hrana (označme její délku jako l(vmin,u)) z vmin, se provede následující operace: pokud (d[vmin] + l(vmin,u)) < d[u], pak do d[u] přiřaď hodnotu d[vmin] + l(vmin,u), jinak neprováděj nic.
Až algoritmus skončí, potom pro každý vrchol v z V je délka jeho nejkratší cesty od počátečního vrcholu s uložena v d[v].
[editovat] Externí odkazy
- Nejkratší cesta v ohodnoceném grafu - popis Dijkstrova algoritmu
- Halda, Dijkstrův algoritmus
