Kortste pad in een graaf
- Auteur:
- chris cambré
Wat is het kortste pad tussen de punten A en G als je de verbindingen in de graaf moet volgen.
Versleep een of meerdere punten en zie zie hoe het pad zich aanpast.
aantal bogen of totale afstand?
aantal bogen of totale afstand?
GeoGebra heeft twee opties om het kortste pad te berekenen tussen twee knopen:
KortsteAfstand( <Lijst met lijnstukken>, <Startpunt>, <Eindpunt>, <Boolean gewogen> )
- KortsteAfstand({f, g, h, i, l, k, l, m, n}, A , G, false ) geeft het pad aan dat langs zo weinig mogelijk knopen passeert. Toepassing: Hoe neem ik de metro van ... naar ... met zo weinig mogelijk overstappen.
- KortsteAfstand({f, g, h, i, l, k, l, m, n}, A , G, true) geeft het pad aan waarbij de totale afstand van de lijnstukken in de constructie minimaal is. Toepassing: Wat is het kortste wandeltraject van ... naar ...
lengte of gewicht?
GeoGebra werkt zuiver meetkundig en kan enkel rekenen met de lengte van lijnstukken als maatgetal.
Het verslepen van knopen wijzigt de situatie en leidt tot andere oplossingen, wat atypisch is voor grafen.
Kortste pad opgaven worden dan ook meestal voorgesteld en opgelost door niet met de lengtes van de bogen te rekenen, maar de bogen een gewicht toe te kennen. We spreken dan van gewogen grafen.
Zo zijn in figuur 1 de bogen getekend volgens de lengte van de lijnstukken, terwijl figuur 2 een overzichtelijke graaf is waarin de lengte van de getekende lijnstukken losstaat van het gewicht van de bogen.
Dit is ook wat in de praktijk gebeurt. Een web van lijnstukken is immers veel te rigide om reële wegentracés en afstanden te tekenen. Met drie knopen lukt het nog, maar verder zullen de lijnstukken niet meer sluiten, zodat je wel met gewichten moet werken i.p.v. met lijnstukken waarvan de lengtes evenredig zijn met de reële afstanden.
Werk je met gewichten, dan doet de lengte van de bogen in de graaf er niet meer toe. Zo kan bv. een gps het verschil maken tussen de kortste en de snelste route tussen twee plaatsen door rekening te houden met de aard van de weg en trajecten waar je een hogere of lagere snelheid kunt verwachten. Bijkomend kan je flexibel inspelen op tijdelijke veranderingen in de verkeerssituatie door de gewichten van de bogen tijdelijk te wijzigen.