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 {
/**
* 適用于單源最短路徑問題烧颖，尤其適用于權(quán)值為負(fù)的情況却盘。
* 它適用于有向圖嘉栓。
* 但是如果有向圖中存在回路，并且回路的權(quán)值之和為負(fù)治力，
* 那么本圖是無法用此算法求最短路徑的，因為越求越小勃黍，
* 根本沒有最小路徑宵统。
* 本算法的實質(zhì)是一個廣度優(yōu)先搜索算法。
* 又叫動態(tài)逼近法覆获。
* 為什么spfa所有隊列中如果有一個結(jié)點马澈，那么相同的結(jié)
* 點就不入隊呢？
* 因為入隊是因為以該頂點為中間點能夠找到更短路徑弄息，
* 入隊是要傳達(dá)一個信息痊班，該頂點具備可以使路徑變得更
* 短的能力，它是一個標(biāo)識而已摹量，而有一個在隊列中就能
* 夠標(biāo)識該頂點能夠使路徑變得更短了涤伐，就不需要第二個
* 了馒胆。
* 其他的也可能是為了不重復(fù)入隊，減少一些不必要的操作吧凝果，或
* 者限制隊列的長度吧祝迂，這樣確實可以確定地設(shè)置隊列的
* 長度。
* 出去的點作為中間點豆村，如果該頂點的出度加上它已有的
* 最小路徑比從源點到其箭頭頂點的距離更短液兽，則更新從
* 源點到箭頭頂點最短路徑的值。
* @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;
}
//用來存儲前驅(qū)的中間結(jié)點數(shù)組四啰，也是結(jié)果集數(shù)組。
int[] preMiddleArray = new int[arrayLength];
//也把它初始化為-1
for (int counter = 0;counter < arrayLength;counter++)
preMiddleArray[counter] = -1;
//為了不讓已經(jīng)在隊列中的頂點標(biāo)號重復(fù)入隊粗恢，所以
// 應(yīng)該弄一個數(shù)組來標(biāo)記有哪個頂點入隊了柑晒。
boolean[] vertexFlag = new boolean[arrayLength];
for (int counter = 0;counter < arrayLength;counter++)
vertexFlag[counter] = false;
//由于隊列中并不存在重復(fù)元素，
// 所以隊列最長為arrayLength眷射。
// 并且采用循環(huán)隊列匙赞。
int[] minPathQueue = new int[arrayLength];
int front = 0;
int rear = front;
minPathQueue[rear] = vertexId;
vertexFlag[vertexId] = true;
System.out.println("標(biāo)記數(shù)組的狀態(tài)是");
for (boolean element:vertexFlag)
System.out.print((element?"O":"X") + " ");
System.out.println();
while ((rear + 1) % arrayLength != front) {
System.out.println("最短路徑數(shù)組狀態(tài)");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驅(qū)結(jié)點狀態(tài)");
for (int element:preMiddleArray)
System.out.print(element + " ");
int currentMiddleIndex = minPathQueue[front++];
vertexFlag[currentMiddleIndex] = false;
System.out.println("\n頂點" + currentMiddleIndex + "出隊");
System.out.println("并把頂點" + currentMiddleIndex + "標(biāo)記為X");
System.out.println("標(biāo)記數(shù)組的狀態(tài)是");
for (boolean element:vertexFlag)
System.out.print((element?"O":"X") + " ");
System.out.println();
front = front % arrayLength;
for (int counter = 0;counter < arrayLength;counter++) {
//這個比較的術(shù)語叫做松弛，所以這一操作被稱為松弛操作妖碉。
// 很形象涌庭，最初兩個頂點之間有根橡皮筋，后來每次找到一
// 個能夠使路徑更短的中間點欧宜，就讓橡皮筋更松弛一些坐榆，于
// 是松弛操作的直接意思就是找到了個中間點讓原來兩頂點
// 之間的路徑更短了。
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 + "入隊并被標(biāo)記為O");
} else System.out.println("頂點" + counter + "無需重復(fù)入隊");
System.out.println("標(biāo)記數(shù)組的狀態(tài)是");
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("最短路徑數(shù)組狀態(tài)");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驅(qū)結(jié)點狀態(tài)");
for (int element:preMiddleArray)
System.out.print(element + " ");
System.out.println();
}
}
System.out.println("頂點" + currentMiddleIndex + "處理完畢");
System.out.println("最短路徑數(shù)組狀態(tài)");
for (int element:minPathArray)
System.out.print(element + " ");
System.out.println("\n前驅(qū)結(jié)點狀態(tài)");
for (int element:preMiddleArray)
System.out.print(element + " ");
System.out.println("\n");
}
System.out.println("此時隊列為空");
//下面打印從源頂點到各頂點的最短路徑
System.out.println("結(jié)果集為:");
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("不可達(dá)");
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();
}
}
}
輸出
標(biāo)記數(shù)組的狀態(tài)是
O X X X X X
最短路徑數(shù)組狀態(tài)
0 285 285 285 285 285
前驅(qū)結(jié)點狀態(tài)
-1 -1 -1 -1 -1 -1
頂點0出隊
并把頂點0標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X X X X
頂點2入隊并被標(biāo)記為O
標(biāo)記數(shù)組的狀態(tài)是
X X O X X X
最短路徑數(shù)組狀態(tài)
0 285 10 285 285 285
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 -1 -1 -1
頂點4入隊并被標(biāo)記為O
標(biāo)記數(shù)組的狀態(tài)是
X X O X O X
最短路徑數(shù)組狀態(tài)
0 285 10 285 30 285
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 -1 0 -1
頂點5入隊并被標(biāo)記為O
標(biāo)記數(shù)組的狀態(tài)是
X X O X O O
最短路徑數(shù)組狀態(tài)
0 285 10 285 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 -1 0 0
頂點0處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 285 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 -1 0 0
最短路徑數(shù)組狀態(tài)
0 285 10 285 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 -1 0 0
頂點2出隊
并把頂點2標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X X O O
頂點3入隊并被標(biāo)記為O
標(biāo)記數(shù)組的狀態(tài)是
X X X O O O
最短路徑數(shù)組狀態(tài)
0 285 10 60 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 2 0 0
頂點2處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 60 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 2 0 0
最短路徑數(shù)組狀態(tài)
0 285 10 60 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 2 0 0
頂點4出隊
并把頂點4標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X O X O
頂點3無需重復(fù)入隊
標(biāo)記數(shù)組的狀態(tài)是
X X X O X O
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 100
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 0
頂點5無需重復(fù)入隊
標(biāo)記數(shù)組的狀態(tài)是
X X X O X O
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 90
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 4
頂點4處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 90
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 4
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 90
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 4
頂點5出隊
并把頂點5標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X O X X
頂點5處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 90
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 4
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 90
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 4
頂點3出隊
并把頂點3標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X X X X
頂點5入隊并被標(biāo)記為O
標(biāo)記數(shù)組的狀態(tài)是
X X X X X O
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 60
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 3
頂點3處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 60
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 3
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 60
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 3
頂點5出隊
并把頂點5標(biāo)記為X
標(biāo)記數(shù)組的狀態(tài)是
X X X X X X
頂點5處理完畢
最短路徑數(shù)組狀態(tài)
0 285 10 50 30 60
前驅(qū)結(jié)點狀態(tài)
-1 -1 0 4 0 3
此時隊列為空
結(jié)果集為:
(0,1):不可達(dá)
(0,2):0-->2
(0,3):0-->4-->3
(0,4):0-->4
(0,5):0-->4-->3-->5
