 Hilfe->Dijkstra- Algorithmus |
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
 |
|
| Hilfe->Dijkstra- Algorithmus |
     |
Hallo!!!
Gegeben sei ein gerichteter Graph G=(V,E), V={a,b,c,d,e} , E={(a,b),(a,e),(b,c),(c,d),(d,e),(e,c)} und deren Gewicht ist 1,2,2,-1,-1,3. Ich soll zeigen wo genau der Dijkstra-Algorithmus versagt.
Am Amfang sind die Abstände d[a]=0, d[b]=d[c]=d[d]=d[e]=unendlich
a wird als erstes entfernt, nachdem, durch die relaxation der Kanten (a,b) und (a,e), die Abstände d[b]=1, d[e]=2 werden.
b wird als nächstes entfernt, nachdem, durch die relaxation der Kante (b,c), der Abstand d[c]=3 wird.
Dann wird e entfernt, nachdem, durch die relaxation der Kante (e,c), der Abstand d[c]=3 wird.
Dann wird c entfernt, nachdem, durch die relaxation der Kante (c,d), der Abstand d[d]=2 wird.
Als letztes wird d entfernt, nachdem, durch die relaxation der Kante (d,e), der Abstand d[e]=1 wird.
Wo genau versagt der Dijkstra-Algorithmus??
|
|
08.06.2013 21:43 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Obwohl der Graph gerichtet ist und E={(a,b),(a,e),(b,c),(c,d),(d,e),(e,c)}, existieren die Kanten (e,d) und (d,c) ???
|
|
|
08.06.2013 22:56 |
|
|
|
|
Verzeihung, das gerichtet habe ich überlesen...
Zweiter Versuch:
der Dijkstra-Algorithmus scheitert bei negativen Kantengewichtungen:
von a aus:
b hat Wert 1; e hat Wert 2.
b wird also über a erreicht.
c erhält einen Wert von 3 (über b erreichbar). e hat aber einen Wert von 2<3, deshalb wird als nächstes der Weg von a nach e gewählt. Und ganau das sollte ja nicht der Fall sein.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
08.06.2013 23:06 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Also müsste der Weg normalerweise {a,b,c,d,e} sein, mit Gewichtung 1?? Und da man mit den Dijkstra-Algorithmus rausfindet dass der kürzeste Weg der {a,b,e,c,d} ist,dessen Gewicht 5 ist, kommen wir zum Ergebnis dass der Algorithmus scheitert??
|
|
|
08.06.2013 23:23 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
A ok... Danke!!! 
Wenn man den Bellman-Ford Algorithmus anwendet, bekommt man d[a]=0, d[b]=1, d[c]=3, d[d]=2, d[e]=1 ???
|
|
|
09.06.2013 01:38 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Ok!!! Dankeschön!!! 
|
|
|
09.06.2013 11:34 |
|
|
|
