import java.util.ArrayList;/** * @ClassName: Graph * @Description: 基于Dijkstra算法的最短路径求解 * @authorzhoupengcheng * @version2015年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 stubint 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 stubint 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 stubfor(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函数 * @authorzhoupengcheng * @version2015年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++); // 1theGraph.addVertex("C", num++); // 2theGraph.addVertex("D", num++); // 3theGraph.addVertex("E", num++); // 4//theGraph.addVertex("F", num++); // 5theGraph.addEdge(0, 1, 50); // AB 50theGraph.addEdge(0, 3, 80); // AD 80theGraph.addEdge(1, 2, 60); // BC 60theGraph.addEdge(1, 3, 90); // BD 90theGraph.addEdge(2, 4, 40); // CE 40theGraph.addEdge(3, 2, 20); // DC 20theGraph.addEdge(3, 4, 70); // DE 70theGraph.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 50System.out.println("Shortest paths");theGraph.path(0); // 设置源点System.out.println();}}/** * @ClassName: DistPar * @Description: 此类的实例是存放在sPath数组中的 * @authorzhoupengcheng * @version2015年4月29日上午9:40:38 */public class DistPar {public int distance;// 保存源点(起点)到此结点的当前最短距离public int parentVert;// 在最短路径中此结点的上一个(父)结点,设置此属性是为了方便输出路径序列public DistPar(int parent,int distance) {// TODO Auto-generated constructor stubthis.parentVert=parent;this.distance=distance;}}/** * @ClassName: Vertex * @Description: 结点类 * @authorzhoupengcheng * @version2015年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;}}
，年轻是我们唯一拥有权利去编织梦想的时光
