New update is available. Click here to update.

Dijkstra's shortest path

Posted: 3 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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