Ein Graph ist definiert durch eine Menge von Knoten (Nodes) N, eine Menge von Kanten (Edges) E und eine Funktion Cost (n1,n2) (n1 und n2 sind Knoten) die angibt, wieviel ein Gang von n1 nach n2 kostet, wobei n1 und n2 durch eine Kante aus E verbunden sind...
Als Knoten kannst Du die Zahlen 1...N annehmen. Die Kanten und die Kosten sind als Entfernungsmatrix (1..N, 1..N) definiert.
Ein Weg der Länge X von a nach b wird dann einfach so abgebildet, das die Matrix [a,b] und [b,a] den Wert X enthält. Wenn man nicht von a nach b laufen kann, ist in der Entfernungsmatrix der Wert -1 (oder maxint) eingetragen.
Auf diese Weise kann man auch unterschiedliche Kosten a->b und b->a implementieren. Wenn b auf einem Berg liegt, ist a->b bestimmt teurer als b->a...
Stell Dir Ein Quadrat vor.
Code:
1---2
|\ |
| \ |
| \|
3---4
Die Matrix sieht dann so aus:
Code:
----1 2 3 4
1| - 10 10 14
2| 10 - - 10
3| 10 - - 10
4| 14 10 10 -
10 ist die Entfernung (oder die Kosten), um von 1 nach 2, 2->4, 1->3 und 3->4 zu gelangen. 1-->4 ist hier etwas länger.
Bei Graphen mit vielen Knoten aber verhältnismäßig wenig Kanten ist diese Abbildung nicht optimal, genauergesagt Schrott.
Dann musst du Dir explizit für jeden Knoten die Kanten und die Kosten speichern, z.B. als Array [1..N] Of Array Of int:
Code:
1: (2,10) , (3,10) , (4,14)
2: (1,10) , (4,10)
3: (1,10) , (4,10)
4: (1,10) , (2,10) , (3,10)
Der Aufwand ist etwas größer, aber wesentlich schneller in der Verarbeitung.
Mein Tipp: Mal Dir mal einen kleinen Graphen mit so 5-7 Knoten auf und unterschiedlichen Entfernungen. Dann trommelst du das per 'Const' in ein Test-Programm und spielst damit rum...
Jetzt kannst Du mit einem rekursiven Algorithmus alle Kombinationen durchrechnen und die optimale Route ausgeben.
Zitat
Baum-Darstellung
