CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 1 of 1
  1. #1
    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
  •  





Click Here to Expand Forum to Full Width

Featured