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



  • 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


Log in to reply