CSES | Shortest Route II














































CSES | Shortest Route II



CSES | SHORTEST ROUTES 2

                                                       Read problem statement

Given n cities and m roads, find the shortest route distance for q queries (Each query consist of starting and ending city).
This problem is from the house of All Source Shortest Path. To solve this kind of problem, we have two approaches - 
         1. Use Single source shortest path algorithm for every vertex.
         2. Use All Source shortest path explicitly.

Using Single Source Shortest Path Algorithm-
We can use Dijkstra's Algorithm for every vertex, so it will be like using Dijkstra's Algorithm n times.

The time complexity would be - O(n2 log n + n*m), using min heap.

But the problem with this method is, it fails for negative edges(which is not the case here, so this algorithm will work fine here).

Since we've already covered Dijkstra's Algorithm in previous article, so go with the second choice.

Using All Source Shortest Path Algorithm (Floyd-Warshall Algorithm)-

Floyd-Warshall Algorithm is a dynamic programming method to solve All Source Shortest Path problem.

Step 1 .

We create a distance matrix, say adj[n+1][n+1].

Before the ith pass, adj[j][k] stores the distance from vertex j to vertex k, which contains only vertices {1, 2, 3 ..., i-1} as internal vertices in the path. 

For i = 0, adj[j][k] = distj,k if there exist a direct path between j and k, infinity otherwise.

Considering vertex i as bridge, we compare if we can relax the distance between two vertices j & k

                                  i.e. adj[j][k] = min(adj[j][k], adj[j][i]+adj[i][k])

The overall time complexity of the algorithm is O(n3).

Limitation: 

Although graph may have negative edges, but there must not be a negative cycle.


C++ Implementation of Shortest Route II

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e17;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> edges;
for(int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges.push_back({a, b, w});
}
int adj[n+1][n+1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
adj[i][j] = inf;
if(i == j)
adj[i][j] = 0;
}
}
for(auto e : edges) {
int a = e[0], b = e[1], c = e[2];
adj[a][b] = min(c, adj[a][b]);
adj[b][a] = min(c, adj[a][b]);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
}
}
}
while(q--) {
int a, b;
cin >> a >> b;
if(adj[a][b] == inf)
cout << -1 << '\n';
else
cout << adj[a][b] << '\n';
}
return 0;
}




More Articles of Anuj Maurya:

Name Views Likes
C++ | Find smallest interval 222 0
C++ | Lexicographic rank of string 95 0
C++ | Counting Rooms (CSES) 92 0
C++ | Building Roads (CSES) 78 0
C++ | High Score (CSES) 199 0
C++ | Collect maximum coin in grid 75 0
C++ | Is this k-palindrome ? 75 0
C++ | Shuffle the array elements 64 0
C++ | Fizz Buzz 81 0
C++ | Check if given points form square 59 0
C++ | Klee Algorithm to find union of line segment 87 0
C++ | Check if points are collinear 75 0
C++ | Check if given point lies inside triangle 82 0
C++ | Check if two line segment intersect 78 0
C++ | Number of ways to decode message 74 0
C++ || Minimise the subset difference 60 0
C++ | Count of subsets with given sum 67 24
C++ | Currency Arbitrage 97 22
C++ | Estimating the value of π (pi) using Monte-Carlo Simulation 57 18
C++ | Find the first missing number 75 16
C++ | Finding word in grid using DFS 66 11
C++ | Implementing pow(x, y) in logarithmic time 52 9
C++ | Sum of all factors of number 80 10
C++ | Building Teams (CSES) 69 21
C++ | Positions of anagram 47 12
C++ | Integer factorization 55 13
C++ | Primality test 63 14
C++ | Subset Sum Problem 64 12
C++ | Civil Time in Abseil 66 19
C++ | Abseil Time Duration 119 15
C++ | absl::Time 92 12
C++ | Introduction to Abseil Time library 81 9
C++ | absl::StripPrefix() and absl::StripSuffix() 79 8
C++ | absl::ConsumePrefix() and absl::ConsumeSuffix() 92 19
C++ | absl::string_view 71 13
C++ | absl::Substitute() | Formatting string in abseil 84 15
C++ | absl::StrJoin() | Yet another way of joining strings 116 7
C++ | String concatenation in Abseil - 2 | absl::StrCat() 103 10
C++ | absl::StrAppend() | String concatenation in abseil - 1 78 16
C++ | absl::StrSplit() 149 15
C++ | Appending to string and Writing to stream in Abseil 86 11
C++ | absl::PrintF(), absl::FPrintF() and absl::SNPrintF() 96 0
C++ | Abseil StrFormat() 70 27
C++ | Abseil flags Library 122 348
C++ | Abseil Numeric Library 86 65
C++ | Abseil Hash library 81 0
C++ | Abseil Containers 138 46
C++ Introduction to Abseil 88 13
CSES | Shortest Route II 251 47
CSES | Shortest Routes I 186 1

Comments