Hilfe->Dijkstra- Algorithmus |
| 08.06.2013, 21:43 | Auf diesen Beitrag antworten » |
| marie m | 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, 22:45 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Zu d kommt man auch von a über e, und zwar mit einer Pfadgewichtung von 1. Von da aus kommt kam mit Gewichtung 0 nach c. |
| 08.06.2013, 22:56 | Auf diesen Beitrag antworten » |
| marie m | 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, 23:06 | Auf diesen Beitrag antworten » |
| eulerscheZahl | 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. |
| Anzeige | |
|
|
|
| 08.06.2013, 23:23 | Auf diesen Beitrag antworten » |
| marie m | 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:27 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Ich weiß nicht, woher du die 5 nimmst. Mit dem Dijkstra-Algorithmus: a->b: d[b] = 1 a->e: d[e] = 2 //einziger Unterschied zur Optimallösung b->c: d[c] = 3 c->d: d[d] = 2 |
| 09.06.2013, 01:38 | Auf diesen Beitrag antworten » |
| marie m | 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, 09:03 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Ja, genau. |
| 09.06.2013, 11:34 | Auf diesen Beitrag antworten » |
| marie m | Ok!!! Dankeschön!!! 
|
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
