Gewichtete Kanten und Dijkstra-Idee

Dijkstra findet kürzeste Wege bei nichtnegativen Kantengewichten. Eine PriorityQueue wählt den nächsten Knoten mit bisher kleinster Distanz. Relaxation aktualisiert Nachbardistanzen.

Negative Kanten brauchen andere Verfahren (Bellman-Ford).

Komplexität hängt von der Queue-Implementierung ab (typisch $O((n+m)\log n)$ mit Binärheap).

$$d(v)=\min(d(v), d(u)+w(u,v))$$

Wo gebraucht

Routing (Karten, Netzwerke), Latenz-optimierte Pfade, Spiele-KI auf Kacheln. Prioritätswarteschlange ist der Produktionsbaustein; A* erweitert die Idee um Heuristiken.

Vertiefung

Dijkstras Verfahren hält vorläufige Distanzen vom Start. Es wählt jeweils den noch offenen Knoten mit kleinster Distanz und versucht, Wege zu dessen Nachbarn durch Relaxation zu verbessern.

Die Korrektheit der endgültigen Festlegung beruht darauf, dass eine spätere Fortsetzung einen bereits kleinsten offenen Wert nicht durch eine negative Zusatzstrecke unterbieten kann. Sind solche Kanten möglich, wird eine andere Methode benötigt.

Eine Prioritätswarteschlange kann veraltete Einträge enthalten, wenn kein effizientes Decrease-Key verfügbar ist. Beim Entnehmen werden diese anhand der aktuellen Distanz verworfen. Das bewahrt Korrektheit bei einfacher Implementierung.

Schwierigkeitsstufen

1. Eine Relaxation numerisch ausführen.
2. Die Wahl des kleinsten offenen Distanzwerts begründen.
3. Veraltete Prioritätseinträge korrekt behandeln.

Fallstricke

Ein einmal entnommener Eintrag ist nur dann aktuell, wenn sein gespeicherter Wert zur Distanztafel passt. Das Verfahren ist für negative Gewichte nicht durch blosse Anpassung der Priorität zu retten.