OR1 – Week 3 - Aantekeningen
Kortste paden en minimale opspannende bomen
Inhoud
Wat is een netwerk?......................................................................................................... 1
Eén netwerk, verschillende vragen ............................................................................ 2
Dijkstra: idee en stappenplan ..................................................................................... 2
Dijkstra uitgewerkt: labeling en tabel ................................................................... 3
Bomen en opspannende bomen ................................................................................... 3
Minimale opspannende boom en Prim........................................................................ 4
Kortste pad versus minimaal opspannende boom ............................................... 5
Verdieping: negatieve kanten, Kruskal en complexiteit ...................................... 5
Key Terms ........................................................................................................................... 7
Een netwerk is een graaf met een niet-negatief geheel getal per tak. Met
één dergelijke graaf kun je verschillende optimalisatievragen modelleren –
van de snelste route tot het goedkoopste elektriciteitsnetwerk – zonder
elke mogelijke route handmatig te hoeven uitproberen.
Wat is een netwerk?
• Knoop (node): een punt in de graaf (bijv. O, A, …, T).
• Tak (edge): een verbinding tussen twee knopen met een gewicht ≥ 0
(bijv. OA = 2).
• Pad: een opeenvolgende reeks knopen; de lengte is de som van de
takgewichten.
• Circuit: een pad dat bij zijn beginknoop eindigt en minstens één tak
bevat.
• Ongericht vs. gericht: in dit vak ongerichte netwerken, d.w.z. takken
hebben geen richting.
• Verbonden: tussen elke twee knopen bestaat een pad.
Netwerk – een graaf waarbij elke tak een niet-negatief geheel getal
(gewicht) heeft.
Brute-force “alle routes nalopen” groeit exponentieel met |V| + |E| en is
onpraktisch voor grote netwerken; daarom gebruiken we efficiënte
algoritmen.
1
, Eén netwerk, verschillende vragen
Het voorbeeldnetwerk Seervada Park (Hillier & Lieberman) heeft knopen O,
A–E en T. Met dezelfde graaf kun je:
• Kortste route van O naar T vinden.
• Goedkoop leidingnetwerk (opsomming van takken die alle knopen
verbinden) ontwerpen.
• Rittenverdeling plannen zodat de natuur zo min mogelijk wordt
verstoord.
Deze drie vragen illustreren hoe één graaf verschillende OR-modellen
ondersteunt.
Dijkstra: idee en stappenplan
1. Oplossingen (solved) = knopen waarvan de kortste afstand
definitief is; onopgelost = rest.
2. Per iteratie kiest men één kandidaat per opgeloste knoop: de
dichtstbijzijnde onopgeloste buur.
3. Voor elke kandidaat wordt totale afstand = kortste afstand tot de
opgeloste knoop + gewicht van de verbindingskant berekend.
4. De kandidaat met de kleinste totale afstand wordt de volgende
opgeloste knoop; bij gelijke totalen (ties) kunnen meerdere knopen
tegelijk worden gekozen.
DIJKSTRA(G, w, s)
for v in V: d[v]=∞, pred[v]=NIL
d[s]=0; Q = priority queue met alle knopen
while Q ≠ ∅:
u = EXTRACT - MIN(Q) // kleinste voorlopige afstand
for (u,v) in E:
if d[v] > d[u] + w(u,v):
d[v] = d[u] + w(u,v)
pred[v] = u
DECREASE - KEY(Q, v, d[v])
Het algoritme vereist niet-negatieve takgewichten; anders kan een
eerder “definitieve” label later nog verbeteren.
2
Kortste paden en minimale opspannende bomen
Inhoud
Wat is een netwerk?......................................................................................................... 1
Eén netwerk, verschillende vragen ............................................................................ 2
Dijkstra: idee en stappenplan ..................................................................................... 2
Dijkstra uitgewerkt: labeling en tabel ................................................................... 3
Bomen en opspannende bomen ................................................................................... 3
Minimale opspannende boom en Prim........................................................................ 4
Kortste pad versus minimaal opspannende boom ............................................... 5
Verdieping: negatieve kanten, Kruskal en complexiteit ...................................... 5
Key Terms ........................................................................................................................... 7
Een netwerk is een graaf met een niet-negatief geheel getal per tak. Met
één dergelijke graaf kun je verschillende optimalisatievragen modelleren –
van de snelste route tot het goedkoopste elektriciteitsnetwerk – zonder
elke mogelijke route handmatig te hoeven uitproberen.
Wat is een netwerk?
• Knoop (node): een punt in de graaf (bijv. O, A, …, T).
• Tak (edge): een verbinding tussen twee knopen met een gewicht ≥ 0
(bijv. OA = 2).
• Pad: een opeenvolgende reeks knopen; de lengte is de som van de
takgewichten.
• Circuit: een pad dat bij zijn beginknoop eindigt en minstens één tak
bevat.
• Ongericht vs. gericht: in dit vak ongerichte netwerken, d.w.z. takken
hebben geen richting.
• Verbonden: tussen elke twee knopen bestaat een pad.
Netwerk – een graaf waarbij elke tak een niet-negatief geheel getal
(gewicht) heeft.
Brute-force “alle routes nalopen” groeit exponentieel met |V| + |E| en is
onpraktisch voor grote netwerken; daarom gebruiken we efficiënte
algoritmen.
1
, Eén netwerk, verschillende vragen
Het voorbeeldnetwerk Seervada Park (Hillier & Lieberman) heeft knopen O,
A–E en T. Met dezelfde graaf kun je:
• Kortste route van O naar T vinden.
• Goedkoop leidingnetwerk (opsomming van takken die alle knopen
verbinden) ontwerpen.
• Rittenverdeling plannen zodat de natuur zo min mogelijk wordt
verstoord.
Deze drie vragen illustreren hoe één graaf verschillende OR-modellen
ondersteunt.
Dijkstra: idee en stappenplan
1. Oplossingen (solved) = knopen waarvan de kortste afstand
definitief is; onopgelost = rest.
2. Per iteratie kiest men één kandidaat per opgeloste knoop: de
dichtstbijzijnde onopgeloste buur.
3. Voor elke kandidaat wordt totale afstand = kortste afstand tot de
opgeloste knoop + gewicht van de verbindingskant berekend.
4. De kandidaat met de kleinste totale afstand wordt de volgende
opgeloste knoop; bij gelijke totalen (ties) kunnen meerdere knopen
tegelijk worden gekozen.
DIJKSTRA(G, w, s)
for v in V: d[v]=∞, pred[v]=NIL
d[s]=0; Q = priority queue met alle knopen
while Q ≠ ∅:
u = EXTRACT - MIN(Q) // kleinste voorlopige afstand
for (u,v) in E:
if d[v] > d[u] + w(u,v):
d[v] = d[u] + w(u,v)
pred[v] = u
DECREASE - KEY(Q, v, d[v])
Het algoritme vereist niet-negatieve takgewichten; anders kan een
eerder “definitieve” label later nog verbeteren.
2
