Shortest Path

Moderate
0/80
Average time to solve is 25m
9 upvotes
Asked in companies
PayPalSoft SuaveRisingWave

Problem statement

You are given a connected, undirected graph with ‘V’ vertices and ‘E’ edges.

You are provided with two vertices, ‘src’ and ‘dest’. Your task is to return the shortest distance between the given vertices ‘src’ and ‘dest’.

For Example:

altImage

For the given graph,
The shortest distance between 1 and 3 is 2 (via 1 <-> 2 <-> 3). Hence, the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘V’ and ‘E’, denoting the number of vertices and the number of edges in the graph.

The next ‘E’ lines of each test case contain two space-separated integers, ‘vertex1’ and ‘vertex2’, corresponding to ‘vertex1’ and ‘vertex2’ are connected with a bidirectional edge.

The last line of each test case contains two space-separated integers, ‘src’ and ’dest’, representing two vertices whose minimum distance should be calculated.
Output Format: 
For each test case, print a single integer representing the shortest distance between the given two vertices, ‘src’ and ‘dest’.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= V <= 10^5
V - 1 <= E <= 10^5
1 <= vertex1 , vertex2 <= V
1 <= src, dest <= V

Time limit: 1 sec
Sample Input 1:
2
3 3 
1 2 
2 3 
1 3
2 3 
4 3 
1 2 
2 3 
3 4 
4 4
Sample Output 1:
1
0
Explanation of sample input 1:
For the first test case, 
The shortest distance between 2 and 3 is 1 (via 2 <-> 3). Hence, the answer is 1.

For the second test case,
The distance between the same vertices is always zero. Hence, the answer is 0.
Sample Input 2:
2
4 3 
1 2 
2 3 
4 1 
2 4
4 3 
1 3 
1 2 
1 4
2 4
Sample Output 2:
2
2
Hint

Can you use any all-pairs Shortest Path algorithm?

Approaches (3)
Floyd Warshall Algorithm

In this approach, we will calculate the shortest path between all pairs using the values of already computed values. This algorithm is known as Floyd Warshall Algorithm.

Floyd Warshall Algorithm is a dynamic programming approach in which the shortest distance of a pair is tried to minimize using an intermediate vertex whose value is already calculated as given below:

dist[index1][index2]=min(dis[index1][index2],dis[index1][k] + dis[k][index2])  

Where k is the intermediate vertex.

 

Algorithm:

  • Floyd Warshall Algorithm:
    • Make an array dist of size (V+1)*(V+1) to store the shortest distance between all pairs of vertices.
    • Initialize all values of the array by maximum integer value because, in the beginning, we assume that all vertices are unreachable.
    • For all vertices index from 1 to V.
      • set dist[index][index] as 0 (distance between same vertices is 0).
    • Set the values of the edge weights into dist from the given edges(edge weight will be 1.).
    • Using each vertex from 1 to V as intermediate vertex k, do the following steps:
      • For a pair between index1 and index2, we are trying to minimize its minimum distance using intermediate vertex k. We will iterate k from 1 to V.
        • Set dist[index1][index2]  as the minimum of dist[index1][index2] and dist[index1][k] + dist[k][index2].
  • Values of the Shortest distance between each pair are calculated.
  • Return the value of dist[src][dest] (Shortest distance between src and dest).
Time Complexity

O(V^3), where V is the number of vertices in the graph.

 

For each pair of vertices, we are trying each node as an intermediate node. The time complexity will be O(V * No of Pairs of vertices), and the number of pairs is V*V. Hence, the overall time complexity is O(V^3).

Space Complexity

O(V^2), where V is the number of vertices in the graph.

 

The O(V^2) space is used to store the minimum distance between all pairs of vertices, and in total, there are V*V = V^2 pairs. Hence, the overall space complexity is O(V^2).

Code Solution
(100% EXP penalty)
Shortest Path
Full screen
Console