Author: Roman Rubanenko
Tester: Vamsi Kavala
Editorialist: Bruno Oliveira
PROBLEM LINKS
DIFFICULTY
Medium
PRE-REQUISITES
Graphs, DFS, Shortest-Path Trees
Problem:
The Chef is going on a trip and he has devised an algorithm by which he will travel. We need to help the Chef to find the number of different pairs of cities (U,V) such that, this algorithm can find the shortest path from city U to city V. Note that if it is impossible to reach city V from U and Chef’s algorithm can conclude the same, then this pair of cities is also counted in the final answer.
Quick Explanation:
Quick Explanation: We can build a shortest paths tree to helps us finding the shortest path from a
given vertex S to all other vertexes. Then applying Chef’s algorithm, along with DFS, we can obtain our final answer.
Detailed Explanation:
As we see that the constraints for the small set are small enough, it is possible to solve this set by applying Floyd-Warshall Algorithm along with Chef’s algorithm for all pair of vertexes.
Floyd-Warshall finds all shortest paths between all pairs of vertexes simply in O(|V|^3) time, by using dynamic programming, improving estimates until the optimal one is found. Refer to this link to learn more about Floyd-Warshall algorithm.
For the remaining set, after reading Chef’s algorithm description, we see that we must find a way of computing shortest paths from a given vertex S (source) to all other vertexes. This can be done by building a shortest paths tree, in the following manner:
We can have an array d[], such that we can say:
- d[i] → Shortest path from vertex S to vertex i.
To find this shortest path, we can use any standard algorithm, like Dijskstra’s algorithm.
After shortest paths are computed, we need to add them to our shortest path tree, and we shall add to our tree only the given triplet U, V and W, such as:
- W → length of the edge formed by the vertexes U and V;
Given the above definition we see that it is equivalent as saying that:
d+W = d[V];
Note that this “restriction” on the number of triplets we add to our tree is a direct consequence of the definition of “shortest path tree” (see Wikipedia for a more formal definition).
After both of the above steps are performed we still need to take one additional thing into account.
Since we have built our Shortest path tree, starting with vertex S, we have the ensurance that every possible shortest path uses only this trees’ edges.
However Chef’s algorithm is “smarter” and only goes trough the shortest edge on that tree, so, to finish the problem we need to only consider a “new tree” formed only by the shortest edges taken into account by Chef’s algorithm.
All that is left to do now is to count how many vertexes are reachable if we consider a given vertex S as our source. Say it is NUM vertexes. So we add NUM to our final answer.
However, such sub-problem as an easy solution now, as all we need to do is to run a DFS (Depth-First Search) starting on vertex S of this “new tree” which considers only edges selected by chef’s algorithm.
The modified DFS to apply to solve this problem can be implemented as the pseudo-code below:
// Pseudo – code for DFS algorithm
dfs(u)
mark_visited(u)
for all children v, of u
if v is not visited and and length_of_egde(v,u)=min
dfs(v)
where min stands for the minimal edge that does not lead to a visited vertex.
Now, all we need to do is to perform this DFS algorithm over all vertexes S that were added in the shortest-tree while we update our final answer, and the problem is complete.
Refer to setter’s and tester’s solution for implementation details.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.