单源最短路径-Dijkstra算法

单源最短路径-Dijkstra算法

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 Dijkstra { private Node [][]graphic; private Node s; private Set nextNodes=new HashSet(); public Dijkstra(int v,int e){ graphic=new Node[v][v]; for(int i=0;i0){ Node node=extractMin(); for(int k=0;k it = nextNodes.iterator(); Node node=null; while(it.hasNext()){ if(node==null){ node=it.next(); }else{ Node n=it.next(); if(n.du.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; System.out.println(graphic[v.end][v.end].start+"=>"+u.start); } } public void print(){ for(int i=0;i indexList=new ArrayList(); List removeList=new ArrayList(); List addList=new ArrayList(); indexList.add(0); 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) { Dijkstra d=new Dijkstra(5,20); d.print(); d.dijkstra(); d.printPath(); }}

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