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

    u = Q.top().first;
    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;


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

  • 1
    \$\begingroup\$ 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* \$\endgroup\$ – Martin York Aug 9 '14 at 9:07
  • 1
    \$\begingroup\$ Note: Here is a more complete implementation of Dijkstra \$\endgroup\$ – Martin York Aug 9 '14 at 10:10
  • 3
    \$\begingroup\$ 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? \$\endgroup\$ – Morwenn Aug 9 '14 at 16:54
  • 2
    \$\begingroup\$ @Morwenn My crystal ball tells me that pp is std::make_pair<Vertex&, int>. But what is tle? \$\endgroup\$ – vnp Aug 9 '14 at 18:46
  • \$\begingroup\$ 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. \$\endgroup\$ – iavr Aug 9 '14 at 20:00

Handling vertices multiple times

There are two places where you are doing extra work because you are handling vertices multiple times:

  1. When you find a shorter path to a vertex, you currently push that vertex with the new path length into your priority queue. While this works, you still have the old vertex in the priority queue as well. You will eventually pop the vertex off twice (and handle it twice), which is not ideal. If you kept track of which vertices you've already handled, you could quickly skip duplicate vertices when you come across them.

  2. When you handle a new vertex, you iterate over all of its edges. But if you see an edge to a vertex that has already been handled, you don't need to deal with it. Right now, you could be pushing vertices back onto your priority queue that you've already dealt with.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.