---

Geschrieben von marie m am 08.06.2013 um 21:43:

  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??

---

Geschrieben von eulerscheZahl am 08.06.2013 um 22:45:

 

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.

---

Geschrieben von marie m am 08.06.2013 um 22:56:

 

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) ???

---

Geschrieben von eulerscheZahl am 08.06.2013 um 23:06:

 

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.

---

Geschrieben von marie m am 08.06.2013 um 23:23:

 

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??

---

Geschrieben von eulerscheZahl am 08.06.2013 um 23:27:

 

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

---

Geschrieben von marie m am 09.06.2013 um 01:38:

 

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 ???

---

Geschrieben von eulerscheZahl am 09.06.2013 um 09:03:

 

Ja, genau.

---

Geschrieben von marie m am 09.06.2013 um 11:34:

 

Ok!!! Dankeschön!!!