Nederlands
Menu

Datastructuren en algoritmen

In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?

  1. AS→A→C→T, lengte 8
  2. BS→B→A→C→T, lengte 7
  3. CS→B→C→T, lengte 9
Antwoord en toelichting tonen

Antwoord: B. S→B→A→C→T, lengte 7

Het algoritme van Dijkstra legt herhaaldelijk de dichtstbijzijnde knoop vast waarvan de afstand nog niet definitief is, en werkt de afstanden van haar buren bij. Vanuit S (0) wordt B vastgelegd op 1, en via B krijgt A de afstand 1 + 2 = 3, korter dan de directe 4. Na het vastleggen van A (3) krijgt C de waarde 3 + 1 = 4 en T de waarde 3 + 6 = 9, en na het vastleggen van C (4) wordt T bijgewerkt tot 4 + 3 = 7. Het kortste pad is dus S→B→A→C→T met lengte 7. S→A→C→T (8) is langer omdat het S−A rechtstreeks neemt, en S→B→C→T (9) is langer omdat B−C het grote gewicht 5 heeft.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?
  2. Voor de taken A tot E gelden de volgordebeperkingen „A vóór C”, „B vóór C”, „C vóór D”, „B vóór E” en „E vóór D”. Welke volgorde voldoet aan alle beperkingen (een resultaat van topologisch sorteren)?
  3. Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?
  4. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?
  5. Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?