# Optimizing implementation of Dijkstra [closed]

I am using a std::priority_queue to implement Dijkstra's algorithm:

while(!Q.empty())
{
u = Q.top().first;
Q.pop();
int size=G[u].size();
for(int i=0; i<size; i++)//tle
{
v = G[u][i].first;
w = G[u][i].second;
//cout<<u<<" "<<v<<" "<<w<<endl;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
Q.push(pp(v,d[v]));

}
}
}


But I think it is a bit slow for competitive programming ($O(e + v*v)$). How can I improve my implementation?

• Dijkstra is a great general purpose algorithm. But there are huristics that are more effecient (may not give the best path (they are heuristics)). Try A* – Martin York Aug 9 '14 at 9:07
• Note: Here is a more complete implementation of Dijkstra – Martin York Aug 9 '14 at 10:10
• Could provide the variables declarations and tell what pp is? Without the types of the variables, I'm afraid that we won't be able to help you much. Also, can you use C++11? – Morwenn Aug 9 '14 at 16:54
• @Morwenn My crystal ball tells me that pp is std::make_pair<Vertex&, int>. But what is tle? – vnp Aug 9 '14 at 18:46
• You need to label each node, to show whether it has been inserted in the queue or whether exited from the queue (three different states). If an adjacent node has been inserted, you don't push it again. If it has exited already, you don't even compare any distance; just continue. – iavr Aug 9 '14 at 20:00