Bellman-Ford Invariante

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Bellman-Ford Invariante

Beitrag von Kija G »

Hallo,
im Wiki ist die Bellman-Ford Invariante folgendermaßen definiert:

Nach i >= 0 Iterationen beinhaltet die Matrix M^i (v,w) den kürzesten Pfad von v nach w mit höchstens i + 1 Kanten.

In den Videos wurde jedoch die Potenz der Matrix mit M^(i+1) ermittelt.

Als Beispiel war die Eingabematrix in der Induktionsbasis als M^1 angegeben.

Welche Version stimmt nun?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Bellman-Ford Invariante

Beitrag von JannikV »

Hey,

ich hab die Videos jetzt nicht gesehen, aber grundsätzlich gilt erstmal das Wiki.
Wenn im Video ein Fehler sein sollte, müssen wir abwarten bis das Produktionsteam Zeit hat da was zu machen..

Fürs lernen erstmal ans Wiki halten ;)

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Bellman-Ford Invariante

Beitrag von Seldon »

Hallo,
Kija G hat geschrieben:Nach i >= 0 Iterationen beinhaltet die Matrix M^i (v,w) den kürzesten Pfad von v nach w mit höchstens i + 1 Kanten.

In den Videos wurde jedoch die Potenz der Matrix mit M^(i+1) ermittelt.
Beide Aussagen sind äquivalent. Die Matrix M^i in der Invariante des Wikis ist nicht als Potenz aufzufassen sondern als Nummerierung. Die Potenz M^(i+1) ergibt tatsächlich den kürzesten Pfad von v nach w mit höchstens i + 1 Kanten nach der Definition "Powers of distance matrices" hier: http://wiki.algo.informatik.tu-darmstad ... .php/Paths M^1 ist gleich dem L aus der Formel für Bellman-Ford, wie oben bei Auxiliary data ausgeführt wird.

Antworten

Zurück zu „Archiv“