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...