Dijkstra Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:41 Fr 09.11.2007 | | Autor: | KathiVT |
Hallo,
Meine Aufgabe lautet: Welche Voraussetzungen müssen für einen bewerteten Graphen erfüllt sein, damit der Dijkstra Algorithmus richtig ist.
Nennen sie ein Beispiel wo diese Voraussetzung nicht erfüllt ist und der Algorithmus ein falsches Ergebnis liefert.
Also die Voraussetzung ist, dass der Graph ein schlichter, bewerteter Graph mit positiven Bewertungen sein muss. Aber wenn ich jetzt ein Beispiel mit negativen Zahlen versuche, ist das natürlich immer der beste Weg. Könnt ihr mir das passende Beispiel dazu liefern?
Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:07 Fr 09.11.2007 | | Autor: | koepper |
Hallo,
> Meine Aufgabe lautet: Welche Voraussetzungen müssen für
> einen bewerteten Graphen erfüllt sein, damit der Dijkstra
> Algorithmus richtig ist.
> Nennen sie ein Beispiel wo diese Voraussetzung nicht
> erfüllt ist und der Algorithmus ein falsches Ergebnis
> liefert.
>
> Also die Voraussetzung ist, dass der Graph ein schlichter,
> bewerteter Graph mit positiven
nicht ganz: nicht-negative reichen aus. Null ist OK, nur negative Kantenlängen schaden.
> Bewertungen sein muss. Aber
> wenn ich jetzt ein Beispiel mit negativen Zahlen versuche,
> ist das natürlich immer der beste Weg. Könnt ihr mir das
> passende Beispiel dazu liefern?
was erwartest du jetzt?
Nimm einen bewerteten Graphen und mache einige Kantenlängen negativ, fertig.
Am besten ist es, du baust einen negativen Zyklus ein, dann fällt der Beweis, daß Dijkstra scheitert am leichtesten (ohne rechnen)
Gruß
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:26 Fr 09.11.2007 | | Autor: | KathiVT |
Ah, o.k.
Auf die Idee mehrere Kanten negativ zu setzen bin ich natürlich nicht gekommen. Und dann ist die Summe negativ und das darf nicht sein, oder?
Das genügt??? O.k.
Danke
|
|
|
|
