Wegsuche

[tuxlan]

Hallo,
ich möchte ein Programm zur Wegsuche programmieren.
Es soll alle möglichen Wege ausgeben! Jedoch finde ich keinen richtigen Ansatz. Kann mir jemand helfen?

Bsp:
----

StadtA|StadtB|StadtC
StadtA - | 50 | -

StadtB 50 | - | 20

StadtC - | 20 | -

etc.

von stadtA nach Stadt C


Ergebnis:
StadtB 50
StadtC 20

[eumops]

Die Entfernungsmatrix ist symmetrisch. Also kannst du eine Hälfte entlang der Hauptdiagonalen ignorieren.

Die x- und die y-Koordinaten der Städte, meinetwegen auch die Namen
speicherst du in einem Array oder sonst einer geeigneten Struktur.

Delphi-Quellcode:

for i := 1 to n do begin
   for j := i to n do begin
       // hier mit x[i],y[i],x[j],y[j] den Satz des Pythagoras anwenden. 
       // In der math-unit gibt's die function hypot() dafür, glaub' ich
   end;
end;

Viel Spass damit ...

[DelphiAndreas]

ob das hier weiterhilft?

http://www.danielgrunwald.de/jufo/2003/pathfinding.php

[ibp]

Zitat:

Zitat von eumops

Die Entfernungsmatrix ist symmetrisch. Also kannst du eine Hälfte entlang der Hauptdiagonalen ignorieren.

... aber nur in diesem speziellen fall, wenn die wege sich jeweils in beide richtungen befahren lassen. sollen auch einbahn-wege berücksichtigt werden, so ist diese matrix nicht mehr symmetrisch!

... wenn du alle möglichen wege durchspielen willst, dann kommst du um einen baumhierarchie nicht herum

... dazu kannst du dir dann auch gleich mal das thema permutationen ansehen...

[eumops]

Zitat:

Zitat von ibp

... aber nur in diesem speziellen fall, wenn die wege sich jeweils in beide richtungen befahren lassen. sollen auch einbahn-wege berücksichtigt werden, so ist diese matrix nicht mehr symmetrisch!

... klar. Aber wie du aus meinem Codeschnippsel erkennen kannst, berücksichtigt mein Vorschlag eh' nur die kürzeste Verbindung zwischen zwei Städten, Richtung ist dann Banane.

[tuxlan]

Hallo!
Vielen Dank, aber ich habe es selber hinbekommen.

Schönen Abend!

tuxlan

[ibp]

und wie?..