SPFA算法
2018-02-23 本文已影响35人
Stroman
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
int[][] testMatrix = {
{-1,-1,10,-1,30,100},
{-1,-1,5,-1,-1,-1},
{-1,-1,-1,50,-1,-1},
{-1,-1,-1,-1,0,10},
{-1,-1,-1,20,-1,60},
{-1,-1,-1,-1,-1,-1}
};
int[][] testMatrix0 = {
{-1,24,8,15,-1,-1,-1},
{-1,-1,-1,-1,6,-1,-1},
{-1,-1,-1,-1,7,3,-1},
{-1,-1,-1,-1,-1,-1,4},
{-1,-1,-1,-1,-1,-1,9},
{-1,-1,-1,-1,2,-1,3},
{-1,3,-1,-1,-1,-1,-1}
};
Spfa.spfa0(testMatrix,0);
}
}
package com.company;
public class Spfa {
/**
* 适用于单源最短路径问题，尤其适用于权值为负的情况。
* 它适用于有向图。
* 但是如果有向图中存在回路，并且回路的权值之和为负，
* 那么本图是无法用此算法求最短路径的，因为越求越小，
* 根本没有最小路径。
* 本算法的实质是一个广度优先搜索算法。
* 又叫动态逼近法。
* 为什么spfa所有队列中如果有一个结点，那么相同的结
* 点就不入队呢？
* 因为入队是因为以该顶点为中间点能够找到更短路径，
* 入队是要传达一个信息，该顶点具备可以使路径变得更
* 短的能力，它是一个标识而已，而有一个在队列中就能
* 够标识该顶点能够使路径变得更短了，就不需要第二个
* 了。
* 其他的也可能是为了不重复入队，减少一些不必要的操作吧，或
* 者限制队列的长度吧，这样确实可以确定地设置队列的
* 长度。
* 出去的点作为中间点，如果该顶点的出度加上它已有的
* 最小路径比从源点到其箭头顶点的距离更短，则更新从
* 源点到箭头顶点最短路径的值。
* @param sourceArray
* @param vertexId
*/
static public void spfa0(int[][] sourceArray,int vertexId) {
int arrayLength = sourceArray.length;
int maxValue = 0;
//获取最大值
for (int counter = 0;counter < arrayLength;counter++)
for (int counter0 = 0;counter0 < arrayLength;counter0++)
if (sourceArray[counter][counter0] > 0)
maxValue += sourceArray[counter][counter0];
int[] minPathArray = new int[arrayLength];
//这里以maxValue代表无穷大。
for (int counter = 0;counter < arrayLength;counter++) {
if (vertexId == counter)minPathArray[counter] = 0;
else minPathArray[counter] = maxValue;
}
//用来存储前驱的中间结点数组，也是结果集数组。
int[] preMiddleArray = new int[arrayLength];
//也把它初始化为-1
for (int counter = 0;counter < arrayLength;counter++)
preMiddleArray[counter] = -1;
//为了不让已经在队列中的顶点标号重复入队，所以
// 应该弄一个数组来标记有哪个顶点入队了。
boolean[] vertexFlag = new boolean[arrayLength];
for (int counter = 0;counter < arrayLength;counter++)
vertexFlag[counter] = false;
//由于队列中并不存在重复元素，
// 所以队列最长为arrayLength。
// 并且采用循环队列。
int[] minPathQueue = new int[arrayLength];
int front = 0;
int rear = front;
minPathQueue[rear] = vertexId;
vertexFlag[vertexId] = true;
System.out.println("标记数组的状态是");
for (boolean element:vertexFlag)
System.out.print((element?"O":"X") + " ");
System.out.println();
while ((rear + 1) % arrayLength != front) {
System.out.println("最短路径数组状态");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驱结点状态");
for (int element:preMiddleArray)
System.out.print(element + " ");
int currentMiddleIndex = minPathQueue[front++];
vertexFlag[currentMiddleIndex] = false;
System.out.println("\n顶点" + currentMiddleIndex + "出队");
System.out.println("并把顶点" + currentMiddleIndex + "标记为X");
System.out.println("标记数组的状态是");
for (boolean element:vertexFlag)
System.out.print((element?"O":"X") + " ");
System.out.println();
front = front % arrayLength;
for (int counter = 0;counter < arrayLength;counter++) {
//这个比较的术语叫做松弛，所以这一操作被称为松弛操作。
// 很形象，最初两个顶点之间有根橡皮筋，后来每次找到一
// 个能够使路径更短的中间点，就让橡皮筋更松弛一些，于
// 是松弛操作的直接意思就是找到了个中间点让原来两顶点
// 之间的路径更短了。
if (sourceArray[currentMiddleIndex][counter] > 0
&& minPathArray[currentMiddleIndex]
+ sourceArray[currentMiddleIndex][counter]
< minPathArray[counter]) {
if (!vertexFlag[counter]) {
minPathQueue[++rear % arrayLength] = counter;
vertexFlag[counter] = true;
System.out.println("顶点" + counter + "入队并被标记为O");
} else System.out.println("顶点" + counter + "无需重复入队");
System.out.println("标记数组的状态是");
for (boolean element:vertexFlag)
System.out.print((element?"O":"X") + " ");
System.out.println();
minPathArray[counter] = minPathArray[currentMiddleIndex]
+ sourceArray[currentMiddleIndex][counter];
preMiddleArray[counter] = currentMiddleIndex;
System.out.println("最短路径数组状态");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驱结点状态");
for (int element:preMiddleArray)
System.out.print(element + " ");
System.out.println();
}
}
System.out.println("顶点" + currentMiddleIndex + "处理完毕");
System.out.println("最短路径数组状态");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驱结点状态");
for (int element:preMiddleArray)
System.out.print(element + " ");
System.out.println("\n");
}
System.out.println("此时队列为空");
//下面打印从源顶点到各顶点的最短路径
System.out.println("结果集为:");
int[] minPathStack = new int[arrayLength];
for (int counter = 0;counter < arrayLength;counter++) {
if (counter == vertexId)continue;
System.out.print("(" + vertexId + "," + counter + "):");
if (minPathArray[counter] == maxValue) {
System.out.println("不可达");
continue;
}
int pathStackTopPointer = -1;
int preIndex = counter;
while (preMiddleArray[preIndex] != vertexId) {
minPathStack[++pathStackTopPointer] = preIndex;
preIndex = preMiddleArray[preIndex];
}
minPathStack[++pathStackTopPointer] = preIndex;
minPathStack[++pathStackTopPointer] = vertexId;
while (pathStackTopPointer > -1) {
if (counter == minPathStack[pathStackTopPointer])
System.out.print(minPathStack[pathStackTopPointer--]);
else System.out.print(minPathStack[pathStackTopPointer--] + "-->");
}
System.out.println();
}
}
}
输出
标记数组的状态是
O X X X X X
最短路径数组状态
0 285 285 285 285 285
前驱结点状态
-1 -1 -1 -1 -1 -1
顶点0出队
并把顶点0标记为X
标记数组的状态是
X X X X X X
顶点2入队并被标记为O
标记数组的状态是
X X O X X X
最短路径数组状态
0 285 10 285 285 285
前驱结点状态
-1 -1 0 -1 -1 -1
顶点4入队并被标记为O
标记数组的状态是
X X O X O X
最短路径数组状态
0 285 10 285 30 285
前驱结点状态
-1 -1 0 -1 0 -1
顶点5入队并被标记为O
标记数组的状态是
X X O X O O
最短路径数组状态
0 285 10 285 30 100
前驱结点状态
-1 -1 0 -1 0 0
顶点0处理完毕
最短路径数组状态
0 285 10 285 30 100
前驱结点状态
-1 -1 0 -1 0 0
最短路径数组状态
0 285 10 285 30 100
前驱结点状态
-1 -1 0 -1 0 0
顶点2出队
并把顶点2标记为X
标记数组的状态是
X X X X O O
顶点3入队并被标记为O
标记数组的状态是
X X X O O O
最短路径数组状态
0 285 10 60 30 100
前驱结点状态
-1 -1 0 2 0 0
顶点2处理完毕
最短路径数组状态
0 285 10 60 30 100
前驱结点状态
-1 -1 0 2 0 0
最短路径数组状态
0 285 10 60 30 100
前驱结点状态
-1 -1 0 2 0 0
顶点4出队
并把顶点4标记为X
标记数组的状态是
X X X O X O
顶点3无需重复入队
标记数组的状态是
X X X O X O
最短路径数组状态
0 285 10 50 30 100
前驱结点状态
-1 -1 0 4 0 0
顶点5无需重复入队
标记数组的状态是
X X X O X O
最短路径数组状态
0 285 10 50 30 90
前驱结点状态
-1 -1 0 4 0 4
顶点4处理完毕
最短路径数组状态
0 285 10 50 30 90
前驱结点状态
-1 -1 0 4 0 4
最短路径数组状态
0 285 10 50 30 90
前驱结点状态
-1 -1 0 4 0 4
顶点5出队
并把顶点5标记为X
标记数组的状态是
X X X O X X
顶点5处理完毕
最短路径数组状态
0 285 10 50 30 90
前驱结点状态
-1 -1 0 4 0 4
最短路径数组状态
0 285 10 50 30 90
前驱结点状态
-1 -1 0 4 0 4
顶点3出队
并把顶点3标记为X
标记数组的状态是
X X X X X X
顶点5入队并被标记为O
标记数组的状态是
X X X X X O
最短路径数组状态
0 285 10 50 30 60
前驱结点状态
-1 -1 0 4 0 3
顶点3处理完毕
最短路径数组状态
0 285 10 50 30 60
前驱结点状态
-1 -1 0 4 0 3
最短路径数组状态
0 285 10 50 30 60
前驱结点状态
-1 -1 0 4 0 3
顶点5出队
并把顶点5标记为X
标记数组的状态是
X X X X X X
顶点5处理完毕
最短路径数组状态
0 285 10 50 30 60
前驱结点状态
-1 -1 0 4 0 3
此时队列为空
结果集为:
(0,1):不可达
(0,2):0-->2
(0,3):0-->4-->3
(0,4):0-->4
(0,5):0-->4-->3-->5
