Fehler bei Bellman-Ford

Lithanel
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 21. Apr 2015 12:13

Fehler bei Bellman-Ford

Beitrag von Lithanel »

Ich denke es liegt hier ein Fehler vor.

a56612c9db38de8f62f993bc28da82e6

Denn, wenn man sich den minimalen Pfad von b nach c anschaut, dann steht als Musterlösung 47. Dies kann jedoch nicht möglich sein, denn dafür müsste man den Pfad b->a->g->e->h->d->c gehen, wofür man jedoch 6 Iterationen brauchen würde. Die richtige Lösung wäre jedoch b->g->e->h->d->c, da i=4 gilt.
Invariant: After i>= iterations, M^i(v,w) contains the length of a shortest (v,w)-path with at most i+1 arcs (for all v,w ∈ V). Also dürfte man in diesem Falle nur 5 Iterationen durchführen. Bitte nochmal überprüfen und falls ich falsch lag bitte eine Bemerkung schreiben. ;)
Dateianhänge
Unbenannt.PNG
Unbenannt.PNG (37.57 KiB) 225 mal betrachtet
graph.PNG
graph.PNG (31.4 KiB) 225 mal betrachtet

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Fehler bei Bellman-Ford

Beitrag von Alexj1988 »

Du hast recht, habe mir deinen Fall genau angeschaut. er hat M^5 gezeigt obwohl nach M^4 gefragt war...*ätz*

ok wird bis morgen gefixt

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Fehler bei Bellman-Ford

Beitrag von Alexj1988 »

ist gefixt, sollte im laufe des abends gepatched werden

Antworten

Zurück zu „Archiv“