最短路径问题

  这个算法的实现是基于图的邻接矩阵表示法。这里使用的是Dijkstra来计算最短路径。

 

 //下面是代码：package testShortPath;

public class Vertex {
	public char label;
	public boolean isVisited;
	
	public Vertex(char label) {
		this.label = label;
	}
}

 package testShortPath;

public class ShortDistAndPath {
	public int distance;
	
	public ShortDistAndPath(int distance) {
		this.distance = distance;
	}
}

 package testShortPath;

import java.util.ArrayList;
import java.util.List;

public class Graph {
	/**最大的顶点数目*/
	private final int MAX_VERTS = 20;
	/**无穷大*/
	private final int INFINITY = 1000000;
	/**顶点列表*/
	private Vertex[] vertexList;
	/**邻接矩阵*/
	private int[][] adjMat;
	/**顶点数目*/
	private int vertNum;
	/**访问过的顶点数目*/
	private int visitedVertNum;
	/**最短路径以及路径的数组*/
	private ShortDistAndPath[] shortDistAndPathStrs;
	/**当前的顶点*/
	private int currentVert;
	/**指定顶点距当前顶点的距离*/
	private int startToCurrentDist;
	
	public Graph() {
		vertexList = new Vertex[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		vertNum = 0;
		visitedVertNum = 0;
		for(int j=0;j<MAX_VERTS;j++) {
			for(int k = 0;k < MAX_VERTS;k++) {
				adjMat[j][k] = INFINITY;
			}
		}
		shortDistAndPathStrs = new ShortDistAndPath[MAX_VERTS];
	}
	
	public void addVertex(char lab){
		vertexList[vertNum ++] = new Vertex(lab);
	}
	
	public void addEdge(int start,int end,int weight) {
		adjMat[start][end] = weight;
	}
	
	/**
	 * 算法的核心
	 */
	public void path() {
		int startTree = 0;
		vertexList[startTree].isVisited = true;
		visitedVertNum = 1;
		for(int i=0;i<vertNum;i++) {
			shortDistAndPathStrs[i] = new ShortDistAndPath(adjMat[startTree][i]);
		}
		while (visitedVertNum < vertNum) {
			int minIndex = getMin();
			int minDist = shortDistAndPathStrs[minIndex].distance;
			if(minDist == INFINITY) {
				System.out.println("There are unreachable vertices.");
				break;
			} else {
				currentVert = minIndex;
				startToCurrentDist = minDist;
			}
			vertexList[currentVert].isVisited = true;
			visitedVertNum ++;
			adjust_sPath();
		}
		displayPaths();
	}
	
	/**
	 * 得到未访问的，最短路径的顶点的下标
	 * @return
	 */
	public int getMin() {
		int minDist = INFINITY;
		int minIndex = 0;
		for(int i=0;i<vertNum;i++) {
			if(!vertexList[i].isVisited && shortDistAndPathStrs[i].distance < minDist) {
				minDist = shortDistAndPathStrs[i].distance;
				minIndex = i;
			}
		}
		return minIndex;
	}
	
	public void adjust_sPath() {
		int vertIndex = 1;
		while(vertIndex < vertNum) {
			if(vertexList[vertIndex].isVisited) {
				vertIndex ++;
				continue;				
			}
			int specificToNext = startToCurrentDist + adjMat[currentVert][vertIndex];
			int shortDist = shortDistAndPathStrs[vertIndex].distance;
			if(shortDist > specificToNext) {
				shortDistAndPathStrs[vertIndex].distance = specificToNext;
			}
			vertIndex ++;
		}
	}
	
	public void displayPaths() {
		for(int j=0;j<vertNum;j++) {
			System.out.print(vertexList[0].label + "-->" + vertexList[j].label + "=");
			if(shortDistAndPathStrs[j].distance == INFINITY) {
				System.out.print("inf");
			} else {
				System.out.print(shortDistAndPathStrs[j].distance);
			}
			System.out.println();
		}
	}
	
	/**
	 * Test
	 * @param args
	 */
	public static void main(String[] args) {
		Graph theGraph = new Graph();
		
		theGraph.addVertex('A');//0
		theGraph.addVertex('B');//1
		theGraph.addVertex('C');//2
		theGraph.addVertex('D');//3
		theGraph.addVertex('E');//4
		
		theGraph.addEdge(0, 1, 50);
		theGraph.addEdge(0, 3, 80);
		theGraph.addEdge(1, 2, 60);
		theGraph.addEdge(1, 3, 90);
		theGraph.addEdge(2, 4, 40);
		theGraph.addEdge(3, 2, 20);
		theGraph.addEdge(3, 4, 70);
		theGraph.addEdge(4, 1, 50);
		
		theGraph.path();
		System.out.println();
		
	}
}

   运行结果为：

A-->A=inf

A-->B=50

A-->C=100

A-->D=80

A-->E=140