Frage zum Korrektheitsbeweis von Dijsktra

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Frage zum Korrektheitsbeweis von Dijsktra

Beitrag von tmuecksch »

Hallo,
ich beschäftige mich mit dem Beweis der Invariante des Dijkstra-Algorithmus (URL: http://wiki.algo.informatik.tu-darmstad ... p/Dijkstra).

Dort steht im 5ten Satz: "The third invariant implies that p has nodes in Q besides v".
Aber das ist doch das genaue Gegenteil, oder wird hier explizit das Gegenteil angenommen?

Denn in der Invariante #3 steht: "a shortest (s,v)-path that solely contains nodes not in Q (except for v itself, of course)".


Möglicherweise liegt hier ein Fehler vor...
Zuletzt geändert von tmuecksch am 29. Aug 2013 15:43, insgesamt 1-mal geändert.

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Re: Frage zum Beweis von Dijsktra

Beitrag von cofi »

Die Invariante bedeutet, dass in dem Pfad nur Knoten sind, die schon bearbeitet wurden. Mit dem zitierten Satz aus dem Korrektheitsbeweis habe ich auch so meine Probleme, die Idee ist hier aber, dass Q noch nicht leer ist und u der naechste Knoten ist der bearbeitet wird.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Frage zum Beweis von Dijsktra

Beitrag von tmuecksch »

cofi hat geschrieben:Die Invariante bedeutet, dass in dem Pfad nur Knoten sind, die schon bearbeitet wurden. Mit dem zitierten Satz aus dem Korrektheitsbeweis habe ich auch so meine Probleme, die Idee ist hier aber, dass Q noch nicht leer ist und u der naechste Knoten ist der bearbeitet wird.
Soweit ist mir das alles klar, das bestärkt ja die Sinnwidrigkeit nochmal.

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

Re: Frage zum Beweis von Dijsktra

Beitrag von JannikV »

Im Satz vorher steht ja "For a contradiction, suppose ..." Das heißt wir wollen was zum Widerspruch führen. Dafür wird angenommen es gäbe noch einen kürzeren Pfad als den bisherigen. Dann muss er einen Knoten haben, der noch in Q ist, also noch nicht angesehen wurde, denn wäre er angesehen worden, würde ja der aktuell kürzeste Pfad über ihn führen (schließlich ist er laut Annahme Teil eines kürzeren Pfades).

VG

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Frage zum Beweis von Dijsktra

Beitrag von tmuecksch »

gelöscht
Zuletzt geändert von tmuecksch am 3. Sep 2013 09:43, insgesamt 1-mal geändert.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Frage zum Korrektheitsbeweis von Dijsktra

Beitrag von tmuecksch »

gelöscht

Antworten

Zurück zu „Archiv“