Seite 1 von 1

Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 7. Apr 2016 13:33
von Stefan1992
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 8. Apr 2016 15:59
von Prof. Karsten Weihe
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 12. Apr 2016 12:03
von Stefan1992
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?

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 12. Apr 2016 12:27
von Prof. Karsten Weihe
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 12. Apr 2016 18:27
von Stefan1992
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.

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 12. Apr 2016 22:38
von Prof. Karsten Weihe
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 13. Apr 2016 12:14
von Stefan1992
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? :?

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 13. Apr 2016 13:29
von Prof. Karsten Weihe
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 14. Apr 2016 09:36
von Stefan1992
Ja. Der Satz ist jetzt klarer. Auch wenn ich mir den Beweis noch ein paar Mal selbst überlegen muss. :lol:

Vielen Dank

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 14. Apr 2016 10:10
von Prof. Karsten Weihe
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

Re: Wiki-Beitrag Dijkstra - Voraussetzungen

Verfasst: 14. Apr 2016 10:22
von Stefan1992
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