import java.util.*; class Vertex { String name; Vertex predecessor; boolean visited; List adjList; int distance = Integer.MAX_VALUE; Vertex(String name){ this.name = name; this.visited = false; adjList = new ArrayList<>(); } @Override public String toString() { return this.name; } } class Edge { Vertex startVertex,targetVertex; int weight; Edge(int weight, Vertex startVertex, Vertex targetVertex) { this.startVertex = startVertex; this.targetVertex = targetVertex; this.weight = weight; } } class Topo { Stack stack; Topo() { this.stack = new Stack<>(); } void makeTopSort(List vertexList) { for(Vertex v : vertexList){ if(!v.visited) { dfs(v); } } } void dfs(Vertex vertex) { for(Edge edge : vertex.adjList) { if(!edge.targetVertex.visited) { edge.targetVertex.visited = true; dfs(edge.targetVertex); // very important } } this.stack.push(vertex); } Stack getStack() { Collections.reverse(stack); return stack; } } class DAG { void shortestPath(List vertexList, Vertex sourceVertex, Vertex destinationVertex) { sourceVertex.distance = 0; Topo ts = new Topo(); ts.makeTopSort(vertexList); Stack sorted = ts.getStack(); System.out.println("Topo is "+sorted); for(Vertex vertex: sorted) { for(Edge e: vertex.adjList) { Vertex u = e.startVertex; Vertex v = e.targetVertex; int newDistance = e.weight + u.distance; if(newDistance < v.distance) { v.distance = newDistance; v.predecessor = u; } } } if(destinationVertex.distance == Integer.MAX_VALUE) { System.out.println("No shortest path"); }else { System.out.println("Shortest path is "+destinationVertex.distance); } } void showPath(Vertex destinationVertex) { List list= new ArrayList<>(); Vertex n = destinationVertex; list.add(n); while(n.predecessor != null ) { n = n.predecessor; list.add(n); } Collections.reverse(list); System.out.println(list); } } public class App { public static void main(String args[]) { Vertex v0 = new Vertex("v0"); Vertex v1 = new Vertex("v1"); Vertex v2 = new Vertex("v2"); List vertexList = new ArrayList<>(); vertexList.add(v0); vertexList.add(v1); vertexList.add(v2); v0.adjList.add(new Edge(1,v0,v1)); v0.adjList.add(new Edge(10,v0,v2)); v1.adjList.add(new Edge(1,v1,v2)); DAG dag = new DAG(); dag.shortestPath(vertexList, v0, v2); dag.showPath(v2); } }

DAG Shortest path