Dijkstra mit negativen Kanten der nicht funktionier

Question

Guten Abend miteinander

Ich suche ein Beispiel für einen Graphen wo man den Dikstra Algorithmus aufführen kann und dieser kein Korrektes Ergebnis liefet. Er sollte wenn möglich negative Kanten Gewichte enthalten.

Danke schön für eure Hilfe

Answer 1

Nimm einfach mal den Graphen

A auf B mit Gewicht -10

A auf C mit Gewicht 2

B auf C mit Gewicht 1

                          A             B           C

Initialisierung    0              -            -

                         0            -10           2

                        0             -10        -9

Aber da man ja keine negativen Gewichte verwendet muss man eine Konstante drauf rechnen, hier +11

dann wär der Graph so

A auf B mit Gewicht -10 +11 = 1
A auf C mit Gewicht 2 +11= 13
B auf C mit Gewicht 1+11= 12

                          A            B          C
Initialisierung    0              -            -
                        0            1          12

Eigentlich war mit neg. Gewichten der Weg von A über B zu C der kürzeste, jedoch jetzt über A zu C