Fehler im Korrektheitsbeweis von Dijkstra's Algorithmus?

Moderator: Effiziente Graphenalgorithmen

rindphi
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 3. Sep 2009 20:52
Kontaktdaten:

Fehler im Korrektheitsbeweis von Dijkstra's Algorithmus?

Beitrag von rindphi » 28. Mär 2014 13:53

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?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrektheitsbeweis von Dijkstra's Algorithmus?

Beitrag von Prof. Karsten Weihe » 7. Mai 2014 20:15

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

Antworten

Zurück zu „Effiziente Graphenalgorithmen“