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