nicht angemeldet
Hallo alle miteinander,
ich sitze gerade an einem relativ kniffligen Problem. Ich möchte auf einer Stadtkarte zwischen zwei beliebigen Punkten den schnellsten weg ermitteln.
Hierzu habe ich in einer Mysql-Datenbank Pfadangaben gemacht. Die bestehen aus diversen Knotenpunkten, die mit x und y Koordinaten auf der Karte liegen und zu ihren jeweiligen Nachbarn verlinkt sind.
Also ein Knotenpunkt hat die Informationen:
*ID
*x-wert
*y-wert
*unmittelbar erreichbare Nachbar-ID's
Mein momentaner Algorithmus ist nicht so der Bringer, produziert ab und an mal Endlosschleifen und gibt nicht den kürzesten weg aus.
Jetzt möchte ich eben gerne den Dijkstra-Algorithmus für PHP programmieren, hab aber selber leider nicht so viel Ahnung von diesem Algorithmus.
Ich hatte eben die Hoffnung, das mir hier jemand dabei etwas behilflich sein könnte. Oder vielleicht gibt es sowas schon fertig für PHP?
Auf der Seite ist mal mein aktuelles Beispiel-skript mit den Wegpunkten aus der Datenbank.
Aber wie gesagt führen manche Kombinationen noch zu Endlosschleifen.
Am besten probiert ihr mal eine Berechnung von 5 nach 15.
Danke für jede Hilfe.