Wat is een graph?

Leerdoel: je weet wat een graph, een pad en een gewicht zijn. Nog geen code; eerst tekeningen en woorden.

Het verhaal

Je hebt een navigatie-app. Je tikt in waar je heen wilt. Wat doet hij?

Hij berekent welke route de kortste totale tijd kost.

Niet zomaar een route, maar de snelste, en dat kan hij bewijzen. Dat is wat het algoritme van Dijkstra doet. Om het te bouwen moet je eerst weten hoe een wegennet eruitziet als je het in een computer stopt.

Drie nieuwe woorden

       4
   A ─────── B
   │         │
   2         1
   │         │
   C ─────── D
       8

Wat zie je?

De letters A, B, C en D zijn nodes: knopen, of op een routekaart plaatsen.
De strepen ertussen zijn edges, de verbindingen. Op een routekaart zijn dat wegen.
De getallen op de strepen zijn gewichten: wat het kost om die verbinding te gebruiken. Dat kan afstand zijn, tijd of geld; hier lees je het als minuten.

Samen heet zo'n plaatje een graph. In het Nederlands is dat een graaf, maar iedereen zegt graph, dus wij ook. Een graph met gewichten heet een gewogen graph.

Wat is een pad?

Een pad is een rijtje nodes waar je achter elkaar doorheen loopt, en elk paar dat na elkaar komt moet met een edge verbonden zijn.

Drie mogelijke paden van A naar D:

A → B → D met gewichten 4 + 1 = 5.
A → C → D met gewichten 2 + 8 = 10.
A → C → A → B → D mag ook, maar heen en terug over dezelfde weg maakt een pad alleen langer: 2 + 2 + 4 + 1 = 9.

De kortste (laagste totaal-gewicht) is A → B → D = 5.

Niet altijd intuïtief: C ligt het dichtst bij A (2), maar vanaf C is de weg naar D lang (8). De duurdere eerste stap naar B (4) wint, omdat B vlak bij D ligt (1).

Gewichten zijn niet altijd letterlijk afstanden

Een gewicht is wat een stap je kost, en wat dat is hangt af van je probleem:

Wat is je graph?	Wat is een gewicht?
Steden + snelwegen	Aantal km of reistijd
Vluchten	Prijs in euro
Computernetwerk	Vertraging in milliseconden
Eiland-vleksprongen	Energie die het kost

Dijkstra geeft niets om wat de gewichten betekenen. Hij wil alleen het totaal zo laag mogelijk hebben.

Eén belangrijke aanname

Dijkstra werkt alleen met positieve gewichten. Geen negatieve, geen weg die je tijd oplevert in plaats van kost. Voor negatieve gewichten bestaat een ander algoritme, Bellman-Ford, en dat doen we hier niet.

Wat we gaan leren

Dijkstra beantwoordt één vraag: vanaf deze startnode, wat is de kortste afstand naar elke andere node? Alle bestemmingen in één keer, niet één per keer. Hoe hij dat doet, voer je eerst zelf uit met pen en papier, voordat je een letter Python schrijft.

Video

Het algoritme stap voor stap uitgetekend (Engels gesproken):

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.

Door naar pen en papier →.

Het verhaal​

Drie nieuwe woorden​

Wat is een pad?​

Gewichten zijn niet altijd letterlijk afstanden​

Eén belangrijke aanname​

Wat we gaan leren​

Video​

Zo bouw je het op​