Hieronder geven we een voorbeeld van een algoritme voor het bepalen van het kortste pad tussen twee punten in een graaf. Dit algoritme is een "klassieker"; het is ruim 50 jaar gelden (1959) gepubliceerd door de Nederlandse informaticus Edsger Dijkstra. Zie: http://nl.wikipedia.org/wiki/Edsger_Dijkstra. De tekst van deze publicatie is in de bijlage te vinden.
Opgave. Hoe klassiek is dit algoritme? Zoek bijvoorbeeld op internet naar "shortest path algorithm", en kijk hoe vaak je het algoritme van Dijkstra tegenkomt. Of, zoek in een willekeurig boek over algoritmen.
Een uitleg van dit algoritme is bijvoorbeeld te vinden op Wikipedia, zie http://nl.wikipedia.org/wiki/Kortste_Pad_Algoritme.
Op het web zijn ook de nodige animaties van dit algoritme te vinden, zie bijvoorbeeld: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml.
Hieronder geven we een uitleg van het algoritme, met een implementatie in de programmeertaal Python. We geven de uitleg, en de implementatie in twee stappen. De eerste versie is bedoeld als een vereenvoudigde opstap naar het uiteindelijke algoritme.
Dit algoritme bepaalt voor alle punten in de graaf wat hun kortste afstand is tot een gegeven beginpunt. Daarmee wordt ook het oorspronkelijke probleem opgelost, de kortste afstand tussen dit beginpunt en een bepaald eindpunt. Het probleem dat opgelost wordt is algemener dan dit oorspronkelijke probleem; maar, er is geen algoritme bekend dat het oorspronkelijke probleem efficiënter oplost dan dit algemenere probleem. Dit is een situatie die wel vaker voorkomt bij het oplossen van problemen, niet alleen in de informatica: je lost een specifiek probleem op door een algemener probleem op te lossen.
Een belangrijke observatie met betrekking tot het kortste pad van punt P naar punt Q in een graaf is dat voor elk tussenliggend punt R op dit pad geldt dat het kortste pad van P naar R een beginstuk is van het kortste pad van P naar Q. Bovendien is de kortste afstand van P naar R ten hoogste (<=) de kortste afstand van P naar Q, omdat de lengtes van alle verbindingen niet-negatief is.
De essentie van het algoritme is dat we voor alle punten in de graaf de kortste afstand tot P bepalen, in volgorde van opklimmende lengte van het kortste pad.
In het onderstaande bedoelen we met de kortste afstand van een punt steeds de kortste afstand van P naar dat punt.
De punten V van de graaf verdelen we in twee verzamelingen:
Alle punten in A liggen dichter bij (<=) P dan alle punten in V-A; deze eigenschap proberen we in stand te houden bij elke stap waarin we een punt van V-A naar A verhuizen. Zo'n eigenschap heet ook wel een invariant van het algoritme; vaak is het vinden van een goede invariant de essentie van het vinden van een algoritme.
In de begintoestand bevat A alleen het startpunt P; merk op dat we dan op een triviale manier aan de invariante eigenschap voldoen.
Als we in elke stap van het algoritme een punt van V-A naar A verhuizen, zal A uiteindelijk alle punten in V bevatten, en is V-A leeg: dan zijn we klaar, omdat we voor alle punten in V de kortste afstand tot P bepaald hebben. Hiermee hebben we ook aangetoond dat het algoritme eindigt; dit is een belangrijke eigenschap, die niet altijd zo eenvoudig aan te tonen is.
Om de genoemde eigenschap in stand te houden, moeten we het punt R in V-A met de kortste afstand (tot P) verhuizen van V-A naar A. (Eigenlijk "een punt", niet "het punt": er kunnen meerdere punten zijn met dezelfde afstand.)
Om het punt in V-A met de kortste afstand enigszins efficiënt te kunnen vinden, houden we van alle punten in A bij wat hun kortste afstand is. We kunnen dan de kortste afstand bepalen van elk punt R in V-A dat een directe verbinding heeft naar een of meer van de punten in A.
Op basis van deze analyse komen we tot een eerste versie van het algoritme zoals dat hieronder beschreven staat (zie kortste pad 0)
Deze versie is nog niet de versie zoals die door Dijkstra gepubliceerd is; we kunnen het algoritme nog efficiënter maken.
Hiervoor gebruiken we de volgende observaties:
Wat deze laatste eigenschap betreft, moeten we extra werk (functie relax) doen als we een punt R verhuizen van X naar A: voor alle uitgaande verbindingen van R die naar een punt Q buiten A wijzen, moeten we de bestemming eventueel toevoegen aan de verzameling X; bovendien bepalen we voor deze bestemmingen de lengte van het kortste pad via R, en passen we eventueel de "voorlopig kortste afstand" aan, als het pad via R korter is.
Dit resulteert in de tweede versie van het algoritme; zie kortste pad 1
Opgave. We laten deze twee versies van het algoritme op een aantal grafen los - de invoer staat aan het begin van de algoritmen. Door middel van enkele toegevoegde operaties kunnen we bijhouden hoeveel stappen het algoritme nodig heeft. Bepaal voor deze verschillende grafen wat het aantal stappen is dat het algoritme nodig heeft (zoals het algoritme dit zelf aangeeft).
Een verbetering die vaak toegepast wordt, is dat in plaats van een verzameling X, een "priority queue" gekozen wordt, waarin de elementen geordend zijn op toenemende "voorlopig kortste afstand". Het selecteren van punt R met minimale afstand is dan triviaal; het bijwerken van de bestemmingen van R buiten A, die mogelijk al in de priority queue opgenomen zijn of nog toegevoegd moeten worden, is dan wat bewerkelijker: als hun "voorlopig kortste afstand" verandert, moeten ze mogelijk naar een andere positie in de priority queue verhuizen.
(Een uitleg van dit algoritme is ook te vinden in de video-colleges van MIT, zie: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm)