De reisplanner

We vertrekken naar de zee. We hebben 2 verschillende reisplanners geraadpleegd en kregen volgende reisplanners aangeboden.

reisplanner 1

Antwerpen V: 8:29

Mechelen A: 10:29

Mechelen V: 10:52

Brussel A: 11:06

Brussel V: 11:10

Oostende A: 12:45

Reistijd: 4 uur en 25 minuten

2 keer overstappen

prijs: 31 euro 10

reisplanner 2

Antwerpen V: 8:53

Gent A: 9:13

Gent V: 9:16

Zandhoven A: 10:03

Zandhoven V: 10:26

Diksmuide A: 11:17

Diksmuide V: 11:22

Oostende A: 13:15

Reistijd: 4 uur 22 minuten

3 keer overstappen

prijs 31 euro 10

Werking reisplanner?

Kortste, snelste en goedkoopste route?

tussen 2 punten

Deze methode heet het algoritme van Dijkstra, genoemd naar de bedenker E.W. Dijkstra.

opdracht 20

In de schematische weergave uit figuur 36 met zeven plaatsen, A tot en met G, ligt een bepaald logistiek netwerk d, dat tevens af te lezen is uit figuur 36. De precieze betekenis ervan is niet zo relevant. Bij de verbindingen is de afstand aangegeven in kilometers.

figuur 36

Bepaal:

a. De kortste route van A naar C:

b. De kortste route van C naar G:

c. De kortste route van B naar G: 

d. De kortste route van D naar G:

opdracht 21

Bepaal:

a. De goedkoopste route van A naar C:

b. De goedkoopste route van C naar G:

c. De goedkoopste route van B naar G:

d. De goedkoopste route D naar G:

In elke samenhangende gewogen graaf met positieve gewichten is de kortste route tussen twee punten een pad. We definiëren de afstand tussen twee punten als de som van de gewichten van zo'n pad.