Ga naar hoofdinhoud

Bouwsteen 2 — de tabel

Hier bouw je op verder

Leerdoel: je vertaalt de twee kolommen van je papieren tabel naar Python: een dict afstanden en een set bezocht.

Wat we willen​

Op papier zag je tabel er na ronde 1 van de kleine graph zo uit:

nodebekend?afstand
Aja0
Bnee4
Cnee2
Dnee?

In Python worden dat twee dingen: een dict afstanden van node naar zijn huidige beste afstand, en een set bezocht met de nodes die al bekend zijn. Twee dingen, omdat het twee vragen zijn: wat is je beste afstand, en ben je al klaar.

Hoe schrijf je "onbekend" als getal?​

Op papier schreef je ? voor onbekend. Python heeft daar geen teken voor, maar wel float('inf'):

oneindig = float('inf')
print(oneindig)
print(oneindig > 999999)

float('inf') is oneindig groot. Je kunt ermee rekenen en vergelijken, en elke route die je vindt is er kleiner dan. Dat is precies wat "afstand nog onbekend" moet doen.

Stap 0: initialiseren​

Dit is stap 0 van je tabel, in code. ? op papier is float('inf') hier; de 0 bij de start is dezelfde 0:

afstanden = {'A': 0, 'B': float('inf'), 'C': float('inf'), 'D': float('inf')}
bezocht = set()
  • De startnode krijgt 0, want daar staan we al.
  • Alle andere nodes krijgen inf: nog niets ontdekt.
  • bezocht is leeg, want aan het begin is niemand klaar.

Dit algemener schrijven​

Dit moet ook werken als de graph er anders uitziet dan A, B, C, D. Begin daarom met een lege dict en vul hem met een for-loop:

afstanden = {}
for node in graph:
    afstanden[node] = float('inf')
afstanden[start] = 0

Voor elke node in de graph komt er een sleutel met waarde inf; daarna gaat de start op 0.

Voorspel​

Wat denk je dat dit print?

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1)],
    'C': [('A', 2), ('D', 8)],
    'D': [('B', 1), ('C', 8)],
}
start = 'A'

afstanden = {}
for node in graph:
    afstanden[node] = float('inf')
afstanden[start] = 0
bezocht = set()

print(afstanden)
print(bezocht)
Antwoord
{'A': 0, 'B': inf, 'C': inf, 'D': inf}
set()

Een lege set print Python als set(), en oneindig als inf.

Run​

Python
Code-omgeving wordt voorbereid…

Iets aan bezocht toevoegen​

Van een set hebben we maar twee dingen nodig: iets erin zetten, en vragen of iets erin zit.

bezocht = set()
bezocht.add('A')
print('A' in bezocht)   # True
print('B' in bezocht)   # False

Daarmee is de boekhouding op orde.

Wat nu nog mist​

Alle afstanden staan op oneindig, op de start na. Ze bijwerken aan de hand van de buren is de relax-stap.

Door naar bouwsteen 3: relax een buur →.