Bezorgroute met een naïeve keuze
Een bezorgdienst moet vanaf het depot S een pakket bezorgen bij T. Onderweg zijn er knooppunten A, B, C en D. De directe verbindingen en hun lengte in kilometers zijn: S–A 1, S–B 2, A–B 1, A–C 10, B–C 1, B–D 5, C–T 10 en D–T 2. Andere directe verbindingen bestaan niet. Een nieuwe medewerker stelt een hebberige aanpak voor: kies bij elk knooppunt de kortste nog niet genomen verbinding die naar een nog niet bezocht punt leidt. De planner waarschuwt dat deze aanpak niet altijd de kortste route oplevert. De dienst wil de kortste route kennen en ook weten waar de hebberige aanpak misgaat, zodat de medewerker het algoritme van Dijkstra leert gebruiken.
1. Laat zien welke route de hebberige aanpak oplevert en hoe lang die route is. Begin in S en kies steeds de kortste directe verbinding naar een nog niet bezocht punt.
Read the worked answer
Vanuit S zijn de mogelijkheden S–A=1 en S–B=2; de hebberige keuze is A.
Vanuit A: A–B=1 (A–C=10), dus naar B.
Vanuit B: B–C=1 en B–D=5, dus naar C.
Vanuit C is de enige verbinding naar T: C–T=10.
De route wordt S–A–B–C–T met lengte 1+1+1+10=13 km. De keuze B–C lijkt lokaal één kilometer korter dan B–D, maar C is een doodlopend stuk met een lange verbinding naar T.
2. Bepaal met het algoritme van Dijkstra de kortste route van S naar T. Geef de afstand en de route.
Read the worked answer
Labels vanuit S: S=0; A=1; B=2 (rechtstreeks). Kies A (1): B wordt min(2,1+1)=2, C=1+10=11. Kies B (2): C=min(11,2+1)=3, D=2+5=7. Kies C (3): T=3+10=13. Kies D (7): T=min(13,7+2)=9. Kies T (9).
De kortste afstand is 9 km. De route loopt via T←D←B←S, dus S–B–D–T met lengte 2+5+2=9 km. Omdat B zowel rechtstreeks (2) als via A (1+1=2) op 2 uitkomt, is S–A–B–D–T met lengte 1+1+5+2=9 km ook een kortste route.
3. Leg uit waarom de hebberige aanpak faalt en geef een situatie waarin hij wel de kortste route geeft.
Read the worked answer
De hebberige aanpak kijkt alleen naar de eerstvolgende afstand en negeert de afstand die daarna nog moet worden afgelegd. Daardoor kan een lokaal korte stap (B–C=1) een veel duurdere staart opleveren (C–T=10). Dijkstra houdt voor elk knooppunt de kleinste totale afstand vanaf S bij en herziet die zodra een betere route gevonden wordt; zo wordt de val vermeden.
De hebberige aanpak geeft wel de kortste route als er geen keuzemoment is waar een lokaal korte stap later duur wordt, bijvoorbeeld in een boom: tussen twee punten is er dan maar één route, dus elke vervolgstap ligt noodgedwongen op die route. Ook bij een netwerk waarin alle randen dezelfde richting en vergelijkbare kosten hebben, kan hij goed werken, maar dat is geen garantie.