Seite 1 von 1

Fehler im Korrektheitsbeweis von Dijkstra's Algorithmus?

Verfasst: 28. Mär 2014 13:53
von rindphi
Meiner Meinung nach hat sich im Beweis der Korrektheit von Dijkstra's Algorithmus auf Folie 17 im Foliensatz 4 ein kleiner Fehler eingeschlichen:

Die Fallunterscheidung mit dem ersten Fall \(d(u)>d(y)\) ist so doch nicht sinnvoll, da wir doch davor annehmen dass \(d(u)\leq d(y)\). Vielmehr folgt aus \(d(u)\leq d(y)\) und der durch Korollar 3 hergeleiteten Unleichung \(d(y)\leq d(v)\) direkt die Gleichheit \(d(u)=d(y)\), und damit \(d(u)=\delta(s,u)\), woraus sich der Widerspruch ergibt. So ist das auch in Cormen et al, 2007 dargestellt. Sehe ich das falsch?

Re: Fehler im Korrektheitsbeweis von Dijkstra's Algorithmus?

Verfasst: 7. Mai 2014 20:15
von Prof. Karsten Weihe
rindphi hat geschrieben: Die Fallunterscheidung mit dem ersten Fall \(d(u)>d(y)\) ist so doch nicht sinnvoll
Was meinen Sie mit "sinnvoll"? Ist die Fallunterscheidung Ihrer Meinung nach falsch oder "nur" überflüssig?

KW