-
June 7th, 2013, 10:48 AM
#1
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??
Last edited by mathmari; June 8th, 2013 at 05:42 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|