Dijkstra Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:28 Di 19.05.2009 | | Autor: | koker |
| Aufgabe | | Falls c konservativ ist, findet der Algorithmus von Dijkstra einen kürztesten Weg von einem Knoten s zu allen anderen Knoten. |
Hallo,
mir ist nicht die genau verständlich wie ich das nun beweisen kann.
Falls alle Kantengewichte positiv sind findet der Dijkstra Algorithmus ja immer den kürzesten Weg von s nach t.
Sobald wir bei s starten vergleich ja der Algorithmus die Nachbarn und sucht sicht den besmöglichen raus.
Sobald wir den besten Nachfolger rausgesucht haben suchen wir von dem am den besten Nachfolger usw. bis wir am Endknoten t angekommen sind.
Auf diese Weise wird es immer ein kurzester Pfad gefunden.
Ich bin mir aber ziemlich sicher, dass das nicht als Beweis reicht...
Habt ihr evtl Tipps für mich?
Schöne Grüße,
koker
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:24 Di 19.05.2009 | | Autor: | bazzzty |
> Falls c konservativ ist, findet der Algorithmus von
> Dijkstra einen kürztesten Weg von einem Knoten s zu allen
> anderen Knoten.
> Hallo,
>
> mir ist nicht die genau verständlich wie ich das nun
> beweisen kann.
Mir ist noch nichtmal klar, was Dein c ist. Kannst Du irgendeine Quelle angeben, wo man Eure/Deine Notation nachvollziehen kann?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 21.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
