AANSLUITINGSPROJECT TUE - VO
startpagina ] omhoog ] opdracht uit kortste weg ] [ gedeelte kortste weg ] kortste weg downloaden ]

 

Een gedeelte uit 
Kun je me de kortste weg vertellen?

2.4  Algoritme van Prim-Dijkstra

Het 'Greedy' Algoritme is makkelijk met de hand toe te passen als je een kleine graaf hebt. Om het door een computer te laten doen is echter moeilijker. Je wilt steeds de kanten ordenen op aflopende lengte en je moet steeds kijken of er geen circuit ontstaat. Door een kleine aanpassing in het "Greedy" Algoritme is dit op te lossen. Het algoritme dat dan overblijft is beter bekend als het Älgoritme van Prim-Dijkstra" en loopt als volgt:
  1. Je maakt eerst een tabel van alle kanten tussen de knopen in je graaf.
  2. Neem nu een willekeurige knoop in je graaf. Deze komt in de boom die je wilt creëren. Stel je kiest B.
  3. Verwijder nu rij B uit je tabel en zoek in kolom B de kleinste waarde op.
  4. Kijk welke knoop bij deze kleinste waarde hoort. Stel dat is knoop C.
  5. Voeg dan kant BC aan je boom toe.
  6. Verwijder rij C uit je tabel en zoek nu in de kolommen B en C naar de kleinste waarde.
  7. Herhaal nu vanaf stap 4, waarbij je steeds bij één kolom meer naar de kleinste waarde moet zoeken.
  8. Als je geen rijen meer over hebt in je tabel heb je een kortste boom gevonden.