所謂的最短路徑米死，顧名思義就是帶權(quán)值的圖中跨扮，求一個結(jié)點到另一個結(jié)點的路徑最小寒波。
Dijkstra算法
1.介紹
迪杰斯特拉（Dijkstra）算法是典型的最短路徑算法吹害，用于計算一個結(jié)點到其他結(jié)點的最短路徑。它的主要特點是以起始點為中心向外層層擴展（廣度優(yōu)先搜索思想）亿虽，直到擴展到終點為止菱涤。
基本思想
通過Dijkstra計算圖G中的最短路徑，需要指定起點s（即從頂點s開始計算）洛勉。
此外粘秆，引出兩個集合S和U。S的作用是記錄已求出最短路徑的頂點（以及相應(yīng)的最短路徑長度）坯认，而U則是記錄還未求出最短路徑的頂點（以及該頂點到起始點的距離）翻擒。
初始時，S中只有起點s牛哺；U中是除s之外的頂點陋气，并且U中頂點的路徑是“起點s到該頂點的路徑”。然后引润，從U中找出最短路徑最短的頂點巩趁，并將其加入到S中；接著淳附，更新U中的頂點和頂點對應(yīng)的路徑议慰。然后，再從U中找出路徑最短的頂點奴曙，并將其加入到S中别凹；接著，更新U中的頂點和頂點對應(yīng)的路徑洽糟。...重復(fù)該操作炉菲，直到遍歷完所有頂點堕战。
操作步驟
(1) 初始時，S只包含起點s拍霜；U包含除s外的其他頂點嘱丢，且U中頂點的距離為"起點s到該頂點的距離"[例如，U中頂點v的距離為(s,v)的長度祠饺，然后s和v不相鄰越驻，則v的距離為∞]。
(2) 從U中選出"距離最短的頂點k"道偷，并將頂點k加入到S中缀旁；同時，從U中移除頂點k勺鸦。
(3) 更新U中各個頂點到起點s的距離诵棵。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點祝旷，從而可以利用k來更新其它頂點的距離；例如嘶窄，(s,v)的距離可能大于(s,k)+(k,v)的距離怀跛。
(4) 重復(fù)步驟(2)和(3)，直到遍歷完所有頂點柄冲。
2.圖解
以上圖G4為例吻谋，來對迪杰斯特拉進行算法演示(以第4個頂點D為起點)。
初始狀態(tài)：S是已計算出最短路徑的頂點集合现横，U是未計算除最短路徑的頂點的集合漓拾！
第1步：將頂點D加入到S中。
此時戒祠，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}骇两。 注:C(3)表示C到起點D的距離是3。
第2步：將頂點C加入到S中姜盈。
上一步操作之后低千，U中頂點C到起點D的距離最短；因此馏颂，將C加入到S中示血，同時更新U中頂點的距離。以頂點F為例救拉，之前F到D的距離為∞难审；但是將C加入到S之后，F(xiàn)到D的距離為9=(F,C)+(C,D)亿絮。
此時告喊，S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}麸拄。
第3步：將頂點E加入到S中。
上一步操作之后葱绒，U中頂點E到起點D的距離最短感帅；因此，將E加入到S中地淀，同時更新U中頂點的距離失球。還是以頂點F為例，之前F到D的距離為9帮毁；但是將E加入到S之后实苞，F(xiàn)到D的距離為6=(F,E)+(E,D)。
此時烈疚，S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}黔牵。
第4步：將頂點F加入到S中。
此時爷肝，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}猾浦。
第5步：將頂點G加入到S中。
此時灯抛，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}金赦。
第6步：將頂點B加入到S中。
此時对嚼，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}夹抗。
第7步：將頂點A加入到S中。
此時纵竖，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}漠烧。
此時，起點D到各個頂點的最短距離就計算出來了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)靡砌。
3.代碼說明
package com.xushu;
public class ListUDG {
private static int INF = Integer.MAX_VALUE;
// 鄰接表中表對應(yīng)的鏈表的頂點
private class ENode {
int ivex; // 該邊所指向的頂點的位置
int weight; // 該邊的權(quán)
ENode nextEdge; // 指向下一條弧的指針
}
// 鄰接表中表的頂點
private class VNode {
char data; // 頂點信息
ENode firstEdge; // 指向第一條依附該頂點的弧
};
private int mEdgNum; // 邊的數(shù)量
private VNode[] mVexs; // 頂點數(shù)組
/*
* 創(chuàng)建圖(用已提供的矩陣)
*
* 參數(shù)說明：
* vexs -- 頂點數(shù)組
* edges -- 邊
*/
public ListUDG(char[] vexs, EData[] edges) {
// 初始化"頂點數(shù)"和"邊數(shù)"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"頂點"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"邊"
mEdgNum = elen;
for (int i = 0; i < elen; i++) {
// 讀取邊的起始頂點和結(jié)束頂點
char c1 = edges[i].start;
char c2 = edges[i].end;
int weight = edges[i].weight;
// 讀取邊的起始頂點和結(jié)束頂點
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
node1.weight = weight;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
node2.weight = weight;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 將node節(jié)點鏈接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 打印矩陣隊列圖
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
/*
* 獲取邊<start, end>的權(quán)值已脓；若start和end不是連通的，則返回?zé)o窮大乏奥。
*/
private int getWeight(int start, int end) {
if (start==end)
return 0;
ENode node = mVexs[start].firstEdge;
while (node!=null) {
if (end==node.ivex)
return node.weight;
node = node.nextEdge;
}
return INF;
}
/*
* Dijkstra最短路徑摆舟。
* 即，統(tǒng)計圖中"頂點vs"到其它各個頂點的最短路徑邓了。
*
* 參數(shù)說明：
* vs -- 起始頂點(start vertex)恨诱。即計算"頂點vs"到其它頂點的最短路徑。
* prev -- 前驅(qū)頂點數(shù)組骗炉。即照宝，prev[i]的值是"頂點vs"到"頂點i"的最短路徑所經(jīng)歷的全部頂點中，位于"頂點i"之前的那個頂點句葵。
* dist -- 長度數(shù)組厕鹃。即兢仰，dist[i]是"頂點vs"到"頂點i"的最短路徑的長度。
*/
public void dijkstra(int vs, int[] prev, int[] dist) {
// flag[i]=true表示"頂點vs"到"頂點i"的最短路徑已成功獲取剂碴。
boolean[] flag = new boolean[mVexs.length];
// 初始化
for (int i = 0; i < mVexs.length; i++) {
flag[i] = false; // 頂點i的最短路徑還沒獲取到把将。
prev[i] = 0; // 頂點i的前驅(qū)頂點為0。
dist[i] = getWeight(vs, i); // 頂點i的最短路徑為"頂點vs"到"頂點i"的權(quán)忆矛。
}
// 對"頂點vs"自身進行初始化
flag[vs] = true;
dist[vs] = 0;
// 遍歷mVexs.length-1次察蹲；每次找出一個頂點的最短路徑。
int k = 0;
for (int i = 1; i < mVexs.length; i++) {
// 尋找當(dāng)前最小的路徑催训；
// 即洽议，在未獲取最短路徑的頂點中，找到離vs最近的頂點(k)漫拭。
int min = INF;
for (int j = 0; j < mVexs.length; j++) {
if (flag[j]==false && dist[j]<min) {
min = dist[j];
k = j;
}
}
// 標(biāo)記"頂點k"為已經(jīng)獲取到最短路徑
flag[k] = true;
// 修正當(dāng)前最短路徑和前驅(qū)頂點
// 即亚兄，當(dāng)已經(jīng)"頂點k的最短路徑"之后，更新"未獲取最短路徑的頂點的最短路徑和前驅(qū)頂點"采驻。
for (int j = 0; j < mVexs.length; j++) {
int tmp = getWeight(k, j);
tmp = (tmp==INF ? INF : (min + tmp)); // 防止溢出
if (flag[j]==false && (tmp<dist[j]) )
{
dist[j] = tmp;
prev[j] = k;
}
}
}
// 打印dijkstra最短路徑的結(jié)果
System.out.printf("dijkstra(%c): \n", mVexs[vs].data);
for (int i = 0; i < mVexs.length; i++)
System.out.printf(" shortest(%c, %c)=%d\n", mVexs[vs].data, mVexs[i].data, dist[i]);
}
// 邊的結(jié)構(gòu)體
private static class EData {
char start; // 邊的起點
char end; // 邊的終點
int weight; // 邊的權(quán)重
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
};
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
EData[] edges = {
// 起點 終點 權(quán)
new EData('A', 'B', 12),
new EData('A', 'F', 16),
new EData('A', 'G', 14),
new EData('B', 'C', 10),
new EData('B', 'F', 7),
new EData('C', 'D', 3),
new EData('C', 'E', 5),
new EData('C', 'F', 6),
new EData('D', 'E', 4),
new EData('E', 'F', 2),
new EData('E', 'G', 8),
new EData('F', 'G', 9),
};
ListUDG pG;
// 采用已有的"圖"
pG = new ListUDG(vexs, edges);
int[] prev = new int[pG.mVexs.length];
int[] dist = new int[pG.mVexs.length];
// dijkstra算法獲取"第4個頂點"到其它各個頂點的最短距離
pG.dijkstra(3, prev, dist);
}
}
Floyd算法
1.介紹
和Dijkstra算法一樣审胚，佛洛依德（Floyd）算法也是一種用于尋找給定的加權(quán)圖頂點間最短路徑的算法。
基本思想
通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時礼旅，需要引入一個矩陣S菲盾，矩陣S中的元素a[i][j]表示頂點i（第i個頂點）到頂點j（第j個頂點）的距離。
假設(shè)圖G中頂點個數(shù)為N各淀，則需要對矩陣S進行N次更新。初始時诡挂，矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值碎浇；如果i和j不相鄰，則a[i][j]=∞璃俗。接下來開始奴璃，對矩陣S進行N次更新。第一次更新時城豁，如果"a[i][j]的距離" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i與j之間經(jīng)過第1個頂點的距離")苟穆，則更新a[i][j]為"a[i][0]+a[0][j]"。 同理唱星，第k次更新時雳旅，如果"a[i][j]的距離" > "a[i][k]+a[k][j]"，則更新a[i][j]為"a[i][k]+a[k][j]"间聊。更新N次之后攒盈，操作完成！
2.圖解
以上圖為例哎榴，進行演示：
初始狀態(tài)：S是記錄各個頂點間最短路徑的矩陣型豁。
第1步：初始化S僵蛛。
矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值；如果i和j不相鄰迎变，則a[i][j]=∞充尉。實際上，就是將圖的原始矩陣復(fù)制到S中衣形。
注:a[i][j]表示矩陣S中頂點i(第i個頂點)到頂點j(第j個頂點)的距離驼侠。
第2步：以頂點A(第1個頂點)為中介點，若a[i][j] > a[i][0]+a[0][j]泵喘，則設(shè)置a[i][j]=a[i][0]+a[0][j]泪电。
以頂點a[1][6]為例，初始的時候纪铺，a[1][6]=∞相速；而將A作為中介點時，(B,A)=12鲜锚，(A,G)=14突诬，因此B和G之間的距離可以更新為26。
同理芜繁，依次將頂點B,C,D,E,F,G作為中介點旺隙，并更新a[i][j]的大小。
3.代碼說明
public class ListUDG {
private static int INF = Integer.MAX_VALUE;
// 鄰接表中表對應(yīng)的鏈表的頂點
private class ENode {
int ivex; // 該邊所指向的頂點的位置
int weight; // 該邊的權(quán)
ENode nextEdge; // 指向下一條弧的指針
}
// 鄰接表中表的頂點
private class VNode {
char data; // 頂點信息
ENode firstEdge; // 指向第一條依附該頂點的弧
};
private int mEdgNum; // 邊的數(shù)量
private VNode[] mVexs; // 頂點數(shù)組
/*
* 創(chuàng)建圖(用已提供的矩陣)
*
* 參數(shù)說明：
* vexs -- 頂點數(shù)組
* edges -- 邊
*/
public ListUDG(char[] vexs, EData[] edges) {
// 初始化"頂點數(shù)"和"邊數(shù)"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"頂點"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"邊"
mEdgNum = elen;
for (int i = 0; i < elen; i++) {
// 讀取邊的起始頂點和結(jié)束頂點
char c1 = edges[i].start;
char c2 = edges[i].end;
int weight = edges[i].weight;
// 讀取邊的起始頂點和結(jié)束頂點
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
node1.weight = weight;
// 將node1鏈接到"p1所在鏈表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
node2.weight = weight;
// 將node2鏈接到"p2所在鏈表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 將node節(jié)點鏈接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 打印矩陣隊列圖
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
/*
* 獲取邊<start, end>的權(quán)值骏令；若start和end不是連通的蔬捷，則返回?zé)o窮大。
*/
private int getWeight(int start, int end) {
if (start==end)
return 0;
ENode node = mVexs[start].firstEdge;
while (node!=null) {
if (end==node.ivex)
return node.weight;
node = node.nextEdge;
}
return INF;
}
/*
* floyd最短路徑榔袋。
* 即周拐，統(tǒng)計圖中各個頂點間的最短路徑。
*
* 參數(shù)說明：
* path -- 路徑凰兑。path[i][j]=k表示妥粟，"頂點i"到"頂點j"的最短路徑會經(jīng)過頂點k。
* dist -- 長度數(shù)組吏够。即勾给，dist[i][j]=sum表示，"頂點i"到"頂點j"的最短路徑的長度是sum锅知。
*/
public void floyd(int[][] path, int[][] dist) {
// 初始化
for (int i = 0; i < mVexs.length; i++) {
for (int j = 0; j < mVexs.length; j++) {
dist[i][j] = getWeight(i, j); // "頂點i"到"頂點j"的路徑長度為"i到j(luò)的權(quán)值"播急。
path[i][j] = j; // "頂點i"到"頂點j"的最短路徑是經(jīng)過頂點j。
}
}
// 計算最短路徑
for (int k = 0; k < mVexs.length; k++) {
for (int i = 0; i < mVexs.length; i++) {
for (int j = 0; j < mVexs.length; j++) {
// 如果經(jīng)過下標(biāo)為k頂點路徑比原兩點間路徑更短售睹，則更新dist[i][j]和path[i][j]
int tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
if (dist[i][j] > tmp) {
// "i到j(luò)最短路徑"對應(yīng)的值設(shè)旅择，為更小的一個(即經(jīng)過k)
dist[i][j] = tmp;
// "i到j(luò)最短路徑"對應(yīng)的路徑，經(jīng)過k
path[i][j] = path[i][k];
}
}
}
}
// 打印floyd最短路徑的結(jié)果
System.out.printf("floyd: \n");
for (int i = 0; i < mVexs.length; i++) {
for (int j = 0; j < mVexs.length; j++)
System.out.printf("%2d ", dist[i][j]);
System.out.printf("\n");
}
}
// 邊的結(jié)構(gòu)體
private static class EData {
char start; // 邊的起點
char end; // 邊的終點
int weight; // 邊的權(quán)重
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
};
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
EData[] edges = {
// 起點 終點 權(quán)
new EData('A', 'B', 12),
new EData('A', 'F', 16),
new EData('A', 'G', 14),
new EData('B', 'C', 10),
new EData('B', 'F', 7),
new EData('C', 'D', 3),
new EData('C', 'E', 5),
new EData('C', 'F', 6),
new EData('D', 'E', 4),
new EData('E', 'F', 2),
new EData('E', 'G', 8),
new EData('F', 'G', 9),
};
ListUDG pG;
// 自定義"圖"(輸入矩陣隊列)
//pG = new ListUDG();
// 采用已有的"圖"
pG = new ListUDG(vexs, edges);
int[] prev = new int[pG.mVexs.length];
int[] dist = new int[pG.mVexs.length];
;
int[][] path = new int[pG.mVexs.length][pG.mVexs.length];
int[][] floy = new int[pG.mVexs.length][pG.mVexs.length];
// floyd算法獲取各個頂點之間的最短距離
pG.floyd(path, floy);
}
}
