|
  |
 Graphen, kürzeste Wege |
|
|
Ich arbeite gerade daran, zu beweisen, dass ein "kürzester" Pfad in einem Graphen, wenn der Graph eine neue Gewichtsfunktion bekommt, immernoch der kürzeste Pfad ist...
Stellt sich mir folgende Frage:
"kürzester Pfad" heisst doch immer "kürzester Pfad" von einem BESTIMMTEN Startknoten aus, oder?
Heisst es nicht sogar, von einem BESTIMMTEN KNOTEN, zu einem anderen BESTIMMTEN knoten!?
__________________
I'm 71% Megatron!
|
|
09.01.2008 16:07 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Das klingt in vielerlei Hinsicht -man entschuldige die Wortwahl- nach Bullshit.
1.) Jeder Pfad hat selbstverständlich festgelegte Start- und Endknoten. Würde man den Startknoten festlegen, den Endknoten jedoch nicht, ist der kürzeste Pfad immer der Nullpfad zu sich selbst. Um das Problem also klar zu formulieren:
Gegeben sind zwei Knoten a, b in einem (gewichteten) Graphen G. Ziel: Finde kürzesten Pfad von a nach b.
2.) Die Kosten eines Pfades sind (nach der mir bekannten Definition) abhängig von der gegebenen Gewichtsfunktion. Das bedeutet in direkter Folge, dass ein kürzester Pfad nach Austausch der Gewichtsfunktion nicht mehr der kürzeste sein muss.
Einfaches Gegenbeispiel:
Gegeben sind drei Knoten und jeder der Knoten ist mit den beiden anderen verbunden (![[latex]K_3[/latex]](http://www.matheboard.de/latex2png/latex2png.php?K_3) ). Gewichten wir die Kanten alle mit 1, ist der direkte Pfad zwischen a und b der kürzeste Pfad (d.h. die Kante ab). Gewichten wir nun die Kante ab mit 5, wird der Umweg über c zum kürzesten Pfad.
|
|
|
09.01.2008 17:42 |
|
|
|
|
es sing überhaupt nicht um die gewichtsfunktion an sich. es ging im allgemeinen darum, dass sssp die kürzesten pfade zu allen anderen erreichbaren pfaden findet. und dass in solch einem zusammenhang start und endknoten sich nciht ändern, auch, wenn durch änderung der gewichtsfunktion ein neuer pfad kürzester ist.
in meinem fall ist die neue gewichtsfunktion so definiert, dass es eben so ist, dass ein kürzester pfad, kürzester pfad bleibt.
war nirgends die rede von, wie die gewichte verteilt sind, oder geändert werden!
einzig und allein die tatsache, dass eben diese beiden pfade start und ende gemeinsam haben machen es in meinem beispiel möglich das zu zeigen, NCIHT allgemein, sondern für dieses beispiel 2er gewichtsfunktionen.
__________________
I'm 71% Megatron!
|
|
|
09.01.2008 19:26 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Aha, gleich mehrere neue Informationen auf einmal.
SSSP (Single Source Shortest Path) berechnet zu einem gegebenen Startknoten die kürzesten Wege zu allen möglichen Endknoten. Wo soll sich deiner Meinung nach hier was an den Knoten ändern? Ein Pfad von a nach b ist ein Pfad von a nach b, egal wie lang er ist.
Das du das auf eine konkrete Situation beziehst (und nicht allgemein meinst), hättest du auch mal erwähnen können.
|
|
|
09.01.2008 19:34 |
|
|
|
|
Sorry, für meine Ungenauigkeit.
Ich hätte eine weitere Frage:
Wenn es um "kürzeste" Wege geht, ist die Distanz, die damit dann minimal ist, immer eine Summe?! Angenommen ich habe einen Pfad, der von q über r und s nach t führt. Ist es immer so, dass sich die Kosten summieren??
d(q,r) + d(r,s) + d(s,t), wenn d() Gewicht oder Länge der Kante ist
Oder ist das definitionsabhänig?
Mir fehlt mal wieder das elementare Verständnis für Graphen und sowas i.a.
__________________
I'm 71% Megatron!
|
|
|
10.01.2008 10:57 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Im Prinzip ist alles definitionsabhängig. Wenn jedoch keine Definition vorhanden ist, muss man annehmen, dass eine allgemeine Übereinkunft über den verwendeten Fachdeterminismus existiert.
Im Falle der Kosten (oder Länge) eines Pfades ist die mir bekannte Definition die Aufsummierung der am Pfad partizipierenden Kantengewichte. Also liegst du richtig.
|
|
|
10.01.2008 13:09 |
|
|
|
|
klasse, ich danke Dir!
__________________
I'm 71% Megatron!
|
|
|
10.01.2008 13:24 |
|
|
|
|
|
|
|
|
