Seite 1 von 1

Fehler bei Bellman-Ford

Verfasst: 30. Jun 2015 17:00
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. ;)

Re: Fehler bei Bellman-Ford

Verfasst: 30. Jun 2015 18:06
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

Re: Fehler bei Bellman-Ford

Verfasst: 30. Jun 2015 20:49
von Alexj1988
ist gefixt, sollte im laufe des abends gepatched werden