Du hast ein Spielfeld, ähnlich wie z.B. ein Schachfeld?
Dann sind die Felder die Knoten, und die Übergänge von einem Feld zum Nachbarn die Kanten. Ein Feld hat ja maximal 8 Nachbarn, also hat jeder Knoten maximal 8 Kanten.
Code:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5*| 6*|
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
Feld 5 und 6 sind Hindernisse. Die Kanten sind also
(1,2) (2,3) (1,4) (4,7) (7,8) (8,9)
Wenn man schräg laufen darf, kommen noch (2,4) und (4,8) hinzu.
Wenn man in beide Richtungen laufen darf, dann natürlich auch die Inversen der Kanten.
Nun erstellst Du deine Matrix, wo z.B. E[1,2] = E[2,1] = 1 und E[2,5] = MaxInt ist.
Dann den A* oder jeden anderen "single source minimum Path" Algorithmus auf z.B. auf (3->9) loslassen und schon bist du fertig.
Übrigens kann man damit auch 'Berge' darstellen. Wenn der Weg von 1->4 bergauf geht, dann ist E[1,4] > E[4,1]. Der A* Algorithmus findet dann den Weg, der am wenigsten anstrengend ist.
Zitat
Baum-Darstellung
