Bouwsteen 2 — de tabel

Hier bouw je op verder: Dictionaries en Sets

Weet je dit niet meer zeker? Lees het terug voordat je verdergaat.

• Python Dictionaries
• Python Sets

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:

node	bekend?	afstand
A	ja	0
B	nee	4
C	nee	2
D	nee	?

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 →.