Voorspel — waar of niet waar?

Leerdoel: je test wat je van Dijkstra begrijpt, voordat je gaat programmeren.

Lees elke stelling en bedenk je antwoord; klap dan pas open.

Stelling 1

"Aan het begin van Dijkstra staat elke afstand op ?, ook die van de startnode."

Antwoord

Niet waar.

Stap 0 zet alles op ? behalve de start: die krijgt 0, want daar sta je al. Die ene 0 is wat ronde 1 op gang brengt. Zonder die 0 is er niets te kiezen, want alles is even onbekend.

Stelling 2

"De kortste route tussen twee nodes is altijd de directe verbinding, als die bestaat."

Antwoord

Niet waar.

In onze voorbeeldgraph was A → D indirect (geen directe edge), maar zelfs als die wel had bestaan met gewicht 20, dan was A → B → D = 5 nog steeds korter geweest. Een "omweg" kan totaal goedkoper zijn.

Stelling 3

"Als je Dijkstra runt vanuit A, weet je tegelijk de kortste afstand naar alle andere bereikbare nodes."

Antwoord

Waar.

Aan het eind van Dijkstra heb je voor elke bereikbare node de kortste afstand. Eén keer op papier geeft je dus alle antwoorden tegelijk: vijf op de grote graph, vier op de kleine.

Stelling 4

"In een graph waar je elke weg beide kanten op mag, betekent een edge tussen A en B met gewicht 4: van A naar B kost 4, én van B naar A kost 4."

Antwoord

Waar.

Zo'n graph heet niet-gericht, en dat zijn alle graphs in dit hoofdstuk op één na. Er bestaan ook eenrichtingswegen, met desnoods een ander gewicht heen dan terug (spitsuur op één route); bij de fouten zie je zo'n graph, met elke weg apart in de dict.

Stelling 5

"Dijkstra werkt ook met negatieve gewichten."

Antwoord

Niet waar.

Dijkstra leunt op het idee "als een node bekend is, kan zijn afstand niet meer verbeteren". Bij negatieve gewichten klopt dat niet meer — een latere route met een negatieve edge zou alsnog korter kunnen zijn.

Voor negatieve gewichten gebruik je Bellman-Ford.

Stelling 6

"Het is mogelijk dat een node tijdens Dijkstra een kortere afstand krijgt, vóór hij als 'bekend' wordt gemarkeerd."

Antwoord

Waar. Dat is precies wat er met D gebeurde op de kleine graph, in ronde 3.

D had eerst afstand 10, via C. Daarna vond Dijkstra een kortere route via B, afstand 5, en pas daarna werd D bekend. Meerdere kandidaten bekijken voordat je iets klaar verklaart: dat is het hele punt.

Stelling 7

"Zodra de bestemming als 'bekend' is gemarkeerd, staat haar afstand vast — ook al zijn andere nodes nog niet klaar."

Antwoord

Waar.

Bekend is definitief; dat is het sleutelidee van de pen-en-papier-pagina. Wie alleen die ene bestemming nodig heeft, mag daar dus stoppen. In dit hoofdstuk laten we Dijkstra uitlopen, omdat je dan meteen de afstanden naar alle nodes hebt.

Nu de code, in kleine stapjes.

Door naar de graph in Python →.