有向无环图的单源最短路径

有向无环图的单源最短路径

package com.data.struct;import java.util.ArrayList;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Random;import java.util.Set;public class OrderedGraphicShortestPath { private Node [][]graphic; private Node s; private Set nextNodes=new HashSet(); private Set addList=new HashSet(); private Set removeList=new HashSet(); private int time=0; private List sortList=new ArrayList(); public OrderedGraphicShortestPath(int v,int e){ graphic=new Node[v][v]; for(int i=0;iu.d+graphic[u.start][v.start].w){ graphic[v.end][v.end].d=u.d+graphic[u.start][v.start].w; graphic[v.end][v.end].parent=u; addList.add(graphic[v.end][v.end]); System.out.println(graphic[v.end][v.end].start+"=>"+u.start); } } private void depthFirstSearch(){ for(int i=0;i0){ addList.clear();removeList.clear(); Iterator it=nextNodes.iterator(); while(it.hasNext()){ Node node=it.next(); for(int k=0;k indexList=new ArrayList(); List removeList=new ArrayList(); List addList=new ArrayList(); indexList.add(sortList.get(0).start); while(indexList.size()>0){ removeList.clear(); addList.clear(); for(int x=0;x children = node.children; for(int i=0;i children=new ArrayList(); } public static void main(String[] args) { OrderedGraphicShortestPath o=new OrderedGraphicShortestPath(5,20); o.print(); //o.depthFirstSearch(); o.printSort(); o.shortestPath(); o.printPath(); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。