Wiki-Beitrag Dijkstra - Voraussetzungen

Moderator: Effiziente Graphenalgorithmen

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 7. Apr 2016 13:33

Hallo,

ich hätte eine Frage zu den Voraussetzungen im Artikel zu Dijkstra.
Hier wird für alle Alpha gilt l(a) >= 0. Ist das hier ein Schreibfehler? Müsste nicht entweder für alle a gilt l(a) >= 0 oder eben für alle Alpha gilt l(Alpha) >= 0.

Grüße

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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Prof. Karsten Weihe » 8. Apr 2016 15:59

Stefan1992 hat geschrieben: ich hätte eine Frage zu den Voraussetzungen im Artikel zu Dijkstra.
Hier wird für alle Alpha gilt l(a) >= 0. Ist das hier ein Schreibfehler? Müsste nicht entweder für alle a gilt l(a) >= 0 oder eben für alle Alpha gilt l(Alpha) >= 0.
Sie haben recht, ist korrigiert. :oops:

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 12. Apr 2016 12:03

Ich habe eine erneute Frage zum Dijkstra-Artikel.

Und zwar heißt es im Korrektheitsbeweis des Induktionsschrittes:
In summary, the subpath of p from s to w [...]
Welcher Knoten ist denn der Knoten w? Der wurde, zumindest in dem Beweis, vorher noch nicht definiert.

Grüße, Stefan

P.S.: Sollen Fragen zum Wiki lieber auf einer Diskussionsseite im Wiki gestellt werden oder lieber hier im Forum?

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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Prof. Karsten Weihe » 12. Apr 2016 12:27

Stefan1992 hat geschrieben: Welcher Knoten ist denn der Knoten w? Der wurde, zumindest in dem Beweis, vorher noch nicht definiert.
Sorry, das ist wieder der vorher schon betrachtete Knoten u. :oops:
Stefan1992 hat geschrieben: P.S.: Sollen Fragen zum Wiki lieber auf einer Diskussionsseite im Wiki gestellt werden oder lieber hier im Forum?
Hier im Forum :!:

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 12. Apr 2016 18:27

Also irgendwie habe ich mich in dem Beweis festgefahren.

Die Knotenmenge V sollte sich doch nicht ändern oder?
Dann verstehe ich die Aussage im vorletzten Satz des Beweises nicht, dass alle Knoten außer v und w zu V_{i - 1} gehören sollen.

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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Prof. Karsten Weihe » 12. Apr 2016 22:38

Stefan1992 hat geschrieben: Die Knotenmenge V sollte sich doch nicht ändern oder?
Dann verstehe ich die Aussage im vorletzten Satz des Beweises nicht, dass alle Knoten außer v und w zu V_{i - 1} gehören sollen.
Ich verstehe den Zusammenhang zwischen Ihren beiden Sätzen nicht?

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 13. Apr 2016 12:14

Die Notation V_{i - 1} bedeutet für mich eigentlich, dass die Menge V vor und nach einer Iteration i unterschiedlich sein kann.
Aber V enthält doch alle Knoten, die im Graphen enthalten sind und sollte nicht veränderlich sein? :?

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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Prof. Karsten Weihe » 13. Apr 2016 13:29

Stefan1992 hat geschrieben:Die Notation V_{i - 1} bedeutet für mich eigentlich, dass die Menge V vor und nach einer Iteration i unterschiedlich sein kann.
Aber V enthält doch alle Knoten, die im Graphen enthalten sind und sollte nicht veränderlich sein? :?
Sorry, das Kürzel V_{i-1} war nach einer Totalrevision der Seite aus Versehen stehengeblieben. :oops:

Ist es mit der Neufassung dieses Satzes nun verständlich?

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 14. Apr 2016 09:36

Ja. Der Satz ist jetzt klarer. Auch wenn ich mir den Beweis noch ein paar Mal selbst überlegen muss. :lol:

Vielen Dank

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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Prof. Karsten Weihe » 14. Apr 2016 10:10

Stefan1992 hat geschrieben:Ja. Der Satz ist jetzt klarer. Auch wenn ich mir den Beweis noch ein paar Mal selbst überlegen muss. :lol:
In meinen Videos zur GdI II in der Videothek Algorthmik auf youtube finden Sie ein Video zu Dijkstra, in dem ich den Beweis zeichnerisch erläutere.

Ihnen ist klar, dass bei Dijkstra nur die Beschleunigungstechniken Teil des EGA-Stoffes sind!?

KW

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Beitrag von Stefan1992 » 14. Apr 2016 10:22

Ja das ist mir klar. Ich möchte den nur der Vollständigkeit halber auch gesamt können.
Vielen Dank für die Hinweise.

Grüße

Antworten

Zurück zu „Effiziente Graphenalgorithmen“