Dijkstra's algorithm using C++ STL












1












$begingroup$


I'm implementing Dijkstra's algorithm using C++ STL.



Input



n e (number of vertices and the number of edges)
followed by e lines of edges and their weights w
followed by u and v the shortest path between which is to be found out



Output



A single integer representing the shortest path between u and v



My Approach



adj : adjacency list representation of the graph



cost : weights associated with each vertex



I'm implementing my own priority queue, which prioritizes the vertices based on their dist values



following are the functions I have implemented:




  1. distance (vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) main logic for the algorithm is implemented here


  2. vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) returns an initial min-heap data structure of the vertices (prioritized according to the dist values)


  3. int extract_min (vector<int> &H, vector<int> dist) returns and deletes the minimum element from the min-heap


  4. void decrease_key (vector <int> &H, int i, int key, vector<int> dist) takes arguments as: the heap, index of the element for which key is to be changed (i), the key value, and the dist array


  5. void min_heapify (vector<int> &H, int i, vector<int> dist)



Code



#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using std::vector;
using std::cout;

int heapsize;

int parent (int i) {
if (i%2 == 0) return (i/2) - 1;
return i/2;
}

void min_heapify (vector<int> &H, int i, vector<int> dist) {
int l = (2*i) + 1;
int r = (2*i) + 2;
int smallest = i;
if (l < heapsize && dist[H[l]] < dist[H[i]]) smallest = l;
if (r < heapsize && dist[H[r]] < dist[H[i]]) smallest = r;
if (smallest != i) {
std::swap(H[i], H[smallest]);
min_heapify(H, smallest, dist);
}
}

void decrease_key (vector <int> &H, int i, int key, vector<int> dist) {
while (i < heapsize && i > 0 && dist[H[parent(i)]] > dist[H[i]]){
std::swap (H[i], H[parent(i)]);
i = parent(i);
}
}

int extract_min (vector<int> &H, vector<int> dist) {
if (heapsize >= 1) {
int min = H[0];
H[0] = H[heapsize - 1];
H[heapsize - 1] = -1;
heapsize -- ;
min_heapify (H, 0, dist);
return min;
}
}

vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) {
vector<int> H;
heapsize = adj.size();
for (int i = 0; i < adj.size(); i ++) H.push_back(i);
for (int i = H.size() / 2; i >= 0; i --) {
min_heapify (H, i, dist);
}
return H;
}

int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
vector <int> dist (adj.size(), std::numeric_limits<int>::max());
dist [s] = 0;
vector<int> H = makequeue (adj, dist);
int u;
while (heapsize != 0) {
u = extract_min (H, dist);
for (int i = 0; i < adj[u].size(); i ++) {
if ( (dist[u] != std::numeric_limits<int>::max()) && (dist[adj[u][i]] > dist[u] + cost[u][i])) {
dist[adj[u][i]] = dist[u] + cost[u][i];
vector<int>::iterator it = find(H.begin(), H.begin() + heapsize, adj[u][i]);
decrease_key (H, std::distance(H.begin(), it) , dist[adj[u][i]], dist);
}
}
}

if (dist[t] == std::numeric_limits<int>::max()) return -1;
else return dist[t];
}

int main() {
int n, m;
std::cin >> n >> m;
vector<vector<int> > adj(n, vector<int>());
vector<vector<int> > cost(n, vector<int>());
for (int i = 0; i < m; i++) {
int x, y, w;
std::cin >> x >> y >> w;
adj[x - 1].push_back(y - 1);
cost[x - 1].push_back(w);
}
int s, t;
std::cin >> s >> t;
s--, t--;
std::cout << distance(adj, cost, s, t);
}


Example



Input



10 9



1 2 1



2 3 1



3 4 1



4 5 1



5 6 1



6 7 1



7 8 1



8 9 1



9 10 1



1 10



Output



9



Concern



the platform where I wish to submit the code gives wrong answer for a particular test case, I haven't been able to figure out where the problem might lie



My best guess is in the decrease_key function since I'm using a workaround here - by first performing a find to determine the index of the vertex. (Something similar to what was asked here: https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu)



I'm not very sure how to use the priority_queue container in C++ STL, therefore I went with my own implementation. I'd prefer if someone could guide me as to what is wrong with the code I've written.









share









$endgroup$

















    1












    $begingroup$


    I'm implementing Dijkstra's algorithm using C++ STL.



    Input



    n e (number of vertices and the number of edges)
    followed by e lines of edges and their weights w
    followed by u and v the shortest path between which is to be found out



    Output



    A single integer representing the shortest path between u and v



    My Approach



    adj : adjacency list representation of the graph



    cost : weights associated with each vertex



    I'm implementing my own priority queue, which prioritizes the vertices based on their dist values



    following are the functions I have implemented:




    1. distance (vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) main logic for the algorithm is implemented here


    2. vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) returns an initial min-heap data structure of the vertices (prioritized according to the dist values)


    3. int extract_min (vector<int> &H, vector<int> dist) returns and deletes the minimum element from the min-heap


    4. void decrease_key (vector <int> &H, int i, int key, vector<int> dist) takes arguments as: the heap, index of the element for which key is to be changed (i), the key value, and the dist array


    5. void min_heapify (vector<int> &H, int i, vector<int> dist)



    Code



    #include <iostream>
    #include <vector>
    #include <limits>
    #include <algorithm>

    using std::vector;
    using std::cout;

    int heapsize;

    int parent (int i) {
    if (i%2 == 0) return (i/2) - 1;
    return i/2;
    }

    void min_heapify (vector<int> &H, int i, vector<int> dist) {
    int l = (2*i) + 1;
    int r = (2*i) + 2;
    int smallest = i;
    if (l < heapsize && dist[H[l]] < dist[H[i]]) smallest = l;
    if (r < heapsize && dist[H[r]] < dist[H[i]]) smallest = r;
    if (smallest != i) {
    std::swap(H[i], H[smallest]);
    min_heapify(H, smallest, dist);
    }
    }

    void decrease_key (vector <int> &H, int i, int key, vector<int> dist) {
    while (i < heapsize && i > 0 && dist[H[parent(i)]] > dist[H[i]]){
    std::swap (H[i], H[parent(i)]);
    i = parent(i);
    }
    }

    int extract_min (vector<int> &H, vector<int> dist) {
    if (heapsize >= 1) {
    int min = H[0];
    H[0] = H[heapsize - 1];
    H[heapsize - 1] = -1;
    heapsize -- ;
    min_heapify (H, 0, dist);
    return min;
    }
    }

    vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) {
    vector<int> H;
    heapsize = adj.size();
    for (int i = 0; i < adj.size(); i ++) H.push_back(i);
    for (int i = H.size() / 2; i >= 0; i --) {
    min_heapify (H, i, dist);
    }
    return H;
    }

    int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
    vector <int> dist (adj.size(), std::numeric_limits<int>::max());
    dist [s] = 0;
    vector<int> H = makequeue (adj, dist);
    int u;
    while (heapsize != 0) {
    u = extract_min (H, dist);
    for (int i = 0; i < adj[u].size(); i ++) {
    if ( (dist[u] != std::numeric_limits<int>::max()) && (dist[adj[u][i]] > dist[u] + cost[u][i])) {
    dist[adj[u][i]] = dist[u] + cost[u][i];
    vector<int>::iterator it = find(H.begin(), H.begin() + heapsize, adj[u][i]);
    decrease_key (H, std::distance(H.begin(), it) , dist[adj[u][i]], dist);
    }
    }
    }

    if (dist[t] == std::numeric_limits<int>::max()) return -1;
    else return dist[t];
    }

    int main() {
    int n, m;
    std::cin >> n >> m;
    vector<vector<int> > adj(n, vector<int>());
    vector<vector<int> > cost(n, vector<int>());
    for (int i = 0; i < m; i++) {
    int x, y, w;
    std::cin >> x >> y >> w;
    adj[x - 1].push_back(y - 1);
    cost[x - 1].push_back(w);
    }
    int s, t;
    std::cin >> s >> t;
    s--, t--;
    std::cout << distance(adj, cost, s, t);
    }


    Example



    Input



    10 9



    1 2 1



    2 3 1



    3 4 1



    4 5 1



    5 6 1



    6 7 1



    7 8 1



    8 9 1



    9 10 1



    1 10



    Output



    9



    Concern



    the platform where I wish to submit the code gives wrong answer for a particular test case, I haven't been able to figure out where the problem might lie



    My best guess is in the decrease_key function since I'm using a workaround here - by first performing a find to determine the index of the vertex. (Something similar to what was asked here: https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu)



    I'm not very sure how to use the priority_queue container in C++ STL, therefore I went with my own implementation. I'd prefer if someone could guide me as to what is wrong with the code I've written.









    share









    $endgroup$















      1












      1








      1





      $begingroup$


      I'm implementing Dijkstra's algorithm using C++ STL.



      Input



      n e (number of vertices and the number of edges)
      followed by e lines of edges and their weights w
      followed by u and v the shortest path between which is to be found out



      Output



      A single integer representing the shortest path between u and v



      My Approach



      adj : adjacency list representation of the graph



      cost : weights associated with each vertex



      I'm implementing my own priority queue, which prioritizes the vertices based on their dist values



      following are the functions I have implemented:




      1. distance (vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) main logic for the algorithm is implemented here


      2. vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) returns an initial min-heap data structure of the vertices (prioritized according to the dist values)


      3. int extract_min (vector<int> &H, vector<int> dist) returns and deletes the minimum element from the min-heap


      4. void decrease_key (vector <int> &H, int i, int key, vector<int> dist) takes arguments as: the heap, index of the element for which key is to be changed (i), the key value, and the dist array


      5. void min_heapify (vector<int> &H, int i, vector<int> dist)



      Code



      #include <iostream>
      #include <vector>
      #include <limits>
      #include <algorithm>

      using std::vector;
      using std::cout;

      int heapsize;

      int parent (int i) {
      if (i%2 == 0) return (i/2) - 1;
      return i/2;
      }

      void min_heapify (vector<int> &H, int i, vector<int> dist) {
      int l = (2*i) + 1;
      int r = (2*i) + 2;
      int smallest = i;
      if (l < heapsize && dist[H[l]] < dist[H[i]]) smallest = l;
      if (r < heapsize && dist[H[r]] < dist[H[i]]) smallest = r;
      if (smallest != i) {
      std::swap(H[i], H[smallest]);
      min_heapify(H, smallest, dist);
      }
      }

      void decrease_key (vector <int> &H, int i, int key, vector<int> dist) {
      while (i < heapsize && i > 0 && dist[H[parent(i)]] > dist[H[i]]){
      std::swap (H[i], H[parent(i)]);
      i = parent(i);
      }
      }

      int extract_min (vector<int> &H, vector<int> dist) {
      if (heapsize >= 1) {
      int min = H[0];
      H[0] = H[heapsize - 1];
      H[heapsize - 1] = -1;
      heapsize -- ;
      min_heapify (H, 0, dist);
      return min;
      }
      }

      vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) {
      vector<int> H;
      heapsize = adj.size();
      for (int i = 0; i < adj.size(); i ++) H.push_back(i);
      for (int i = H.size() / 2; i >= 0; i --) {
      min_heapify (H, i, dist);
      }
      return H;
      }

      int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
      vector <int> dist (adj.size(), std::numeric_limits<int>::max());
      dist [s] = 0;
      vector<int> H = makequeue (adj, dist);
      int u;
      while (heapsize != 0) {
      u = extract_min (H, dist);
      for (int i = 0; i < adj[u].size(); i ++) {
      if ( (dist[u] != std::numeric_limits<int>::max()) && (dist[adj[u][i]] > dist[u] + cost[u][i])) {
      dist[adj[u][i]] = dist[u] + cost[u][i];
      vector<int>::iterator it = find(H.begin(), H.begin() + heapsize, adj[u][i]);
      decrease_key (H, std::distance(H.begin(), it) , dist[adj[u][i]], dist);
      }
      }
      }

      if (dist[t] == std::numeric_limits<int>::max()) return -1;
      else return dist[t];
      }

      int main() {
      int n, m;
      std::cin >> n >> m;
      vector<vector<int> > adj(n, vector<int>());
      vector<vector<int> > cost(n, vector<int>());
      for (int i = 0; i < m; i++) {
      int x, y, w;
      std::cin >> x >> y >> w;
      adj[x - 1].push_back(y - 1);
      cost[x - 1].push_back(w);
      }
      int s, t;
      std::cin >> s >> t;
      s--, t--;
      std::cout << distance(adj, cost, s, t);
      }


      Example



      Input



      10 9



      1 2 1



      2 3 1



      3 4 1



      4 5 1



      5 6 1



      6 7 1



      7 8 1



      8 9 1



      9 10 1



      1 10



      Output



      9



      Concern



      the platform where I wish to submit the code gives wrong answer for a particular test case, I haven't been able to figure out where the problem might lie



      My best guess is in the decrease_key function since I'm using a workaround here - by first performing a find to determine the index of the vertex. (Something similar to what was asked here: https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu)



      I'm not very sure how to use the priority_queue container in C++ STL, therefore I went with my own implementation. I'd prefer if someone could guide me as to what is wrong with the code I've written.









      share









      $endgroup$




      I'm implementing Dijkstra's algorithm using C++ STL.



      Input



      n e (number of vertices and the number of edges)
      followed by e lines of edges and their weights w
      followed by u and v the shortest path between which is to be found out



      Output



      A single integer representing the shortest path between u and v



      My Approach



      adj : adjacency list representation of the graph



      cost : weights associated with each vertex



      I'm implementing my own priority queue, which prioritizes the vertices based on their dist values



      following are the functions I have implemented:




      1. distance (vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) main logic for the algorithm is implemented here


      2. vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) returns an initial min-heap data structure of the vertices (prioritized according to the dist values)


      3. int extract_min (vector<int> &H, vector<int> dist) returns and deletes the minimum element from the min-heap


      4. void decrease_key (vector <int> &H, int i, int key, vector<int> dist) takes arguments as: the heap, index of the element for which key is to be changed (i), the key value, and the dist array


      5. void min_heapify (vector<int> &H, int i, vector<int> dist)



      Code



      #include <iostream>
      #include <vector>
      #include <limits>
      #include <algorithm>

      using std::vector;
      using std::cout;

      int heapsize;

      int parent (int i) {
      if (i%2 == 0) return (i/2) - 1;
      return i/2;
      }

      void min_heapify (vector<int> &H, int i, vector<int> dist) {
      int l = (2*i) + 1;
      int r = (2*i) + 2;
      int smallest = i;
      if (l < heapsize && dist[H[l]] < dist[H[i]]) smallest = l;
      if (r < heapsize && dist[H[r]] < dist[H[i]]) smallest = r;
      if (smallest != i) {
      std::swap(H[i], H[smallest]);
      min_heapify(H, smallest, dist);
      }
      }

      void decrease_key (vector <int> &H, int i, int key, vector<int> dist) {
      while (i < heapsize && i > 0 && dist[H[parent(i)]] > dist[H[i]]){
      std::swap (H[i], H[parent(i)]);
      i = parent(i);
      }
      }

      int extract_min (vector<int> &H, vector<int> dist) {
      if (heapsize >= 1) {
      int min = H[0];
      H[0] = H[heapsize - 1];
      H[heapsize - 1] = -1;
      heapsize -- ;
      min_heapify (H, 0, dist);
      return min;
      }
      }

      vector<int> makequeue (vector<vector<int>> adj, vector<int> dist) {
      vector<int> H;
      heapsize = adj.size();
      for (int i = 0; i < adj.size(); i ++) H.push_back(i);
      for (int i = H.size() / 2; i >= 0; i --) {
      min_heapify (H, i, dist);
      }
      return H;
      }

      int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
      vector <int> dist (adj.size(), std::numeric_limits<int>::max());
      dist [s] = 0;
      vector<int> H = makequeue (adj, dist);
      int u;
      while (heapsize != 0) {
      u = extract_min (H, dist);
      for (int i = 0; i < adj[u].size(); i ++) {
      if ( (dist[u] != std::numeric_limits<int>::max()) && (dist[adj[u][i]] > dist[u] + cost[u][i])) {
      dist[adj[u][i]] = dist[u] + cost[u][i];
      vector<int>::iterator it = find(H.begin(), H.begin() + heapsize, adj[u][i]);
      decrease_key (H, std::distance(H.begin(), it) , dist[adj[u][i]], dist);
      }
      }
      }

      if (dist[t] == std::numeric_limits<int>::max()) return -1;
      else return dist[t];
      }

      int main() {
      int n, m;
      std::cin >> n >> m;
      vector<vector<int> > adj(n, vector<int>());
      vector<vector<int> > cost(n, vector<int>());
      for (int i = 0; i < m; i++) {
      int x, y, w;
      std::cin >> x >> y >> w;
      adj[x - 1].push_back(y - 1);
      cost[x - 1].push_back(w);
      }
      int s, t;
      std::cin >> s >> t;
      s--, t--;
      std::cout << distance(adj, cost, s, t);
      }


      Example



      Input



      10 9



      1 2 1



      2 3 1



      3 4 1



      4 5 1



      5 6 1



      6 7 1



      7 8 1



      8 9 1



      9 10 1



      1 10



      Output



      9



      Concern



      the platform where I wish to submit the code gives wrong answer for a particular test case, I haven't been able to figure out where the problem might lie



      My best guess is in the decrease_key function since I'm using a workaround here - by first performing a find to determine the index of the vertex. (Something similar to what was asked here: https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu)



      I'm not very sure how to use the priority_queue container in C++ STL, therefore I went with my own implementation. I'd prefer if someone could guide me as to what is wrong with the code I've written.







      c++ algorithm





      share












      share










      share



      share










      asked 7 mins ago









      nglglhtrnglglhtr

      614




      614






















          0






          active

          oldest

          votes











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214152%2fdijkstras-algorithm-using-c-stl%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          0






          active

          oldest

          votes








          0






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes
















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214152%2fdijkstras-algorithm-using-c-stl%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          404 Error Contact Form 7 ajax form submitting

          How to know if a Active Directory user can login interactively

          Refactoring coordinates for Minecraft Pi buildings written in Python