UBahn Verbindungsnetz für Suchalgorithmus darstellen ?
-
Hallo,
ich möchte gern ein Suchprogramm für ein UBahnnetz schreiben, dass die kürzeste Strecke zwischen Punkt A und B ausgibt. Dazu lese ich sämtliche Bahnstrecken per xml ein. Danach muss ich mir aus den Daten ein sinnvolles Netzwerk anlegen, dass ich mit einem Suchalgorithmus durchsuchen kann.
Das Problem ist nur, wie legt man so ein netzwerk an. hab schon verkettete Liste probiert aber das funktioniert nicht mehr wenn sich Bahnverbindungen überschneiden.
Wenn jemand eine clevere Lösung hat bitte ich um Hilfe.
-
Für dieses Problem gibst die Graphentheorie :o
-
Ja das ist das Paradebeispiel für einen Graphen. Als Suchalgo kannst dann z.B. den Dijkstra verwenden.
-
Danke für den Tipp.
Wo finde ich den Einsteigerfreundliche Erklärungen dazu ?
-
http://www.boost.org/libs/graph/doc/index.html
http://www.boost.org/libs/graph/doc/table_of_contents.html
-