PROBLEM LINK:
DIFFICULTY:
Simple
PREREQUISITES:
Graph theory, Shortest Paths
PROBLEM:
You’re given an N * N grid where (i,j)th entry is the distance between ith and jth point. You’re given M queries consisting of three points A, B, C. You’re task is to find out shortest distances : d(A, C) and d(A,B) + d(B, C).
QUICK EXPLANATION:
Pre-compute all pair-shortest paths using Floyd-Warshall algorithm. Solve every query in O(1) time.
DETAILED EXPLANATION:
Number of queries is so large that we can’t hope to find the shortest distance separately for each query. So we must do some precomputation so that we can answer individual queries fast enough. But as vertices change with each individual query, we can’t precompute distances from some points only, we need all pair shortest paths. Once we figure out this much, we could choose one of the algorithms for all pair shortest paths. The most common and simplest algorithm is Floyd Warshall which has a runnning time of O(N3)
Those of you who don’t know this algorithm, let me describe it a little here and you can follow up in detail in any algorithms book. Floyd Warshall is essentially a DP algorithm. DP state is d(i, j, k) which denotes the shortest distance between vertices j and k such that only vertices 1…i are allowed to be intermediate vertices. Base case is when i = 0 and it means shortest paths between vertices when no intermediate vertices are allowed. This is same as edge lengths between pair of vertices. After that when we include a new ith vertex, shortest path between j and k might not change in which case it’d be d(i-1, j, k) or it might change. It’d change iff ith vertex appears on the shortest path in which case its value would be d(i-1, j, i) + d(i-1, i, k).
We can save space by storing the dp for different values of i in the same 2D array. Sample code follows:
for i from 1 to N
for j from 1 to N
dist[j][k] = adj[j][k] // adj[j][k] is the adjacency matrix, as given in the problem
for i from 1 to N
for j from 1 to N
for k from 1 to N
dist[j][k] = min(dist[j][k], dist[j[i] + dist[i][k])
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.