Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Shortest Path in Directed Acyclic Graph

Sharing is caring!

Problem Statement

Given a weighted Directed Acyclic Graphs (DAG), find the shortest path to a particular point from the given starting point.
One thing you can do is apply an O(N*N) algorithm and find the shortest distance by calculating all the distances from each node to every other node. As you can guess, a better method exists. You should notice here that there is subproblem quality that exists here. If a particular node can be reached using two nodes, you can simply find the minimum of the values at the two nodes plus the cost for reaching to the node in question. So you are extending your previous solutions. Yes, Dynamic Programming. The reason you are able to find such an optimal substructure here is because a DAG can be linearized (Topologically sorted). For example, the above DAG is linearized as follows:
Now if we want to find the minimum distance from start S to A. All we need to do is see the minimum distances to reach the nodes from which A can be reached. In this case, these nodes are S and C. Now the minimum of these minimum distances for previous nodes (till S=0, till C=2) added with the cost of reaching from these nodes (from S = 1, from C=4), is our answer.

Solution

package problems;

import java.util.*;

public class DAGShortestPath {
    private static class Graph {
        private Map<Integer, Set<Integer>> nodes;
        private Map<Integer, Map<Integer, Integer>> weights;

        public Graph() {
            nodes = new HashMap<>();
            weights = new HashMap<>();
        }

        public void addEdge(int u, int v, int weight) {
            if (!nodes.containsKey(u)) {
                nodes.put(u, new HashSet<>());
            }

            if (!nodes.containsKey(v)) {
                nodes.put(v, new HashSet<>());
            }

            if (!weights.containsKey(u)) {
                weights.put(u, new HashMap<>());
            }

            nodes.get(u).add(v);
            weights.get(u).put(v, weight);
        }

        public Set<Integer> getNeighbors(int u) {
            return nodes.get(u);
        }

        public int getWeight(int u, int v) {
            if (!nodes.containsKey(u)) {
                throw new IllegalArgumentException(("Node " + u + " is not in the graph!"));
            } else {
                if (!weights.get(u).containsKey(v)) {
                    throw new IllegalArgumentException(("No edge " + u + "->" + v + " exists in the graph!"));
                } else {
                    return weights.get(u).get(v);
                }
            }
        }

        public List<Integer> getNodes() {
            return new LinkedList<>(nodes.keySet());
        }
    }


    private static Stack<Integer> topologicallySort(Graph g) {
        Stack<Integer> ans = new Stack<>();
        Stack<Integer> recursionStack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        List<Integer> nodes = g.getNodes();

        for (int s : nodes) {
            if (!visited.contains(s)) {
                recursionStack.push(s);
            }

            while (!recursionStack.isEmpty()) {
                int u = recursionStack.peek();
                visited.add(u);

                int uncompletedNeighborsCount = 0;
                for (int v : g.getNeighbors(u)) {
                    if (!visited.contains(v)) {
                        recursionStack.push(v);
                        uncompletedNeighborsCount++;
                    }
                }

                if (uncompletedNeighborsCount == 0) {
                    ans.push(u);
                    recursionStack.pop();
                }
            }
        }

        return ans;
    }

    private static int shortestPath(Graph g, int s, int t) {
        final int INF = 1000;
        Stack<Integer> nodes = topologicallySort(g);
        int[] dp = new int[nodes.size() + 1];

        for (int v = 0; v < dp.length; v++) {
            dp[v] = INF;
        }
        dp[s] = 0;

        // Process nodes in topological order
        while (!nodes.isEmpty()) {
            int u = nodes.pop();
            for (int v : g.getNeighbors(u)) {
                dp[v] = Math.min(dp[v], dp[u] + g.getWeight(u, v));
            }
        }

        return dp[t];
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 3, 99);
        g.addEdge(2, 3, 123);
        g.addEdge(2, 4, 88);
        g.addEdge(3, 5, 67);
        g.addEdge(4, 6, 101);
        g.addEdge(5, 6, 123);
        g.addEdge(5, 8, 45);
        g.addEdge(6, 7, 75);

        System.out.println(shortestPath(g, 2, 7));
    }
}