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.