| Die letzten 9 Beiträge |
| marie m |
Ok!!! Dankeschön!!! 
|
| eulerscheZahl |
Ja, genau. |
| 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 ??? |
| 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 |
| 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?? |
| 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. |
| 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) ??? |
| 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. |
| 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?? |
|
|
