Bellmann-Ford-Algorithmus (alphabetisch) |
10.07.2013, 20:13 | manni_12345 | Auf diesen Beitrag antworten » |
Bellmann-Ford-Algorithmus (alphabetisch) ich beschäftige mich im Moment mit dem folgenden Graphenproblem: [attach]30903[/attach] Hierbei soll ich die kürzesten Wege vom Knoten A (Quellknoten) zu den anderen Knoten ermitteln. Die Lösung soll mithilfe eines geeigneten "Kürzeste-Wege-Verfahren" ermittelt werden. Meiner Meinung nach bietet sich hier der Bellmann-Ford-Algorithmus an, da eine negative Bewertung im Modell vorkommt. Eine Besonderheit ist, dass ich die Knoten alphabetisch abarbeiten soll. Meine Frage ist nun folgende: Wie viele Arbeitsschritte benötige ich zur Lösung des Problems? Beim ersten Mal kam ich auf sechs Schritte, bei zweiter Betrachtung habe ich die Knoten mit Verbesserungen, hinsichtlich des kürzesten Weges, erneut in die Warteschlange aufgenommen. Somit konnte ich den Algorithmus nach acht Schritten abbrechen (negativer Kreis). Welches der Ergebnisse stimmt oder gibt es eventuell noch einen weiteren Ansatz, der zu einem ganz anderen Resultat führt? Danke für jegliche Hilfe... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|