kürzeste Wege |
| 19.05.2004, 17:05 | Maesta | Auf diesen Beitrag antworten » |
| kürzeste Wege Komme mit der einen Aufgabe nicht klar, hoffe mir kann vielleicht jemand helfen. Man möchte in einem Graphen einen kürzesten Weg vom Start zum Ziel bestimmen. Es stehen jedoch drei mögliche Startknoten s1, s2, s3 und drei mögliche Endknoten t1, t2, t3 zur Verfügung. Wie findet man am effektivsten den kürzesten Weg? (Eine Möglichkeit wäre 9 Wege zu bestimmen und diese zu vergleichen, doch dies ist nicht effektiv genug. Es sollte die Bestimmung eines kürzesten Weges reichen). Aber wie? Hilft einem vielleicht der Dijkstra-Algorithmus weiter? |
||
| 19.05.2004, 17:09 | SirJective | Auf diesen Beitrag antworten » |
Ja, Dijkstra hilft weiter: Setze einfach alle drei Startknoten auf Distanz 0, und fuehre den Algorithmus aus, bis du einen der drei Zielknoten erreichst. Diese Erweiterung des Algorithmus ist ja richtig nett. Der Aufwand steigt hoechstens proportional zur Anzahl der Ziele, nicht mit der Anzahl der Starts. Wenn du also mal ein Problem mit 2 Startfeldern und 10 Zielfeldern hast, dann beginnst du am besten bei den Zielen und gehst zu den Startfeldern. Gruss, SirJective |
||
| 21.05.2004, 20:45 | Maesta | Auf diesen Beitrag antworten » |
"Setze einfach alle drei Startknoten auf Distanz 0, und fuehre den Algorithmus aus, bis du einen der drei Zielknoten erreichst." Wie meinst du das? Kannst das vielleicht ein wenig ausführlicher erklären? |
||
| 21.05.2004, 22:22 | m00xi | Auf diesen Beitrag antworten » |
Hiho Maesta. Schau doch einfach mal bei google nach Dijkstra und schau dir den Algorithmus an, die Veränderung ist minimal und du bist bei deinem gewünschten Effekt. Gruß Hanno |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
