Funktioniert Dijkstra bei diesem Graph mit negativen Gewichten?

Hallo,

normalerweise habe ich keine Problem mit dem Dijkstra Algorithmus, soweit ich mich erinnere funktioniert er doch eigentlich nur bei positiven Gewichten.

Nun wurde heute aber gesagt dass Dijsktra für den folgenden Graph funktioniert:

Ich frage mich wieso, da ich dachte es wäre nicht möglich. Der kürzeste Weg würde doch 0 ergeben, aber mit Dijkstra würde ich doch auf 32+16+8+4+2 kommen oder nicht?

Answer 1

[KarlRanseierIII]

Dijkstra funktioniert nicht bei negativen Kantengewichten, bzw. präziser, er funktioniert nicht zuverlässig. Er kann aber dann zum richtigen Ergebnis kommen, wenn durch die Greediness der richtige Pfad gewählt wird. (Du kannst Dir das im Wikipedieartikel durchlesen).

Der nächste Knoten wird über das minimale kumulierte Kantengewicht ermittel, sodaß die negativen Gewichte den Algo auf den Zickzackkurs ziehen, wäre das invers, also z.b 69 gefolgt von -69 würde Dijkstra gradlinig nach rechts laufen und diesen Pfad wählen.