WisFaq!

Kortste paden

Kan iemand mij helpen bij deze vraag?

Stel dat we een kralen/touwtjes model van een gewogen graaf hebben, waarvan de gewichten juist de lengtes van de touwtjes zijn. Er is dan een aardige manier om zonder grafentheorie het kortste pad tussen 2 punten te vinden. Welke?

Zou het algoritme ook weren bij gerichte grafen? Hoe moet het worden aangepast?

Alvast bedankt!
Groeten

johan
7-12-2010

Antwoord

Neem een van de twee kralen in je linkerhand en de andere in je rechterhand en spreid je handen uit elkaar totdat het kralentouwtjesmodel tussen je twee handen strak gespannen staat.
De touwtjes en kralen van het kortste pad liggen dan op de rechte lijn van je linkerhand naar je rechterhand.
(Als je je handen niet ver genoeg kunt spreiden, zul je hulphandjes moeten gebruiken.)

Dit algoritme werkt niet altijd voor gerichte grafen, want het kan zijn dat een van de touwtjes op de lijn van je linkerhand naar je rechterhand in de andere richting moet worden doorlopen.
Misschien moet je zo'n verkeerd gericht touwtje, gericht van kraal A naar kraal B, vervangen door een nieuw en even lang touwtje, gericht van kraal A naar een extra kraal B', plus touwtjes met de goede overeenkomstige lengtes van B' naar alle kralen waar vanuit B een touwtje naar toe gaat, en het dan nog eens opnieuw met strekken proberen?

hr
23-12-2010