Nederlands
Menu

Datastructuren en algoritmen

Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?

  1. ADe graaf heeft geen cykels (paden die naar dezelfde knoop terugkeren)
  2. BDe kanten hebben geen richting
  3. CAlle gewichten van de kanten zijn 0 of groter
Antwoord en toelichting tonen

Antwoord: C. Alle gewichten van de kanten zijn 0 of groter

Het algoritme van Dijkstra legt de nog niet vastgelegde knoop met de kleinste afstand vast. Dat berust op de aanname dat een omweg via andere knopen een afstand alleen kan vergroten en nooit verkleinen. Met een kant met negatief gewicht kan een afstand later via een andere route korter worden: in een gerichte graaf met S→A 2, S→B 3 en B→A −2 wordt A vastgelegd op 2, voordat het pad S→B→A met lengte 1 wordt gevonden. Bij negatieve gewichten worden methoden zoals het algoritme van Bellman-Ford gebruikt. Het algoritme van Dijkstra werkt ook met cykels en met gerichte kanten, zolang alle gewichten 0 of groter zijn.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. 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)?
  2. 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?
  3. 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?
  4. 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?
  5. Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?