Function to find the shortest path from source * using Dijkstra's algorithm * source: the source vertex * V: number of vertices * e: number of edges * adj[]: array of vectors representing the graph * h: vector of distance readjustments found by bellman ford * sp: short form for shortest path used in comments */
| 79 | * sp: short form for shortest path used in comments |
| 80 | */ |
| 81 | void dijkstra(int source, int V, int e, vector <int> &dist, vector <int> h) { |
| 82 | |
| 83 | // shortest_path_found[i] denotes whether vertex i's shortest path is finalized |
| 84 | vector <int> shortest_path_found(V + 1, 0); |
| 85 | |
| 86 | // pq (min heap implementation) contains vertex whose sp is not found with their smallest distance from source |
| 87 | priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq; |
| 88 | |
| 89 | // source vertex: parameter to the function, distance 0 |
| 90 | // first of the pair, i.e. distance is the key in pq (smallest key pair will be on the top) |
| 91 | pq.push({0, source}); |
| 92 | dist[source] = 0; |
| 93 | |
| 94 | // process till no more vertex to be added in the MST |
| 95 | while (!pq.empty()) { |
| 96 | // extract the node with smallest distance from source (sp not finalized) |
| 97 | pair <int, int> best_node; |
| 98 | best_node = pq.top(); |
| 99 | pq.pop(); |
| 100 | |
| 101 | int current_vertex = best_node.second; |
| 102 | int sp_distance = best_node.first; |
| 103 | |
| 104 | if (shortest_path_found[current_vertex] == 1) { |
| 105 | continue; |
| 106 | } |
| 107 | // mark the current vertex to have its sp finalized |
| 108 | shortest_path_found[current_vertex] = 1; |
| 109 | |
| 110 | // process all neighbouring vertices |
| 111 | for (int next_idx = 0; next_idx < adj_new[current_vertex].size(); next_idx ++) { |
| 112 | int next_vertex = adj_new[current_vertex][next_idx].first; |
| 113 | int edge_weight = adj_new[current_vertex][next_idx].second; |
| 114 | |
| 115 | // relaxation condition |
| 116 | if (!shortest_path_found[next_vertex] && dist[next_vertex] > edge_weight + dist[current_vertex]) { |
| 117 | dist[next_vertex] = dist[current_vertex] + edge_weight; |
| 118 | |
| 119 | pq.push({dist[next_vertex], next_vertex}); |
| 120 | } |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | // make readjustments for correct weights in original graph |
| 125 | for (int i = 1; i <= V; i ++) { |
| 126 | if (dist[i] != INT_MAX) { |
| 127 | dist[i] = dist[i] - (h[source] - h[i]); |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | int johnson(int t_no, int n, int m) { |
| 133 |