[CN] Dijkstra en aanverwanten

[dr_b]

Ik ben toch nog niet helemaal mee met dat algorithme van dijkstra hoor ... Vooral niet bij de oefeningen.
Heeft iemand een idee van de oplossingen voor oefening 3 en 4 bij routing ?

Vraag 3 (eerste zittijd 2005-2006)

Code: Select all

Leg uit met een voorbeeld dat het bij het algoritme van Dijkstra geen verschil maakt welke node je kiest als je op een gegeven moment moet kiezen tussen nodes met gelijke kost

Vraag 4 (eerste zittijd, 2005-2006)

Code: Select all

Een 'routing loop' is een situatie waarbij nodes elkaar als volgende hop beschouwen voor dezelfde bestemming, paketten zouden in een loop tussen de 2 nodes blijven. Als alle nodes in een netwerk Dijkstra toepassen, kunnen er dan routing loops optreden ? Zoja, geef een voorbeeld en verklaar grondig waarom het fout gaat. Zo nee, leg zo volledig mogelijk uit waarom dit niet kan .

Alvast weer nen dikke merci hé,
mzzl

[Michael Cochez]

op vraag 3
volgens mij is dat in het dijkstra algoritme wanneer ge moet gaan kiezen welke node ge toevoegt aan u verzameling van gekende nodes, dan kan het gebeuren dat er twee (of meer) kandidaten zijn (twee of meer met een even kleine waarde) daar moet ge dan een voorbeeld van geven.
op vraag 4
ik denk niet dat zoiets kan voorkomen
elke node zal pakketten via de kortste weg sturen,
stel node A wil naar C en kiest de weg over B,
dan is de kortste weg van B naar C zeker niet over A maar rechtstreeks naar C

[Teun]

Zie ook eens in je wiskunde boek, daar staat meer info. Het eerste is met een voorbeeldje uitwerken, niet echt moeilijk. En bij vraag 4: je hebt naar een node een vastgelegd pad dat je volgt.