Dijkstra最短路径算法
import java.util.ArrayList; /** * @ClassName: Graph * @Description: 基于Dijkstra算法的最短路径求解 * @author zhoupengcheng * @version 2015年4月29日上午9:37:43 */ public class Graph { private final int MAX_NUM = 20000; private final int INFINITY = 100000; private ArrayList<Vertex> vertexList;// ArrayList保存所有结点 private int adjMatrix[][];//邻接矩阵 private int nVerts;// 保存当前图中当前顶点数 private int nTree; // 保存已经加入到最短路径上的结点 //private DistPar sPath[];//保存源点到每个点的当前最短路径距离 private ArrayList<DistPar> sPath; private int currentVert;//搜索最短路径到达的当前结点 private int startToCurrent;//源点到当前结点的(最短)距离 //--------------------构造函数-------------------- public Graph(){ vertexList=new ArrayList<Vertex>(); adjMatrix=new int[MAX_NUM][MAX_NUM]; nVerts=0; nTree=0; for(int i=0;i<MAX_NUM;i++){ for(int j=0;j<MAX_NUM;j++) adjMatrix[i][j]=INFINITY; } //sPath=new DistPar[MAX_NUM]; sPath=new ArrayList<DistPar>(); } //--------------------------------------------- public void addVertex(String lab,int id){ vertexList.add(new Vertex(lab,id)); nVerts++; } //--------------------------------------------- public void addEdge(int start, int end,int weight) { adjMatrix[start][end] = weight;//有向带权图 } //--------------------------------------------- public void path(int startTree){//寻找最短路径 //int startTree=0;//假设都是从下标为0的点开始搜索 vertexList.get(startTree).isIntree=true; nTree=1; //根据邻接矩阵中两点的权值构造初始的sPath,sPath在搜索最短路径的过程中不断更新 for(int k=0;k<nVerts;k++){ int tmpDist=adjMatrix[startTree][k]; //sPath[k]=new DistPar(startTree,tmpDist); sPath.add(new DistPar(startTree,tmpDist)); } //直到所有的结点都已经加入到最短路径中,否则继续迭代 while(nTree<nVerts){ int indexMin=getMin();//从sPath中获取最小的路径 //int minDist=sPath[indexMin].distance; int minDist=sPath.get(indexMin).distance; if(minDist==INFINITY){ System.out.println("无法到达未连通的结点!"); break; }else{ currentVert=indexMin; //startToCurrent=sPath[indexMin].distance; startToCurrent=sPath.get(indexMin).distance; } vertexList.get(currentVert).isIntree=true; nTree++; adjust_sPath(); } displayPaths(startTree);//打印最短路径搜索结果 nTree=0; //清空标志位,还原一个没有遍历过的树 for(int j=0;j<nVerts;j++){ vertexList.get(j).isIntree=false; } } //------------从sPath中获得一个离源点距离最短的结点---------- private int getMin() { // TODO Auto-generated method stub int minDist=INFINITY; int indexMin=0; for(int j=0;j<nVerts;j++){ if(!vertexList.get(j).isIntree&&sPath.get(j).distance<minDist){ indexMin=j; minDist=sPath.get(j).distance; } } return indexMin; } //------------调整sPath中的值,更新最新的最短距离(距源点)------------ private void adjust_sPath() { // TODO Auto-generated method stub int column=0;//起始点就不要更新了 while(column<nVerts){ if(vertexList.get(column).isIntree) { column++; continue; } int currentToFringe=adjMatrix[currentVert][column]; int startToToFringe=currentToFringe+startToCurrent; int sPathDist=sPath.get(column).distance; if(startToToFringe<sPathDist){ sPath.get(column).distance=startToToFringe; sPath.get(column).parentVert=currentVert; } column++; } } private void displayPaths(int srcVertex) { // TODO Auto-generated method stub for(int i=0;i<nVerts;i++){ System.out.print(vertexList.get(i).label+"="); if(sPath.get(i).distance==INFINITY){ System.out.print("inf"); }else{ System.out.print(sPath.get(i).distance); } String parent=vertexList.get(sPath.get(i).parentVert).label; System.out.print("("+parent+") "); } System.out.println(); // 打印源点到图中每个点走过的最短路径,根据DistPar对象的parent结点来找路径 for (int j = 0; j < nVerts; j++) { if (sPath.get(j).distance == INFINITY) continue; if (j == srcVertex) continue; int x = sPath.get(j).parentVert; if (x == srcVertex) { System.out.print(vertexList.get(j).label + "<-" + vertexList.get(srcVertex).label + " "); } else { System.out.print(vertexList.get(j).label + "<-"); while (x != srcVertex) { System.out.print(vertexList.get(x).label + "<-"); x = sPath.get(x).parentVert; } System.out.print(vertexList.get(srcVertex).label); } System.out.println(""); } } }
/** * @ClassName: Main * @Description: 工程的main函数 * @author zhoupengcheng * @version 2015年4月29日上午9:39:12 */ public class Main { public static void main(String[] args) { Graph theGraph = new Graph(); int num = 0; theGraph.addVertex("A", num++); // 0 (start) theGraph.addVertex("B", num++); // 1 theGraph.addVertex("C", num++); // 2 theGraph.addVertex("D", num++); // 3 theGraph.addVertex("E", num++); // 4 //theGraph.addVertex("F", num++); // 5 theGraph.addEdge(0, 1, 50); // AB 50 theGraph.addEdge(0, 3, 80); // AD 80 theGraph.addEdge(1, 2, 60); // BC 60 theGraph.addEdge(1, 3, 90); // BD 90 theGraph.addEdge(2, 4, 40); // CE 40 theGraph.addEdge(3, 2, 20); // DC 20 theGraph.addEdge(3, 4, 70); // DE 70 theGraph.addEdge(4, 1, 50); // EB 50 //构造无向图 // theGraph.addEdge(1, 0, 50); // AB 50 // theGraph.addEdge(3, 0, 80); // AD 80 // theGraph.addEdge(2, 1, 60); // BC 60 // theGraph.addEdge(3, 1, 90); // BD 90 // theGraph.addEdge(4, 2, 40); // CE 40 // theGraph.addEdge(2, 3, 20); // DC 20 // theGraph.addEdge(4, 3, 70); // DE 70 // theGraph.addEdge(1, 4, 50); // EB 50 System.out.println("Shortest paths"); theGraph.path(0); // 设置源点 System.out.println(); } }
/** * @ClassName: DistPar * @Description: 此类的实例是存放在sPath数组中的 * @author zhoupengcheng * @version 2015年4月29日上午9:40:38 */ public class DistPar { public int distance;// 保存源点(起点)到此结点的当前最短距离 public int parentVert;// 在最短路径中此结点的上一个(父)结点,设置此属性是为了方便输出路径序列 public DistPar(int parent,int distance) { // TODO Auto-generated constructor stub this.parentVert=parent; this.distance=distance; } }
/** * @ClassName: Vertex * @Description: 结点类 * @author zhoupengcheng * @version 2015年4月29日上午9:41:03 */ public class Vertex { public String label;//节点的内容,一个元组的数据摘要 public boolean isIntree;//标记该点是否已经包含在最短路径中 public int id;//标识这个数据结点,到时要输出包含关键词节点的ID另作处理 public Vertex(String label,int id){ this.label=label; this.id=id; this.isIntree=false; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。