-
Dijkstra's algorithm
Hi!!!
I need some help at the following exercise...
We have a directed graph G=(V,E), 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[b]=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[b]=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??