-
June 3rd, 2014, 08:04 PM
#1
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...
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|