Aufgabe:
Betrachten Sie folgenden Digraph = (, ) mit Kantengewichten ∶ → ℝ:
Problem/Ansatz:
1) Bestimmen Sie mit Hilfe des Dijkstra-Algorithmus einen kürzesten Weg von nach .
2) Betrachten Sie den Graphen, bei dem das Kantengewicht der Kante (, ) auf −1 gesetzt wird. Findet der Dijkstra-Algorithmus in diesem Fall trotzdem einen kürzesten Weg von
nach , auch wenn das für negative Kantengewichte nicht garantiert ist? Begründen Sie Ihre Antwort.
3) Geben Sie ein Beispiel an, das zeigt, dass der Dijkstra-Algorithmus im Allgemeinen keinen kürzesten Weg mehr findet, wenn die Kantengewichte negativ sind.
