Each Path

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
SalesforceFlipkart limited

Problem statement

In the Ninja world, 'N' cities are connected via 'M' one-way roads. Each road has a toll checkpoint, but the tax collection rules are different from the standard toll system. These checkpoints not only take money from you but give you as well.

The government of Ninja world fixed taxes for each checkpoint. If the tax value is positive, you have to pay that amount, and if the amount is negative, you receive that amount. For example, if tax is 3 dollars at a checkpoint, you have to pay 3 dollars at the checkpoint. If tax is -5 dollars, you receive 5 dollars from that checkpoint.

One of your friends, Alice, is planning a trip in the Ninja world but wants to understand taxation very well. Your task is to provide him with the minimum amount he needs to pay for each pair of cities, i.e., print a matrix of size N*N where matrix[i][j] denotes minimum tax one needs to pay to travel from city 'i' to city 'j' via some connecting roads.

Note:-

1. Cities are numbered from [0, 1, 2 ….. N-1] in input data.
2. To minimize the cost for a pair (i, j), any road can be travelled any number of times.
3. For any pair (i, j), if city 'j' is not reachable from city 'i', the value of matrix[i][j] should be '-1'.
4. If matrix[i][j] is negative for any pair, you should minimize it too, i.e., find the most negative value.
5. For any pair (i, j), if  'j' is reachable from city 'i', but it’s impossible to minimize the cost, fill the entire answer matrix with integer '-1'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains 'T', denoting the number of tests.
 For each Test :
    The first line contains two space-separated integers, 'N' and 'M', denoting the number of cities and roads, respectively.
    Next 'M' lines contain three integers 'x[i]', 'y[i]', 'w[i]' denoting there is a directed road from city 'x[i]' to city 'y[i]', and having tax 'w[i]'.
Output Format: 
For each Test :
    There should be 'N' lines, each containing 'N' space-separated integers. The j-th value in i-th row denotes the minimum tax to travel from city 'i' to city 'j'.
    If a pair of cities is unreachable, print integer  -1.
    If a pair is reachable but cannot minimize cost, all elements in the matrix must be  -1.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= 'T' <= 10
1 <= 'N' <= 10^3
0 <= 'M' <= min(10^3 , N*(N-1)/2 )
0 <= x[i], y[i] < 'N'   i ∈  (1,M)
-10^4 <= w[i] <= 10^4   i ∈  (1, M)
Note - Sum of 'N' and Sum of 'M' over all test cases does not exceed 10^3.

Time Limit: 1 sec
Sample Input 1:
1
4 5
0 3 3
0 1 -5
1 2 4
2 3 1
0 2 2
Sample Output 1
0 -5 -1 0
-1 0 4 5
-1 -1 0 1
-1 -1 -1 0
Explanation for Sample Input 1:

For pairs (1,0), (2,0), (2,1), (3,0), (3,1), (3,2), city ‘y’ is unreachable from city ‘x’. Hence, the answer is ‘-1’.
For pairs (0,0), (1,1), (2,2), (3,3), the answer is 0 as no road needed to travel.
For pair (0,1), there is a directed road with minimum possible cost -5.
For pair (0,2), although there is a directed road with cost 2, but path (0 -> 1 -> 2) gives minimum, i.e., -5+4 = -1.
For pair (0,3), the minimum cost path is (0 -> 1 -> 2 -> 3) with cost -5+4+1 = 0.
For pair (1,2), there is a direct road with minimum possible cost 4.
For pair (1,3), the minimum cost path is (1 -> 2 -> 3) with cost 4+1 = 5.
For pair (2,3), there is a direct road with minimum possible cost 1.
Sample Input 2:
2
4 4
1 2 3
2 3 3
3 1 3
3 2 -3
3 4
1 2 -1
2 3 -2
2 1 -1
3 1 5
Sample Output 2:
0 -1 -1 -1
-1 0 3 6
-1 6 0 3
-1 3 -3 0
-1 -1 -1
-1 -1 -1
-1 -1 -1
Hint

Make all the edge weights positive so that shortest path algorithms work on it.

Approaches (1)
Johnson’s Algorithm

Approach: Consider the given network as a directed graph with 'N' vertices and 'M' edges, where weights of edges are positive, negative, and zero.

Our task is to find the shortest path between each pair of vertices, for which Johnson’s algorithm is an optimal solution.

 

Let's understand how Johnson's algorithm works.

There exist two standard algorithms, Dijkstra and Bellman-ford, to find the shortest path from a fixed source vertex. For both algorithms, time complexities are O(E logV) and O(VE), respectively, where 'V' and 'E' are the numbers of vertices and edges.
 

If we run the Dijkstra algorithm from each vertex, the shortest paths for all pairs can be calculated in O(VE logV) time, but the problem is that it doesn't work for a graph with negatively weighted edges.

 

The main idea of Johnson's algorithm is to re-weight all the edges to make them positive, apply the Dijkstra algorithm on each vertex as a source node, and finally convert the weights back to their original value.
 

To calculate the new weights of edges, the Bellman-ford algorithm is used. Here, a dummy node is introduced in the graph, and it has an outgoing edge (zero weighted) to each vertex of the graph. The minimum distance to each vertex from this dummy is calculated in O(VE) time. Let these distances be H[0, 1, 2 ….. V-1].

Updated weight of an edge (i, j) will be (original_weight + H[i] - H[j] ). It’s guaranteed that all the edge weights become non-negative.

 

Using Dijkstra, assume the cost of a path (x, y) is ‘C’ then the original cost will be (C + H[y] - H[x]).


 

Algorithm:

  • Implement Bellman-ford algorithm as follows:
    • The graph has nodes numbered from 0 to N-1. Assume node-N as a dummy node.
    • Connect the dummy node to all other nodes with zero weighted edges.
    • Initialize an array 'dist' of size 'N' containing all values infinite, denoting distance of i-th node from dummy.
    • Iterate the complete list of edges' N' times.
      • If dist[source] + weight < dist[destination], update dist[destination] with (dist[source] + weight).
    • Iterate the list of edges one last time, and if the above condition still holds for any edge, then the graph contains a loop whose sum is negative.
  •  
  • Implement Dijkstra algorithm as follows:
    • Initialize an array 'dist' of size 'N' containing all values infinite, denoting distance of i-th node from the source node.
    • Initialize a boolean array 'visited' of size 'N' containing all values false, denoting whether i-th node is visited in finding the shortest path.
    • Create a min-heap containing the nodes in the increasing order of distances from the source node.
    • Push the source node into heap and dist[source] = 0.
    • While min-heap is not empty.
      • Pop the first element (at a minimum distance) from the heap.
      • If it is not already visited, mark it visited and explore its neighbor nodes.
        • If the neighbor's distance is minimized by [sum of the distance of current node and edge weight], update its distance and push to the heap.
    • Finally, the 'dist' array contains the shortest distances of each node from source.
  •  
  • Implement our main function as follows:
    • Pass the list of edges to Bellman-ford and if it signals a negative loop, return a matrix of size N*N with all elements as -1.
    • Bellman-ford returns H[0, 1, 2 …. N-1], which will be used to re-weight the edges.
    • Convert the list of edges into an adjacency list representation of a graph.
    • Re-weight all the edges (i, j): updated_weight = original_weight + H[i] - H[j].
    • Iterate a for loop, i = 0 to N-1.
      • Assume i-th node as source vertex and call Dijkstra on it.
      • Dijkstra returns distances of all nodes from the i-th node. Update them as follows:
        • If the distance is infinite, make it -1.
        • Else, for a distance from ‘i’ to ‘j’, add H[j] - H[i] into it.
      • Mark current array of distances as i-th row in answer matrix.
    • Return answer matrix.
Time Complexity

O(N * M * logN + N * M), where 'N' and 'M' are the number of cities/nodes and roads/edges, respectively.

The Dijkstra algorithm from a single source takes the time complexity of O(M logN). We take each vertex as a source node, so 'N' times Dijkstra is executed, resulting in a complexity of O(NM logN). To re-weight the edges, Bellman-ford is called, which takes time O(NM). Hence, overall time complexity becomes O(N * M * logN + N * M).

Space Complexity

O(N ^ 2), where 'N' is the number of cities/nodes.

The final matrix contains N*N elements, denoting the cost shortest path between each pair of vertices. Hence, overall space complexity becomes O(N ^ 2).

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