CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Jul 2009
    Posts
    28

    Dijkstra's algorithm C++ - 2 implementations

    Hello,

    I've a question regarding dijkstra's algorithm in C++. I've always used the following implementation:

    Code:
    struct edge //needed only for std::set, see below    {
            int vertex;
            unsigned long weight;
    
    
            edge(int v, unsigned long wt) : vertex(v), weight(wt) { }
    
    
            bool operator<(const edge& e2) const
            {
                return weight < e2.weight;
            }
        };
    
    
        void dijkstra_algorithm()
        {
            for(int i = 0 ; i < G.V() ; ++i)
            {
                wt[i] = ULONG_MAX;  //length of the shortest path from start vertex to "i"
                spt[i] = 0;         //last edge on the way from start vertex to "i"
            }
            
            int v = start_vertex;
            wt[v] = 0;
    
    
            std::set<edge> vertex_queue;
            vertex_queue.insert(edge(v, wt[v]));
    
    
            while(!vertex_queue.empty())
            {
                v = vertex_queue.begin()->vertex;
                vertex_queue.erase(vertex_queue.begin());
    
    
                DenseWeightedGRAPH::adjIterator A(G, v);
                for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())    //examining every neighbour of "v" vertex as Weighted_edge
                {
                    unsigned long P = wt[v] + e->wt();  //wt() returns the edge weight
                    int w = e->other(v);    //the function returns the opposite vertex to "v" in the edge "e"
    
    
                    if(P < wt[w])
                    {
                        vertex_queue.erase(edge(w, wt[w]));
    
    
                        wt[w] = P;
                        spt[w] = e;
    
    
                        vertex_queue.insert(edge(w, wt[w]));
                    }
                }
            }
        }
    But when I was writing a program for some online judge, it was keeping on failing on the largest input test and I discovered that the above algorithm was the problem. I've found another implementation of Dijkstra and modified it towards my graph representation classes and everything's fine now:

    Code:
    void dijkstra_algorithm()    {
            for(int i = 0 ; i < G.V() ; ++i)
            {
                wt[i] = ULONG_MAX;  
                spt[i] = 0;
            }
    
    
            int v = start_vertex;
            wt[v] = 0;
    
    
            bool visit[MAX_VERTICES] = { false };
    
    
            queue<int> q;
            q.push(v);
            while (!q.empty())
            {
                v = q.front();
                q.pop();
                visit[v] = false;
    
    
                DenseWeightedGRAPH::adjIterator A(G, v);
                for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())
                {
                    unsigned long P = wt[v] + e->wt();
                    int w = e->other(v);
    
    
                    if(P < wt[w])
                    {
                        wt[w] = P;
                        spt[w] = e;
    
    
                        if(!visit[w])
                        {
                            visit[w] = true;
                            q.push(w);
                        }
                    }
                }
            }
        }
    As you can see, here we got a visited table and an ordinary queue instead of priority one under std::set.


    Like I said, it's working now, but what's wrong with the first algorithm? The second one seems to be even simpler but according to definitions, Dijkstra requires some kind of a priority queue - not a normal queue that stores only vertex numbers and doesn't take weights into account itself...

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Dijkstra's algorithm C++ - 2 implementations

    Quote Originally Posted by Quentin026 View Post
    Like I said, it's working now, but what's wrong with the first algorithm?
    Isn't it a little bit pompous to think that people would jump on the chance to figure out what you did wrong?

    I mean Dijkstra got it right and that enough to satisfy most people.

    I'll eat my hat if Quent026 comes back here. No one ever does. Regardless of how fine a reply you've posted.

    And furthermore there are increasing evidence moderator corruption. When the dumb gets the upper hand it's time to leave for greener pastures. So good bye good people. This is my last post. Good luck.
    Last edited by razzle; June 13th, 2014 at 05:10 PM.

  3. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Dijkstra's algorithm C++ - 2 implementations

    Quote Originally Posted by Quentin026 View Post
    Like I said, it's working now, but what's wrong with the first algorithm? The second one seems to be even simpler but according to definitions, Dijkstra requires some kind of a priority queue - not a normal queue that stores only vertex numbers and doesn't take weights into account itself...
    I'm sure you can come up with a test case that fails the second algorithm.
    As to why the first one may be too slow: a std::set keeps all its elements sorted. Dijkstra's algorithm only needs to access the lowest element, so the order of the other elements does not matter. A binary heap can implement that more efficiently than a std::set.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  4. #4
    Join Date
    Apr 2014
    Location
    in northeast ohio
    Posts
    94

    Re: Dijkstra's algorithm C++ - 2 implementations

    just to throw in some info
    Dijkstra who can even pronounce that
    Dijkstra isn't Dijkstra once you weight it. ,its really more of a flood fill type algorithim anyways
    typically its not used for long distances as it increases over distance by approx d^2 checks

    Astar or A* is preferred in most case's as its faster and is meant for weighting its very similar
    i think once you weight Dijkstra's your starting to turn it into astar anyways
    Last edited by willmotil; June 18th, 2014 at 02:58 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