0 Daumen
875 Aufrufe

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

von

1 Antwort

0 Daumen

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

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community