# Java Approach with Topological Sort

• 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] );
}

// Connect Right Edge
if (j+1 < cols) {
int to = from + 1;
Edge e = new Edge( from, to, grid[i][j+1] );
}

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];

}

}
``````

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