最短路径问题
程序员文章站
2022-05-08 13:29:46
...
这个算法的实现是基于图的邻接矩阵表示法。这里使用的是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