Die am weitesten entfernte Stadt finden

Hellraiser

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

Ivo

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

Hellraiser

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ählen

Hellraiser

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.

knivil

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.

Hellraiser

super, jetzt weiss ich wenigstens was ich mir ansehen muss, danke.

Das werd ich mir gleich mal durchsehen und versuchen in C umzusetzen

Hellraiser