Die am weitesten entfernte Stadt finden
-
Hallo
Ich soll ein Programm schreiben, das über eine Datei Städte einliest und auch Strassen sollen eingelesen werden. Dann soll das Programm die am Weitesten entfernte Stadt finden (vom der Ausgangsstadt aus gesehen). Wenn es mehrere Strassen gibt soll man immer den kürzesten verwenden um weiter zu kommen.
Das einlesen und in Stukturen zu verteilen ist nicht das Problem nur bei der Suche hänge ich nun und weiss nicht mehr weiter.
Kann mir hier wer weiterhelfen
mfg
Hellraiser
-
Ohne irgendwelche Information, zum Beispiel die UTM / GPS Koordinaten, wirst Du da nicht weit kommen.
Du kannst Dir dann z.B. einen Datensatz wie diesen anlegen:Hamburg xx xx xx xx Lohore xx xx xx xx Nha Trang xx xx xx xx Zugspitze xx xx xx xx
Dann gibts Du Deinen Ort ein und kannst es berechnen.
Viel Spass
-
Naja es sind keine GPs Daten die Daten für die Strassen sehen so aus
1 3 135 (von Stadt nach Stadt KM)
und die Stadt sieh so aus
1 Salzburg 149355 1 424 (ID Stadtname Einwohner GebietID Meereshöhe)
Sind mal 2 kleine Beispiele
Das einlesen ist kein Problem, ich scheitere einfach am Algorithmus, denn ich muss ja für alle Städte die Wege berechnen und dann den längsten auswählenHellraiser
-
du könntest dir mal z.b. den dijkstra- oder prim-algorithmus (zur errechnung des kürzesten weges) anschauen und entsprechend umstricken um auf den größten weg zu kommen. es gibt sicherlich noch bessere algorithmen, aber die zwei sind relativ verständlich und könntest du hier sicherlich anwenden.
-
Du berechnest den kuerzesten Weg von der Ausgangsstadt zu allen anderen Staedten und vergleichst diese dann. Ein Weg ist z.B. durch A*. Die Verbindung zwischen den Staedten kannst du z.B. durch eine Adjazenzmatrix mit den entsprechenden Kantengewichten darstellen und so damit einfach arbeiten.
-
super, jetzt weiss ich wenigstens was ich mir ansehen muss, danke.
Das werd ich mir gleich mal durchsehen und versuchen in C umzusetzen
Hellraiser