Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 3 Dec, 2020

Dijkstra's shortest path

Moderate
Asked in companies
Phone PeDeutsche BankGoogle

Problem statement

You have been given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges. Each edge connecting two nodes (‘X’,’Y’) will have a weight denoting the distance between node ‘X’ and node ‘Y’.

Your task is to find the shortest path distance from the source node, which is the node labeled as 0, to all vertices given in the graph.

Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

alt text

In the given input, the number of vertices is 4, and the number of edges is 5.

In the input, following the number of vertices and edges, three numbers are given. The first number denotes node ‘X’, the second number denotes node ‘Y’ and the third number denotes the distance between node ‘X’ and ‘Y’.

As per the input, there is an edge between node 0 and node 1 and the distance between them is 5.

The vertices 0 and 2 have an edge between them and the distance between them is 8.
The vertices 1 and 2 have an edge between them and the distance between them is 9.
The vertices 1 and 3 have an edge between them and the distance between them is 2.
The vertices 2 and 3 have an edge between them and the distance between them is 6.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There can be parallel edges i.e. two vertices can be directly connected by more than 1 edge.

Input format:

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

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

The next ‘E’ lines contain three space-separated integers ‘X’, ‘Y’, and ‘DISTANCE’, denoting a node ‘X’, a node ‘Y’, and the distance between nodes ‘X’ and ‘Y’ respectively.

Output format:

For each test case, print a single line containing ‘V’ space-separated integers that denote the shortest distance for each node from 0 to ‘V’-1, considering that we need the shortest distance from source node 0.

Print the maximum positive integer value, i.e 2147483647, for the disconnected graph.

Output for each test case will be printed in a separate line.
Note
You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 50
1 <= V <= 1000
1 <= E <= 3000
0 <= X, Y < V
1 <= DISTANCE[X][Y] <= 10^5


Time limit: 1 sec

Approaches

01 Approach

The idea is to maintain two arrays, one stores the visited nodes, and the other array stores the distance (element at index ‘i’ denotes the distance from node 0 to node ‘i’). We pick an unvisited minimum distance vertex, then update the distance of all its adjacent vertices considering the path from source to an adjacent vertex to pass through the picked minimum distance vertex. Repeat the process till all nodes are visited.

 

The Steps are as follows:

 

  1. We are given three variables, two nodes, and the distance between them. We need to form an adjacency matrix from this given information. For this, take a matrix of size ‘V’ * ‘V’, initialize all the positions to 0. Now, update the distance between two vertices in the matrix (denoted by the row number and column number) to the given distance in the input.
  2. Initialize the DISTANCE vector to ‘INT_MAX’ and the visited nodes vector to false.
  3. Since the distance of the source node i.e. node 0 to itself will be 0, update ‘DISTANCE[0]’ to 0.
  4. Find the shortest path for all vertices using the steps below:
    • Pick the minimum distance vertex, which is not yet visited, let’s say ‘X’.
    • Mark it as true in the visited vector.
    • Update the distances of the adjacent vertices. Update distance[Y] only if vertex ‘Y’ is not already visited and the current distance of the vertex ‘Y’ is greater than the distance from source vertex 0 to vertex ‘X’ plus the distance from ‘X’ to ‘Y’. This means that the shortest path from the source vertex to vertex ‘Y’ passes through vertex ‘X’.
    • Repeat the above steps till all the vertices are visited.
       

 5.    Return the ‘DISTANCE’ vector, which is our required solution.