mathmari Posted June 7, 2013 Share Posted June 7, 2013 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?? Link to comment Share on other sites More sharing options...
mathmari Posted June 8, 2013 Author Share Posted June 8, 2013 (edited) 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, 2013 by mathmari Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now