Thursday, December 31, 2009

Dijkstra's Algorithm in C++


Dijkstra's Algorithm

Dijkstra's algorithm is a single source shortest path (sssp) algorithm. Like BFS, this famous graph searching algorithm is widely used in programming and problem solving, generally used to determine shortest tour in a weighted graph. This algorithm is almost similar to standard BFS, but instead of using a Queue data structure, it uses a heap like data structure or a priority queue to maintain the weight order of nodes. Here is the algorithm and pseudo-code. You can also look into Introduction to Algorithms (by C.L.R.S).

Here is a short implementation of this algorithm in C++, I assumed that, all the edge-weights are positive, and the max possible distance is less than 220 which is set as INF. The nodes are marked from 1 to N inclusive where N is the number of nodes.

Input format:

N E // number of nodes and edges
E lines containing an edge (u, v, w) on each line // edge(u, v, w) means weight of edge u-v is w. Nodes u, v are within range 1 to N
S // starting node

C++ code:

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define MAX 100001
#define INF (1<<20)
#define pii pair< int, int >
#define pb(x) push_back(x)

struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};

priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];

int main() {
    int i, u, v, w, sz, nodes, edges, starting;

    // create graph
    scanf("%d %d", &nodes, &edges);
    for(i=0; i<edges; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        G[v].pb(pii(u, w)); // for undirected
    }
    scanf("%d", &starting);

    // initialize distance vector
    for(i=1; i<=nodes; i++) D[i] = INF;
    D[starting] = 0;
    Q.push(pii(starting, 0));

    // dijkstra
    while(!Q.empty()) {
        u = Q.top().first;
        Q.pop();
        if(F[u]) continue;
        sz = G[u].size();
        for(i=0; i<sz; i++) {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u]+w < D[v]) {
                D[v] = D[u] + w;
                Q.push(pii(v, D[v]));
            }
        }
        F[u] = 1; // done with u
    }

    // result
    for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);
    return 0;
}

This is a straight forward implementation, according to the problem solving purpose, changes are to be made here and there.

Here is another implementation that does not use a custom comparison structure and the code is a bit more re-usable too. Note, that, nodes are numbered from 1 to n, pair for priority queue elements are assumed to be (weight, node) where pair for graph edges are assumed to be (node, weight). Also I have added comments to make the code more readable. Visit this codepad url for uncommented version of the code.

#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef pair< int, int > pii;

/*
Set MAX according to the number of nodes in the graph. Remember,
nodes are numbered from 1 to N. Set INF according to what is the
maximum possible shortest path length going to be in the graph.
This value should match with the default values for d[] array.
*/
const int MAX = 1024;
const int INF = 0x3f3f3f3f;

/*
pair object for graph is assumed to be (node, weight). d[] array
holds the shortest path from the source. It contains INF if not
reachable from the source.
*/
vector< pii > G[MAX];
int d[MAX];

/*
The dijkstra routine. You can send a target node too along with
the start node.
*/
void dijkstra(int start) {
    int u, v, i, c, w;

    /*
    Instead of a custom comparator struct or class, we can use
    the default comparator class greater<T> defined in quque.h
    */
    priority_queue< pii, vector< pii >, greater< pii > > Q;

    /*
    Reset the distance array and set INF as initial value. The
    source node will have weight 0. We push (0, start) in the
    priority queue as well that denotes start node has 0 weight.
    */
    memset(d, 0x3f, sizeof d);
    Q.push(pii(0, start));
    d[start] = 0;

    /*
    As long as queue is not empty, check each adjacent node of u
    */
    while(!Q.empty()) {
        u = Q.top().second; // node
        c = Q.top().first; // node cost so far
        Q.pop(); // remove the top item.

        /*
        We have discarded the visit array as we do not need it.
        If d[u] has already a better value than the currently
        popped node from queue, discard the operation on this node.
        */
        if(d[u] < c) continue;

        /*
        In case you have a target node, check if u == target node.
        If yes you can early return d[u] at this point.
        */

        /*
        Traverse the adjacent nodes of u. Remember, for the graph,,
        the pair is assumed to be (node, weight). Can be done as
        you like of course.
        */
        for(i = 0; i < G[u].size(); i++) {
            v = G[u][i].first; // node
            w = G[u][i].second; // edge weight

            /*
            Relax only if it improves the already computed shortest
            path weight.
            */
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                Q.push(pii(d[v], v));
            }
        }
    }
}

int main() {
    int n, e, i, u, v, w, start;
    /*
    Read a graph with n nodes and e edges.
    */
    while(scanf("%d %d", &n, &e) == 2) {

        /*
        Reset the graph
        */
        for(i = 1; i <= n; i++) G[i].clear();

        /*
        Read all the edges. u to v with cost w
        */
        for(i = 0; i < e; i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(pii(v, w));
            G[v].push_back(pii(u, w)); // only if bi-directional
        }

        /*
        For a start node call dijkstra.
        */
        scanf("%d", &start);

        dijkstra(start);

        /*
        Output the shortest paths from the start node.
        */
        printf("Shortest path from node %d:\n", start);
        for(i = 1; i <= n; i++) {
            if(i == start) continue;
            if(d[i] >= INF) printf("\t to node %d: unreachable\n", i);
            else printf("\t to node %d: %d\n", i, d[i]);
        }
    }
    return 0;
}

Dijkstra is a single source shortest path problem. So if you want to see the shortest path from every node, you have to call dijkstra once for each source or starting node.


69 comments:

  1. One thing. If a node has been push more then one time it will also pop more then one times. Consider the graph;
    6 6
    1 2 3
    1 4 7
    2 3 10
    2 4 3
    4 5 1
    4 6 2
    1
    Here 4 is pop'ed 2 times. I know its should not cause any problem but is not it unnecessary? If we do like below is there could be any problem?

    // dijkstra
    while(!Q.empty()) {
    u = Q.top().first;
    Q.pop();
    if(F[u]) continue; //If already done forget it
    sz = G[u].size();

    ReplyDelete
  2. No, It will not cause any trouble. You can do that :)

    ReplyDelete
  3. Can you please suggest how to modify the code if I want to find the shortest path for any 2 nodes?

    Thx so much

    ReplyDelete
  4. @Jo, I guess you were talking about all-pair shortest paths (so that you might get shortest path between any two nodes).
    Well, dijkstra won't be able to solve that easily, you could have run dijkstra once for each query.
    But there are more straight forward ways to get that. Use floyed warshall or johnson's algorithms.
    Floyed Warshall is very easy.

    ReplyDelete
  5. I keeping just for Dijkstra's Algorithm c++ codes and accidentally came here. I coded my assignment of Dijkstra's Algorithm in 2D array and i have problems implement it. Any idea or what good website gives sample codes of Dijkstra's Algorithm. The Dijkstra's i know how it works in paper, however when comes to coding, i'm not really good at it.
    I have try to compile your code successfully, but i dont have the text file of in.txt. Please you show the file to run ur code.

    ReplyDelete
  6. Hi, forget the in.txt thing, if you look carefully, that line is disabled. All you need to do is just enter the input graph, follow this format:
    First give two integers:
    # of nodes: n and # of edges: e
    Then e lines each containing and edge:
    u v w where the edge is u<--->v having weight w
    done!

    If you want to use a directed graph, then look, in the input area, remove this line:
    G[v].pb(pii(u, w));

    Hope you can do it now, but actually I didn't believe what you have written, I mean, if you know C++ then this code is very easy to understand, at least anyone can determine the input format from it! and if you don't know the language or don't know how to implement dijkstra, that will be a clear cheating, don't do that, learn the hard way :)

    ReplyDelete
  7. Obfuscated code.... If this were an application that required collaboration you would be scolded.

    Seriously the choice of variable names makes me want to strangle you.

    ReplyDelete
    Replies
    1. I am afraid you are in a wrong place, this is no place for software developers and this NEVER will require collaboration. This program is PERFECTLY OK for contest programming. Anyways, thanks for visiting my blog :)

      Delete
  8. @Anonymous::What the heck are you talking ? There can't be more neat and clean and accurate code than this. I will suggest you take some elementary school book and learn the topic "Coding Style". This higher level code is not for you..

    ReplyDelete
  9. Dear Zobayer:

    Your code was very useful for a beginner like me to understand a C++ implementation of the Dijkstra algorithm. I have a silly question (I am a beginner). I would like to find the distance between the "starting" node and another node (let's call it "target", which we can be read in the beginning ), I don't need the entire distance D[i]. This should take less time on a large graph. So I thought I should just change the condition for while loop in your code to
    while(!F[target]). Is that correct. I was getting nonsensical answers when I did that..could you please help?
    Tarun

    ReplyDelete
    Replies
    1. The only optimization you can do here is, between line 45 and 46, you can add the check, if(u == target) return d[u]; You cannot do anything other than this, because that will not ensure the correctness of dijkstra anymore. No matter whether you need or not, the nodes used in various paths between start and target must be calculated.
      Thanks for visiting my blog :)

      Delete
    2. Dijkstra algorithm is actually dynamic programming algorithm so before node n you must calculate minimum distance too all nodes <n otherwise u won't get correct answer

      Delete
  10. Hi Zobayer,

    Thanks a lot for your code. I'm a beginner to C++, and this is very helpful.

    I have one question about the speed to construct the graph. When I have a graph which has 1,000,000 nodes, and about 4,000,000 edges, this part"G[u].pb(pii(v, w))" takes a lot of time (e.g., 3s). Is there better way to make this part faster?

    Thank you!

    ReplyDelete
    Replies
    1. Yes there is. Just keep a list of the edges and maintain a link among the edges those who start from the same nodes. An example is in this post
      http://zobayer.blogspot.com/2010/05/maximum-flow-dinitz-algorithm.html
      Just check how I maintained the graph. It's not hard to understand.

      Thanks for visiting.

      Delete
    2. Hi Zobayer,

      Thank you for your reply.
      I managed to roughly understand the list used to represent the graph. But my problem is, after I change my graph to that format, how can I still use the Dijkastra algorithm listed in this blog?

      Thank you!

      Delete
    3. basically all you need to do is just change the loop in which adjacents to node u are traversed.
      basically it is something like:
      u = Q.top().first;
      ......
      ......
      for(i=fin[u]; i>=0; i=next[i]) {
      v = to[i]; // now work with v
      ......
      ......

      Delete
  11. I was wondering how to modify key in priority queue.
    Solution you have presented is very clever and elegant.
    I like it very much.

    ReplyDelete
    Replies
    1. This is straight forward textbook implementation. I didn't do the clever thing myself either.

      Delete
    2. I will explain what I mean.
      During relaxation you have to actualize elements in priority queue. How it can be done in STL priority queue?
      You have some elements there, but you can only take minimal one and put another. There is no decrease-key operation.

      In your or textbook (from which textbook?) implementation you just ignore old elements in priority queue, you are removing them later. That is clever and elegant for me :)

      Delete
    3. Thanks for replying, actually by textbook I meant conventional. What I wanted to do is to implement the min heap using stl priority queue. By definition, values I want most will be popped earlier, no matter how many old useless values are still on priority queue. They will be removed sooner or later as you have noticed. Basically this is very old code and now a days, we do not write like this. I mean the comp class is really not necessary when the datatype is generic. For example here, greater< pii > instead of comp in priority queue declaration would do the same thing with lesser hassle.

      Delete
  12. what is the use of DEBUG function here??
    in what conditions will it run?

    ReplyDelete
    Replies
    1. It's of no use to the algorithm itself. I use it to see values of some variables on specific point. If you set the macro on line 08 from if(0) to if(1), the debug lines will be printed.

      Delete
  13. I can't understand line 13. Sorry I'm a beginner.

    ReplyDelete
  14. Thanks zobayer . Its very nice :)

    ReplyDelete
  15. Great work Zobayer!

    Could you help me to print all the nodes (in the right sequence) of the minimum path between two nodes (starting node and end node given).

    Thanks a lot.

    Steve

    ReplyDelete
    Replies
    1. Hi Steve, printing the optimal path is not that hard. We have to add another array to keep track of the previous node.
      Let pre[v] stores the node from which we have last updated node v. So in dijkstra function:
      if(!F[v] && D[u]+w < D[v]) {
      DEBUG printf(" %d,", v);
      D[v] = D[u] + w;
      pre[v] = u; // this line stores the fact that v is updated from u with optimal cost
      Q.push(pii(v, D[v]));
      }

      Then we need to write another function that will print the optimal path:
      void printPath(int src, int dst) { // src and dst are source and destination nodes
      if(dst == src) {
      printf("%d", dst);
      return;
      }
      printPath(src, pre[dst]);
      printf(" %d", dst);
      }

      So first call dijkstra for src and dst, then call this function. Don't forget to reset the pre[] array.

      Hope its clear now :)

      Delete
  16. So I tried this with this text file:

    6 10
    0 1 9
    0 3 2
    1 2 11
    1 4 3
    2 4 5
    2 5 12
    3 1 4
    3 4 8
    4 3 1
    4 5 6
    0

    and it does not work correctly. The output states:

    Node 1, min weight = 6
    Node 2, min weight = 8
    Node 3, min weight = 2
    Node 4, min weight = 3
    Node 5, min weight = 9

    however this is not correct the correct output should be:

    Node 1, min weight = 6
    Node 2, min weight = 17
    Node 3, min weight = 2
    Node 4, min weight = 9
    Node 5, min weight = 15

    ReplyDelete
    Replies
    1. Wrong. If you take the path (0,3) -> (4,3) -> (2,4),
      the second line should be: Node 2, min weight = 8
      because 2 + 1 + 5 = 8. So, Zobayer's algorithm's is correct.


      Delete
    2. Thanks for the reply :) And this is not my algorithm, that credit goes to Dijkstra :D

      Delete
  17. Many people have tested this code . It is more likely that you are doing something wrong

    ReplyDelete
  18. Is there any way to exclude the bool[] F from the code?

    ReplyDelete
    Replies
    1. Yes, there is. in fact we do not use the boolean array for flagging in dijkstra implementations. If you look carefully, when you are getting a u = Q.top().first; you can get w = Q.top().second before popping it. It is the weight of node u when the node was inserted in the queue and as we are using a min heap / priority queue, it is already the minimum possible value for u. And a few lines below, there you will see, whenever we can update the cost of node V from U, we update it in d[V]. so d[V] will always store the minimum possible value for node V. Now, the observation is, there can be multiple instances of the node U in Q at any given time. But we only want to expand from the minimum one, i.e. the first one that is popped from the Q. The flag array is using the exact same thing, it is just marking whether we already used node U or not. The same logic can be checked by testing if (w > d[u]) continue;. Becuse d[u] will always hold minimum for u, and if w (the one paired with u in the Q) is greater than d[u], then we are sure that we have already seen and traversed from u before.

      Thus you don't need that anymore.

      Delete
  19. #include
    using namespace std;
    #define MAX 100000
    struct comp {
    bool operator() (const pair &a, const pair &b) {
    return a.second > b.second;
    }
    };
    void inp(int &x)
    {
    register int c = getchar_unlocked();
    x = 0;
    for(;(c<48 || c>57);c = getchar_unlocked());
    for(;c>47 && c<58;c = getchar_unlocked())
    {
    x = (x<<1) + (x<<3) + c - 48;
    }
    }
    map mapp;
    int main(){
    int m,n,i,j,u,v,w,src,dest,edges,testcases,t;
    inp(t);
    while(t--){
    inp(m);
    priority_queue,vector >,comp> PQ;
    vector > vec[m+1];
    for(i=0;idist(m+1,INT_MAX);
    memset(visited,0,sizeof(visited));
    dist[src]=0;
    PQ.push(make_pair(src,0));
    while(!(PQ.empty())){
    u=PQ.top().first;
    PQ.pop();
    if(u==dest)
    break;
    for(i=0;i<vec[u].size();i++){
    v=vec[u][i].first;
    w=vec[u][i].second;
    if(visited[v]==false && dist[u]+w<dist[v]){
    dist[v]=dist[u]+w;
    PQ.push(make_pair(v,dist[v]));
    }
    }
    visited[u]=true;
    }
    printf("%d\n",dist[dest]);
    }
    printf("\n");
    }
    return 0;
    }
    I am getting Wrong Answer on Spoj, taking help from the above algorithm. Can you please please tell where I am going wrong?

    ReplyDelete
    Replies
    1. AC now.. the priority queue should not be declared global :)

      Delete
    2. I think you should not use global operator override for known classes or primitive types.

      Delete
  20. its a great tutorial thanx .. :-)

    ReplyDelete
  21. Good Job Zobayer!

    Is it possible to verify if a graph is disconnected with this algorithm?

    ReplyDelete
    Replies
    1. Yes. Start from any node. Do not use "early returns" and when the algorithm stops, check distance array if every position has less than infinite.

      Delete
    2. Whhat do you mean by "early returns"? if(F[u]) continue; ?

      Delete
    3. no, sometimes when you run it for specific destination, then once the destination point is popped from the queue, you can return from dijkstra. in that case many other nodes can remain unexplored. I mentioned about this scenario which is not present in this code anyway.

      Delete
  22. What is the use of vector in priority queue ( priority_queue,comp> )? comp is comparator and pii is vertex,weight pair. but what is the use of vector insite a priority queue.
    I am beginner in C++, so I don't know much about it. Please explain.

    ReplyDelete
    Replies
    1. The container for the priority queue data structure.
      http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

      Delete
  23. Hello my friend,
    thanks for you post.

    I have execute your code on this graph :
    nbr_nodes=5 , nbr_edges=8
    4 0 7 (i j w)
    4 2 2
    4 3 7
    4 1 11
    1 0 5
    1 3 1
    2 3 3
    2 0 4

    i got this result when the starting node is 4:
    Node 0, min weight = 0
    Node 1, min weight = 11
    Node 2, min weight = 2
    Node 3, min weight = 5
    Node 4, min weight = 0

    I dont understand why distance from 4 to 0 is 0 !! it should be 6 because : 4->2->0=6.

    Can you help plz ?

    Thanks a lot

    ReplyDelete
    Replies
    1. Hello friend!
      My program was written considering nodes were numbered from 1 to n. 0 is not a recognized node. Please change the input and try again. Also let me know if it works this time. Thank you :)

      Delete
  24. hey, thanks for your response.

    Yes it works good! :-)

    i have another question, i want to make a loop for exemple to compute the shortest starting from 1, then i choose another source and compute the shortest path. I made a loop, but it gives me strange results. i'm still looking where i have to put this loop. Idea?

    ReplyDelete
    Replies
    1. I'm glad that it worked. I have added a new version of code, it is shorter (well when you delete the comments) and looks cleaner too. If you want to get the shortest path distance from every node, instead of taking a specific start node as input, run a loop for every node over lines 115 through 125 of the second code.
      Happy coding!

      Delete
  25. hello again,
    the type of weights of my edges is float. i modified the "int distance[]" to float, and pair< int, int > to pair< float, int >, int w to float w.. i didn't succeed to have good results for floating weights. Any ideas please?

    Thanks a lot

    ReplyDelete
    Replies
    1. try using 'double' type instead of float. float is buggy.
      now to the point, I assume you have changed the definition of pii. Please look carefully, pair used in graph and priority queue are not same. both have different meaning of first and second; in one of the first is node, while the other first is distance. and in the first code, I think pair< int, float > will work. let me know.

      Delete
    2. for the second code, you need pair< float, int > for Q and pair< int, float > for G.

      Delete
  26. Hi Zobayer I was solving this problem on SPOJ :-

    http://www.spoj.com/problems/SHPATH/

    I tried your method of dijkstra but it gave TLE. Then I made some modifications in dijkstra method according to some other blog which is given below :-

    int dijk(int src, int des)
    {
    priority_queueque;
    que.push(mp(0, src));
    vectorcost(n + 5, N);
    int nd, ed, ln;
    cost[src] = 0;
    while (1)
    {
    nd = (que.top()).second;
    ed = -(que.top()).first;
    if (nd == des)return ed;
    que.pop();
    if (cost[nd] < ed)continue;
    ln = list[nd].size();

    rep(i, 0, ln)
    {
    int x = list[nd][i].first;//cost
    int y = list[nd][i].second;//node
    if (ed + x < cost[y])que.push(mp(-(cost[y] = ed + x), y));
    }

    }
    }

    Although above method got accepted but it made me more confused about the algorithm. How is above method more efficient than given in this blog.

    In particular I have following doubts :-

    1) Why we are storing cost as -ve value in queue.

    2) Does the order of how we store value in pair also matters because I have tried to exchange the position of node and weight in priority queue but it does not works as expected.

    ReplyDelete
    Replies
    1. Hello Neeraj,
      I have got accepted in SHPATH using the code shown here. Here is my solution: http://codepad.org/7I7WAScT

      Now to answer your question:
      1. The default priority queue evaluates in "the bigger the better" fashion, So if you use -ve with weight when inserting, you don't need to write extra compare functions.
      2. The above codes assume that the first element is weight and second is node. It matters. STL compares pair elements from left to right, no matter how you nest it. So if it is pair< pair< int, pair< int, int > >, int >, STL still compares from leftmost to rightmost.

      Thanks for visiting, happy coding !

      Delete
  27. Hi
    Thanks for such good tutorial
    I am having a doubt i know its stupid but being a beginner please help
    In priority queue when we are pushing vertex along with distance there is possibility that future distance will get changed .My doubt is when we are pushing same vertex and distance again does priority queue has two distance with same weight.How it will resolve
    Thanks in advance

    ReplyDelete
  28. Here's a JAVA implementation for anyone interested. It has a complexity of O((M+N)Lg(N))

    http://ideone.com/NBKrYc

    ReplyDelete
  29. Am just gonna copy and paste this code. I was asked to implement Dijkstra using C++ and I don't know a thing in C++ language. I can comfortably understand this if it were coded in JAVA!. Please I need your permission to use your code

    ReplyDelete
  30. Why is the priority queue declared in such a way -
    priority_queue< pii, vector< pii >, greater< pii > > Q;
    If we are only pushing a pair < int, int > to Q, then what is meant by vector < pii > in the declaration?

    ReplyDelete
    Replies
    1. Hi there, the vector< pii > specified here is the underlying container type for our priority_queue declaration.
      You can get more info about priority_queue constructors here: http://www.cplusplus.com/reference/queue/priority_queue/

      Delete
  31. Hi Zobayer Hasan, I was wondering what type of complexity time is your program?

    ReplyDelete
  32. Hello Zobayer Hasan, I was wondering what was the time complexity of this program?

    ReplyDelete
  33. Can you explain line 61
    Thanks

    ReplyDelete
    Replies
    1. Same node can be present in the priority queue more than once. But for any node u, d[u] is the currently found minimum distance from source. Now, in priority queue, we keep u with corresponding cost c at the time of insertion. So, in those cases where you pop out a node u with cost c, but you see that d[u] is already better than c, then you already found a better path to u and no need to consider the currently popped node. So we continue.

      Delete
  34. Hi, I am working on a code where I am using Dijkstra's algorithm to find the shortest path. I also want to send a packet through the shortest path, but I want to use the ACK protocol. I don't have any idea on how to use ACK on a c++ code. I searched and it said using string but I don't really know how to use ACK protocol. I wrote my own Dijkstra's algorithm code, so I am a beginner at coding. Will you be able to help me and write a c++ code line to help me understand on how to use the ACK protocol on the shortest route?

    ReplyDelete
  35. This code will not work in case of multiple edges between pair of vertices :P

    ReplyDelete
    Replies
    1. Have you tested it? Cause that is not an exceptional case as long as you are not storing the graph in matrix. As far as I remember this code is capable of handling that too.

      Delete
  36. #define INF 1e9
    #define pii pair
    vector v[1010];
    int N[1010][1010];
    int cost[1010];
    bool vis[1010];
    priority_queue< pii, vector , greater > q;
    int calcsw(int n,int s,int e)
    {
    for(int i=1; i<=n; i++)
    cost[i]=INF;
    q.push(pii(0,s));

    cost[s]=0;
    while(!q.empty())
    {
    int a=q.top().second;
    int b=q.top().first;
    q.pop();
    if(cost[a] < b) continue;
    if(a==e)
    return cost[e];
    for(int i=0; icost[a]+N[a][i])
    {
    cost[u]=cost[a]+N[a][i];
    q.push(pii(cost[u],u));
    }
    }
    vis[a]=true;
    }

    return -1;
    }

    what i've done wrong?

    ReplyDelete
  37. Can I borrow this code for my thesis? Ruben Safir ruben@mrbrklyn.com

    ReplyDelete