(ArrayList<Edge>[] graph,int src)
| 61 | } |
| 62 | |
| 63 | public static void shortPath(ArrayList<Edge>[] graph,int src){ |
| 64 | boolean []flag=new boolean[graph.length] ; |
| 65 | |
| 66 | PriorityQueue<Pair> pq = new PriorityQueue<>(); |
| 67 | pq.add(new Pair(src,""+src,0)) ; |
| 68 | |
| 69 | while(pq.size()>0){ |
| 70 | Pair top=pq.remove() ; |
| 71 | if(flag[top.vtx]) continue ; |
| 72 | flag[top.vtx]=true ; |
| 73 | System.out.println(top.vtx+" via "+top.path+" @ "+top.wt) ; |
| 74 | for(Edge e:graph[top.vtx]){ |
| 75 | if(!flag[e.nbr]) pq.add(new Pair(e.nbr,top.path+e.nbr,top.wt+e.wt)) ; |
| 76 | } |
| 77 | |
| 78 | } |
| 79 | |
| 80 | |
| 81 | |
| 82 | } |
| 83 | } |