INF_CHR20_VWO_P6_LES-08

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Algoritmes - Short path

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Leerdoelen

Wij gaan het hebben over de algortime van Dijkstra

Wij gaan het hebben over wie Dijkstra is

Wij gaan de stappen van het algortime Dijkstra doornemen

Jij gaat het algoritme van Dijkstra zelf toepassen

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Korste pad Dijkstra

• Het algoritme berekend uit wat de kortste pad is 

      van startpunt tot bestemmingspunt

• Vanzelf sprekend start je bij het startpunt 

     met een startgetal(meestal met het getal 0)

• Het algoritme bekijkt steeds de aanliggende 

     knooppunten (met haar gewogen graaf) vanaf de

     huidige knooppunt

• Een graaf bestaat uit een verzameling punten, 

     knopenpunten genoemd, waarvan deze (sommige) 

     verbonden zijn door lijnen, gewogen graaf is dan niks 

     anders dat de afstand tussen de verzameling punten bekend is

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Wie was Dijkstra?

Was een Nederlandse wiskundige, informaticus. Dijkstra heeft in 1959 een belangrijk algoritme gemaakt. Namelijk het algoritme van Dijkstra (kortst pad algoritme).

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Hoe werkt het algoritme van Dijkstra - 

knooppunten / gewogen graaf

Zoals eerder benoemd hebben wij gewogen graaf. Voor het gemak gebruiken wij afstand als gewogen graaf. In plaats van afstand kan je ook zeggen reiskosten per pad, tijd, enz. eigenlijk alles waar een gewicht aan gehangen kan worden.

knooppunten = { Home, A,B,C,D,E,F, School }

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

De stappen

Bekijk alle knooppunten vanaf H die mogelijk zijn en noteer afstand en herkomst van de knooppunt

zoek goedkoopste knooppunt en ga daarmee verder, noteer deze door hem bijvoorbeeld blauw te maken

Bekijk weer alle knooppunten, tel bij elkaar op en vergelijk welke goedkoper is tov van de vorige

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Opdracht

Bekijk alle knooppunten vanaf H die mogelijk zijn en noteer afstand en herkomst van de knooppunt

zoek goedkoopste knooppunt en ga daarmee verder, noteer deze door hem bijvoorbeeld blauw te maken

Bekijk weer alle knooppunten, tel bij elkaar op en vergelijk welke goedkoper is tov van de vorige

Zoek de kortste pad van a naar g

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Uitwerking opdracht

• Zomerschool
• Site van het Johan de Witt
  
• Aanbod
• Brede school
  
• 
  Zomer College 
• - Klik hier om in te schrijven

Je kan het ook ander doen

Er is ook een andere manier (vergelijkbaar) op de algoritime van Dijkstra uit te werken. 

Deze vind je in het boek fundament online 

Kernprogramma -> B Grondslagen -> Algortimen -> Standaardalgoritme    2.8 Het korstepadalgoritme

Voor de toets dien je het op de manier die het boek uitlegt uit te werken.