PROBLEM LINK:
Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi
PREREQUISITES:
the Bellman-Ford algorithm
PROBLEM:
Given a directed weighted graph, for each vertex output the minimum weight of a path (not necessarily simple) that goes through it or “INF” if such a minimum weight does not exist.
EXPLANATION:
Note: To understand the solution you need to have a good understanding of the Bellman-Ford algorithm; Especially the part where the algorithm determines if there is a negative cycle in the graph.
For the sake of simplicity, we’ll use the term “shortest path” to denote “minimum weighted path” in this editorial.
First, Let’s define two arrays st and en. st[v] is the weight of the shortest path that starts from v. Similarly, en[v] is the weight of the shortest path that ends at v. It is clear that the answer for vertex v is equal to st[v] + en[v] or “INF” if st[v] = -inf or en[v] = -inf. We’ll talk about how to calculate en[v] for each vertex v. st can be calculated the same way.
Let’s add a new vertex and call it source. Now, for each vertex v, add an edge from source to v with weight 0. Consequently, en[v] is equal to the weight of the shortest path that starts from source and ends at v.
To calculate en in our modified graph, run the Bellman-Ford algorithm on this graph from source. The algorithm will correctly determine en[v] if en[v] is not -inf. So all that’s left is to find out for which v s, en[v] is equal to -inf.
en[v] is equal to -inf if there is a vertex u (could be same as v) that is on a negative cycle and there is a path from u to v. On each negative cycle in the graph, there is a vertex z that en[z] changes on the n^{th} iteration of the Bellman-Ford algorithm. We can identify these vertices and run a DFS from them and see which vertices they reach. Those vertices would be the ones whose answer is equal to -inf. This solution runs in O(N \times M).
Instead of running a DFS from the abovementioned vertices in the end, you can run the Bellman-Ford algorithm again and on each iteration, mark the vertices that have an edge from a marked vertex (a vertex whose answer is -inf). Refer to the tester’s
solution to see this approach.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here