Java Approach with Topological Sort


  • 0
    W

    This problem can can solved with Dynamic programming, however you can also solve it as a graph theory problem. Notice that the graph we create from the matrix is a directed acyclic graph meaning that we can actually apply a topological sorting on the nodes of the graph and find the shortest path in O(V + E) time!

    class Edge {
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    
    public class Solution {
        
        // Construct graph from input matrix
        public Map<Integer, List<Edge>> createGraph( int[][] grid, int rows, int cols ) {
            
            int k = rows*cols;
            Map<Integer, List<Edge>> graph = new HashMap<>();
    
            for(int i = 0; i < rows; i++) {
                for(int j = 0; j < cols; j++) {
                    
                    int from = i*cols+j;
                    List<Edge> edges = new ArrayList<Edge>(2);
    
                    // Connect Bottom Edge
                    if (i+1 < rows) {
                        int to = from + cols;
                        Edge e = new Edge( from, to, grid[i+1][j] );
                        edges.add(e);
                    }
                    
                    // Connect Right Edge
                    if (j+1 < cols) {
                        int to = from + 1;
                        Edge e = new Edge( from, to, grid[i][j+1] );
                        edges.add(e);
                    }
                    
                    graph.put( from, edges );
                    
                }
            }
            
            return graph;
            
        }
        
        private void topologicalSortDFS( int node, boolean[] visited, Stack<Integer> order,  Map<Integer, List<Edge>> graph ) {
            
            visited[node] = true;
            
            List<Edge> edges = graph.get(node);
            if (edges != null) {
                for(Edge edge : edges) {
                    if (!visited[edge.to]) {
                        topologicalSortDFS( edge.to, visited, order, graph );                
                    }
                }            
            }
    
            order.push( node );
            
        }
        
        // Create topological sort 
        public Stack<Integer> topologicalSort( Map<Integer, List<Edge>> graph ) {
            
            Stack<Integer> order = new Stack<>();
            boolean[] visited = new boolean[ graph.size() ];
            
            for(int i = 0; i < graph.size(); i++)
                if (!visited[i])
                    topologicalSortDFS( i, visited, order, graph );
    
            return order;
            
        }
        
        
        // get the shortest distance to every node
        public Integer[] shortestPathDAG( Map<Integer, List<Edge>> graph, int startNode, int numNodes ) {
            
            Stack<Integer> ordering = topologicalSort(graph);
            Integer[] dist = new Integer[ numNodes ];
            dist[startNode] = 0;
            
            while(!ordering.isEmpty()) {
                
                Integer node = ordering.pop();
                List<Edge> edges = graph.get(node);
                if (edges != null) {
                    for(Edge edge : edges) {
                        if (dist[edge.to] == null) {
                            dist[edge.to] = dist[edge.from] + edge.weight;
                        } else {
                            dist[edge.to] = Math.min(dist[edge.to], dist[edge.from] + edge.weight);
                        }
                    }                
                }
            }
            
            return dist;
            
        }
            
        public int minPathSum(int[][] grid) {
            
            int rows = grid.length;
            if (rows == 0) return 0;
            
            int cols = grid[0].length;
            if (cols == 0) return 0;
    
            Map<Integer, List<Edge>> graph = createGraph( grid, rows, cols );
            Integer[] pathDist = shortestPathDAG(graph, 0, rows*cols);
            
            int endNode = rows*cols-1;
            return pathDist[endNode] + grid[0][0];
            
        }
        
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.