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());

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;

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