Seite 1 von 1

Bellman Ford: Vorgehensweise?

Verfasst: 16. Sep 2015 18:30
von tmuecksch
Hi Leute,

es gab diesbezüglich bereits einen Thread; hat jemand von Euch eine Vorgehensweise wie man den Bellman Ford schnell und verlässlich durchführen kann?

Selbst bei nur 4 Iterationen und 7 Knoten brauche ich pro Aufgabe rund 30 Minuten und haben dann trotzdem noch kleine Fehler drin die dann durch propagieren. Und ich fülle nur eine Hälfte der Matrix (gemessen an der 0-er Diagonalen) aus...


Also hat jemand von Euch Ideen und Tips? Ich verzweifle hier :( :cry:


Danke im Voraus!

Re: Bellman Ford: Vorgehensweise?

Verfasst: 16. Sep 2015 18:59
von Nullmann
30 Minuten ist dann doch arg viel.. Ich glaube, du machst dann etwas falsch oder musst einfach noch mehr üben.

Abgesehen davon kenne ich keine hilfreiche Strategie für Bellman Ford oder Floyd Warshal. Bei beiden muss man sich sehr gut konzentrieren und hoffen, dass man einfach die kürzesten Pfade sieht - bei den gegebenen Restriktionen natürlich.

Re: Bellman Ford: Vorgehensweise?

Verfasst: 16. Sep 2015 19:02
von tmuecksch
Heißt das Du arbeitest eher mit der Grafik als mit der Tabelle?

Re: Bellman Ford: Vorgehensweise?

Verfasst: 16. Sep 2015 19:11
von headhumper
• Die Diagonale der Matrix kann sofort mit Nullen gefüllt werden.
• Für einen ungerichteten Graph ist die Matrix symmetrisch. Man muss also nur das obere oder untere Dreieck ausfüllen und kann die Werte dann in das andere Dreieck übertragen.
• Die Anzahl der Iterationsschritte plus 1 gibt die maximale Anzahl Kanten an, über die ein kürzester Weg führen darf. (Invariante!)

Viel mehr gibt's wohl (leider) nicht zu sagen :(

Re: Bellman Ford: Vorgehensweise?

Verfasst: 16. Sep 2015 21:14
von Nullmann
Ja, genau. Ich arbeite lediglich mit der Grafik. Und trage dann nacheinander die "halbe" Matrix ab, wie von Headhumper beschrieben.

Re: Bellman Ford: Vorgehensweise?

Verfasst: 17. Sep 2015 10:17
von tmuecksch
Vielen Dank für die Infos. Dann heißt es wohl einfach weiter üben ^^