0 Daumen
519 Aufrufe

Aufgabe:

Betrachten Sie folgenden Digraph = (, ) mit Kantengewichten ∶ → ℝ:

blob.png
Problem/Ansatz:

1) Bestimmen Sie mit Hilfe des Dijkstra-Algorithmus einen kürzesten Weg von nach .

2) Betrachten Sie den Graphen, bei dem das Kantengewicht der Kante (, ) auf −1 gesetzt  wird. Findet der Dijkstra-Algorithmus in diesem Fall trotzdem einen kürzesten Weg von
nach , auch wenn das für negative Kantengewichte nicht garantiert ist? Begründen Sie Ihre Antwort.

3)  Geben Sie ein Beispiel an, das zeigt, dass der Dijkstra-Algorithmus im Allgemeinen keinen  kürzesten Weg mehr findet, wenn die Kantengewichte negativ sind.

Avatar von

Hallo

was ist "von nach" ?

was bedeutet (, )

meist benutzt man ein Programm, die gibts auch im Netz, oder soll das per Hand geschehen.

lul

Hallo,

Sorry das ist ein Schreibfehler. Also von a nach d .
der Kante (b,e) auf -1 gesetzt .....

Es soll per Hand geschehen.


Vielen Dank

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community