A competitive runner would like to create a route that starts and ends at his house, with the condition that the route goes entirely uphill at first, and then entirely downhill.
Given a dictionary of places of the form {location: elevation}, and a dictionary mapping paths between some of these locations to their corresponding distances, find the length of the shortest route satisfying the condition above. Assume the runner's home is location 0.
For example, suppose you are given the following input:
elevations = {0: 5, 1: 25, 2: 15, 3: 20, 4: 10}
paths = {
(0, 1): 10,
(0, 2): 8,
(0, 3): 15,
(1, 3): 12,
(2, 4): 10,
(3, 4): 5,
(3, 0): 17,
(4, 0): 10
}
In this case, the shortest valid path would be 0 -> 2 -> 4 -> 0, with a distance of 28.
Solution 1. Dijkstra's algorithm to compute shortest path from a single source
1. Construct two subgraphs, one with only rising edges, the other one with only falling edges. For the falling edges only graph, revert all edges' direction so we can apply the Dijkstra's single source shortest path algorithm.
2. Apply Dijkstra's algorithm on rising-edge subgraph to compute the shortest path from location 0 to all other locations on rising-only edges; Then apply Dijkstra's algorithm again on falling-edge subgraph to compute the shortest path from all other locations to location 0 on falling-only edges. Denote these two results as rising[] and falling[].
3. Iterate through all other locations on rising[] and falling[] and find the minimum sum.
The runtime is O(V + E * log E), space is O(V + E)
public class ShortestRouteWithRestriction { public static int shortestRouteWithRestriction(int[] elevations, int[][] paths) { int n = elevations.length; int[] rising = new int[n]; int[] falling = new int[n]; Arrays.fill(rising, Integer.MAX_VALUE); Arrays.fill(falling, Integer.MAX_VALUE); Map<Integer, List<int[]>> risingGraph = new HashMap<>(); Map<Integer, List<int[]>> fallingGraph = new HashMap<>(); for(int i = 0; i < n; i++) { risingGraph.put(i, new ArrayList<>()); fallingGraph.put(i, new ArrayList<>()); } //construct graph with only rising/falling paths for(int i = 0; i < paths.length; i++) { if(paths[i][1] > paths[i][0]) { risingGraph.get(paths[i][0]).add(new int[]{paths[i][1], paths[i][2]}); } else if(paths[i][1] < paths[i][0]) { fallingGraph.get(paths[i][1]).add(new int[]{paths[i][0], paths[i][2]}); } } dijkstra(risingGraph, rising, 0); dijkstra(fallingGraph, falling, 0); int res = Integer.MAX_VALUE; for(int i = 1; i < n; i++) { if(rising[i] < Integer.MAX_VALUE && falling[i] < Integer.MAX_VALUE) { res = Math.min(res, rising[i] + falling[i]); } } return res; } private static void dijkstra(Map<Integer, List<int[]>> g, int[] distance, int startNode) { boolean[] processed = new boolean[distance.length]; distance[startNode] = 0; PriorityQueue<int[]> minPq = new PriorityQueue<>((a1, a2) -> {return a1[0] - a2[0];}); minPq.add(new int[]{0, startNode}); while(!minPq.isEmpty()) { int[] curr = minPq.poll(); int currNodeDistance = curr[0]; int currNodeLabel = curr[1]; if(processed[currNodeLabel]) { continue; } processed[currNodeLabel] = true; for(int[] edge : g.get(currNodeLabel)) { int neighborNodeLabel = edge[0]; int weight = edge[1]; if(currNodeDistance + weight < distance[neighborNodeLabel]) { distance[neighborNodeLabel] = currNodeDistance + weight; minPq.add(new int[]{distance[neighborNodeLabel], neighborNodeLabel}); } } } } public static void main(String[] args) { int[] elevations = {5,25,15,20,10}; int[][] paths = {{0, 1, 10}, {0, 2, 8}, {0, 3, 15}, {1, 3, 12}, {2, 4, 10}, {3, 4, 5}, {3, 0, 17}, {4, 0, 10}}; System.out.println(shortestRouteWithRestriction(elevations, paths)); } }
Solution 2. Topological Sort to compute shortest path from a single source
Similar with solution 1, we still divide the original problem into two subproblems. But we can compute the uphill only and downhill only distances more efficiently. If we only consider only uphill or only downhill path segments, it will be impossible to form a cycle, so we are dealing with a DAG. As a result, for each of these two subproblems, we can use a topological sort to determine in what order to visit the locations starting from 0.(for downhill, we revert the edge directions just like solution 1). Then we use this ordering to find the minimum cost path for each subproblem.
Both the runtime and space complexity are O(V + E).
public class ShortestRouteWithRestriction { public static int shortestRouteWithRestriction(int[] elevations, int[][] paths) { int n = elevations.length; Map<Integer, List<int[]>> risingGraph = new HashMap<>(); Map<Integer, List<int[]>> fallingGraph = new HashMap<>(); for(int i = 0; i < n; i++) { risingGraph.put(i, new ArrayList<>()); fallingGraph.put(i, new ArrayList<>()); } //construct graph with only rising/falling paths for(int i = 0; i < paths.length; i++) { if(paths[i][1] > paths[i][0]) { risingGraph.get(paths[i][0]).add(new int[]{paths[i][1], paths[i][2]}); } else if(paths[i][1] < paths[i][0]) { fallingGraph.get(paths[i][1]).add(new int[]{paths[i][0], paths[i][2]}); } } Stack<Integer> risingOrder = topologicalSort(risingGraph, 0); Stack<Integer> fallingOrder = topologicalSort(fallingGraph, 0); int[] rising = getDistance(risingGraph, risingOrder); int[] falling = getDistance(fallingGraph, fallingOrder); int res = Integer.MAX_VALUE; for(int i = 1; i < n; i++) { if(rising[i] < Integer.MAX_VALUE && falling[i] < Integer.MAX_VALUE) { res = Math.min(res, rising[i] + falling[i]); } } return res; } private static Stack<Integer> topologicalSort(Map<Integer, List<int[]>> g, int startNode) { boolean[] visited = new boolean[g.size()]; Stack<Integer> stack = new Stack<>(); topologicalSortHelper(g, startNode, visited, stack); return stack; } private static void topologicalSortHelper(Map<Integer, List<int[]>> g, int currNode, boolean[] visited, Stack<Integer> stack) { if(!visited[currNode]) { for(int[] edge : g.get(currNode)) { topologicalSortHelper(g, edge[0], visited, stack); } visited[currNode] = true; stack.push(currNode); } } private static int[] getDistance(Map<Integer, List<int[]>> g, Stack<Integer> order) { int[] distance = new int[g.size()]; Arrays.fill(distance, Integer.MAX_VALUE); distance[0] = 0; while(!order.isEmpty()) { int curr = order.pop(); for(int[] edge : g.get(curr)) { distance[edge[0]] = Math.min(distance[edge[0]], distance[curr] + edge[1]); } } return distance; } }