Hi!!! I need some help at the following exercise...

Let G=(V,E) be a directed graph, where V={a,b,c,d,e}, E={(a,b),(a,e),(b,c),(c,d),(d,e),(e,c)} and their weights 1,2,2,-1,-1,3 respectively. Show where the Dijkstra's algorithm fails.

What I've done so far is:

At the beginning the distances are d[a]=0, d=d[c]=d[d]=d[e]=infinity

a gets extracted first, after the edges (a,b) and (a,e) are relaxed, and the distances are d=1, d[e]=2.

b is extracted next, after the edge (b,c) is relaxed, and d[c]=3

then c is extracted,after the edge (c,d) is relaxed and d[d]=2

At this step I have difficulties... Now d[d]=d[e]... How do I continue??

Sorry, but what I did the exercise is not correct, so I did it again and found that:

At the beginning the distances are d[a]=0, d=d[c]=d[d]=d[e]=infinity

a gets extracted first, after the edges (a,b) and (a,e) are relaxed, and the distances are d=1, d[e]=2.

b is extracted next, after the edge (b,c) is relaxed, and d[c]=3

then e is extracted,after the edge (e,c) is relaxed, and d[c]=3

then c is extracted,after the edge (c,d) is relaxed, and d[d]=2

finally d is extracted,after the edge (d,e) is relaxed, and d[e]=1

How can I show that Dijkstra's Algorithm fails??

Edited June 8, 201312 yr by mathmari