/**
* 这是一个点对点(S-T)Dijkstra算法的具体实现。用于求两点间的最短路径。
* @author Fe
*/
public class STDijkstra {
/**
* 所求路经所在图的邻接链表引用。
*/
GraphAdjList graphAdjList[] = null;
/**
* 图中总的结点数。
*/
int totalNodeNum;
/**
* 源结点和目标结点。
*/
int sourceNode, targetNode;
/**
* 两结点间的路径长度。
*/
int distance = -1;
/**
* 求得最短路径子图中的每个结点的前驱结点。用于求出从源结点到目标结点的一条通路。
*/
int preNodes[] = null;
/**
* 用一个图的邻接表引用构造一个实例引用。
* @param graph
* 图的邻接表引用
*/
public STDijkstra(GraphAdjList graph[]) {
graphAdjList = graph;
totalNodeNum = graphAdjList.length;
preNodes = new int[totalNodeNum];
}
/**
* 用一个图的邻接表以及源结点和目标结点构造一个实例引用。
* @param graph
* 图的邻接表引用
* @param source
* 源结点
* @param target
* 目标结点
*/
public STDijkstra(GraphAdjList graph[], int source, int target) {
graphAdjList = graph;
totalNodeNum = graphAdjList.length;
preNodes = new int[totalNodeNum];
setST(source, target);
}
/**
* 设置源结点和目标结点。用于求不同的结点间的最短路径。
* @param s
* 源结点
* @param t
* 目标结点
*/
public void setST(int s, int t) {
sourceNode = s;
targetNode = t;
for (int i = 0; i < totalNodeNum; i++) {
preNodes[i] = sourceNode;
}
}
/**
* 返回所求最短路径的路径长度。
* @return
* 所求路径的总路径长度
*/
public int getDistance() {
return distance;
}
/**
* 返回从结点s到结点t得最短路径长度。
* @param s
* 源结点
* @param t
* 目标结点
* @return
* 所求得的最短路径长度
*/
public int getDistance(int s, int t) {
setST(s, t);
go();
return distance;
}
/**
* 返回所求结点间最短路径经过的结点序列。其中，path[0]为目标结点。
* @return
* 所求结点间最短路径经过的结点序列
*/
public int[] getPath() {
int temp = targetNode;
int nodeNumInPath = 1;
while (temp != sourceNode) {
nodeNumInPath++;
temp = preNodes[temp];
}
int path[] = new int[nodeNumInPath];
path[0] = targetNode;
temp = targetNode;
int nextPathNode = 1;
while (temp != sourceNode) {
temp = preNodes[temp];
path[nextPathNode] = temp;
nextPathNode++;
}
return path;
}
/**
* 计算从s到t的最短路径信息。
* @param s
* 源结点
* @param t
* 目标结点
*/
public void go(int s, int t) {
setST(s, t);
go();
}
/**
* Dijkstra(S-T)算法的具体实现。
*/
public void go() { //暂不考虑非连同情形，待改进。
//用于存储从源结点到其他各个结点的最短路径长度的temp。
int distanceTemp[] = new int[totalNodeNum];
//初始时将从源结点到其他各个结点的最短路径长度全都设置为无穷远。除源结点到自身的长度为0。
for (int i = 0; i < totalNodeNum; i++) {
distanceTemp[i] = 0X0FFFFFFF;
}
distanceTemp[sourceNode] = 0;
//根据图的邻接表具有的信息，将于源结点邻接的结点的路径长度设置为边的权值，其余不变，作为长度初始值。
NextAdjNode temp = null;
temp = graphAdjList[sourceNode].firstNode;
distanceTemp[temp.nodeNum] = temp.edgeWeight;
while (temp.nextNode != null) {
temp = temp.nextNode;
distanceTemp[temp.nodeNum] = temp.edgeWeight;
}
//已经找到的在最短路径子图中的结点i对应的hasInPath[i]设置为true，其余设置为false。初始值全为false。
boolean hasInPath[] = new boolean[totalNodeNum];
for (int i = 0; i < totalNodeNum; i++) {
hasInPath[i] = false;
}
//nextNode为所要找的下一个到源结点路径最短的结点。
int nextNode = -1;
//当找到的结点不是目标结点时，继续找下一个结点。
while (nextNode != targetNode) {
//下一个结点为不在已找到的最短路径子图中的结点中离源结点路径最短的结点。
nextNode = chooseNextPathNode(distanceTemp, hasInPath);
//将此结点加入到最短路径子图中。
hasInPath[nextNode] = true;
//通过新找到的结点，比较剩余结点结点到源结点的路径。
//若源结点通过新结点到剩余某结点的总路径小于目前源结点到某结点的路径，则修改源结点到某结点的路径。
updateDistance(nextNode, distanceTemp, hasInPath);
}
//将最终从源结点到目标结点的路径长度赋给distance。
distance = distanceTemp[targetNode];
}
/**
* 找下一个结点。<br>下一个结点为不在已找到的最短路径子图中的结点中离源结点路径最短的结点。
* @param distanceTemp
* 目前从源结点到各结点的距离
* @param hasInPath
* 已经在最短路径子图中的结点
* @return
* 找到的下一个结点的索引。
*/
private int chooseNextPathNode(int distanceTemp[], boolean hasInPath[]) {
int temp = 0X0FFFFFFF;
int nextNode = -1;
for (int i = 0; i < totalNodeNum; i++) {
if (!hasInPath[i]) {
if (temp > distanceTemp[i]) {
temp = distanceTemp[i];
nextNode = i;
}
}
}
return nextNode;
}
/**
* 通过新找到的结点，比较剩余结点结点到源结点的路径。
* <br>若源结点通过新结点到剩余某结点的总路径小于目前源结点到某结点的路径，则修改源结点到某结点的路径。
* @param currentNode
* 刚刚找到的到源结点路径最短的结点的索引
* @param distanceTemp
* 目前从源结点到各结点的距离
* @param hasInPath
* 已经在最短路径子图中的结点
*/
private void updateDistance(int currentNode, int distanceTemp[], boolean hasInPath[]) {
NextAdjNode temp = graphAdjList[currentNode].firstNode;
while (temp != null) {
if (!hasInPath[temp.nodeNum]) {
if (distanceTemp[currentNode] + temp.edgeWeight < distanceTemp[temp.nodeNum]) {
distanceTemp[temp.nodeNum] = distanceTemp[currentNode] + temp.edgeWeight;
preNodes[temp.nodeNum] = currentNode;
}
}
temp = temp.nextNode;
}
}
}