CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
Join Date
Apr 2013
Posts
45

## 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
•