Hallo
Ich habe 2 Frage zu diesem Dijkstras Algorithmus (kürzester Weg in einem Graphen zwischen 2 Knoten):
1) Ist das sicher immer der Fall, dass man dann über die Vorgänger-Beziehungen eine Baumstruktur erhält?
2) Liefert der Algorithmus wirklich immer den kürzesten Weg zwischen 2 Knoten?
Auf diese zweite Frage komme ich, weil in einem Buch steht, dass der Algorithmus "greedy" wäre. Bei "greedy" bin ich immer nervös, ob es dann auch wirklich immer die beste Lösung liefert, und nicht ev. so irgendeine Lösung, die halt irgendwie passt.
EDIT: Jetzt ist mir grad bewusst geworden, dass das Thema hier ganz falsch ist, oder? Gehört das in die Plauderecke?
Ich habe 2 Frage zu diesem Dijkstras Algorithmus (kürzester Weg in einem Graphen zwischen 2 Knoten):
1) Ist das sicher immer der Fall, dass man dann über die Vorgänger-Beziehungen eine Baumstruktur erhält?
2) Liefert der Algorithmus wirklich immer den kürzesten Weg zwischen 2 Knoten?
Auf diese zweite Frage komme ich, weil in einem Buch steht, dass der Algorithmus "greedy" wäre. Bei "greedy" bin ich immer nervös, ob es dann auch wirklich immer die beste Lösung liefert, und nicht ev. so irgendeine Lösung, die halt irgendwie passt.
EDIT: Jetzt ist mir grad bewusst geworden, dass das Thema hier ganz falsch ist, oder? Gehört das in die Plauderecke?
Zuletzt bearbeitet: