dijkstra-algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:39 Mi 14.07.2010 | | Autor: | mathetuV |
| Aufgabe | was bedeutet dist[v]> dist[u] + f(uv)?
das problem ist wenn ich die entsprechenden kanten wähle, dann kommt zum Beispiel raus, 3 > 3? kann mir jemand das erklären wie mann das addiert, |
was bedeutet dist[v]> dist[u] + f(uv)?
das problem ist wenn ich die entsprechenden kanten wähle, dann kommt zum Beispiel raus, 3 > 3? kann mir jemand das erklären wie mann das addiert?
vielen dank für eure hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:49 Mi 14.07.2010 | | Autor: | max3000 |
> was bedeutet dist[v]> dist + f(uv)?
> das problem ist wenn ich die entsprechenden kanten wähle,
> dann kommt zum Beispiel raus, 3 > 3? kann mir jemand das
> erklären wie mann das addiert,
Also dist heißt bei euch wahrscheinlich die aktuell kürzeste Distanz zum Zielknoten.
f(uv) ist wahrscheinlich die Länge der Kante, die u und v verbindet.
Und im Dijkstra-Algorithmus gehst du ja alle Knoten durch und schaust nach, ob zu allen Knoten, die den aktuellen Knoten mit einer Kante verbinden, einen kürzeren Weg über den aktuellen Knoten hätten als der bereits berechnete.
Also dein Ausschnitt bedeutet so viel wie:
Aktuell kürzester Weg von v zum Ziel > Aktuell kürzester Weg von u zum Ziel + Länge der Kante zwischen u und v.
Ist diese Bedingung erfüllt setzt du ja dann dist(u) = dist(v) + f(uv) , weil der Weg von u über Knoten v zum Ziel kürzer ist als der, den du irgendwann davor berechnet hast.
3>3 ist ja egal. Da sind die Wege eben gleich lang, also auch keine Verbesserung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:01 Do 15.07.2010 | | Autor: | mathetuV |
vielen dank für deine hilfe
freut mich sehr, genauso eine erklärung habe ich gesucht
|
|
|
|
