Bellman Ford: Vorgehensweise?

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Bellman Ford: Vorgehensweise?

Beitrag 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!

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Bellman Ford: Vorgehensweise?

Beitrag 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.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Bellman Ford: Vorgehensweise?

Beitrag von tmuecksch »

Heißt das Du arbeitest eher mit der Grafik als mit der Tabelle?

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Bellman Ford: Vorgehensweise?

Beitrag 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 :(

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Bellman Ford: Vorgehensweise?

Beitrag von Nullmann »

Ja, genau. Ich arbeite lediglich mit der Grafik. Und trage dann nacheinander die "halbe" Matrix ab, wie von Headhumper beschrieben.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Bellman Ford: Vorgehensweise?

Beitrag von tmuecksch »

Vielen Dank für die Infos. Dann heißt es wohl einfach weiter üben ^^

Antworten

Zurück zu „Archiv“