一唧领、最短路徑的概念：從有向圖中某一頂點（起始頂點）到達(dá)另一頂點（終止頂點）的路徑中，其權(quán)值之和最小的路徑
二呐萌、算法一：Dijkstra算法
單源最短路徑問題：給定一個帶權(quán)有向圖 D 與源點 v ，求從v 到 D 中其它頂點的最短路徑。限定各邊上的權(quán)值大于0悦析。
如何求得這些路徑？迪杰斯特拉(Dijkstra)提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法此衅。首先求出長度最短的一條最短路徑强戴，再參照它求出長度次短的一條最短路徑，依次類推挡鞍，直到從頂點 v 到其它各頂點的最短路徑全部求出為止骑歹。
解決步驟描述：
- 設(shè)置輔助數(shù)組dist。它的每一個分量dist[i]表示當(dāng)前找到的從源點 v0到終點 vi的最短路徑的長度墨微；
- 初始狀態(tài)：
2.1. 若從源點 v0 到頂點 vi有邊：dist[i]為該邊上的權(quán)值道媚；
2.2. 若從源點 v0 到頂點 vi無邊：dist[i]為∞。
根據(jù)以上描述翘县，可以得到如下描述的算法：
假設(shè)用帶權(quán)的鄰接矩陣Edge[i][j]表示邊(vi,vj)上的權(quán)值最域。若(vi,vj)不存在，則置Edge[i][j]為∞锈麸。S為已.找到從v出發(fā)的最短路徑的終點的集合镀脂，它的初始狀態(tài)為空集。
1.初始化： S ← {v0 };dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
2.找出最短路徑所對應(yīng)的點 K：dist[k] == min { dist[i] }, i ∈ V- S ;S ← S U { k };
3.對于每一個 i ∈ V- S 修改：dist[i] ← min{ dist[i],dist[k] + Edge[k][i] }忘伞；
4.判斷：若 S = V, 則算法結(jié)束薄翅，否則轉(zhuǎn)2。
算法的精髓：S 集內(nèi)的頂點是已經(jīng)找到最短路徑的頂點氓奈，V0 到 w 的最短路徑只能通過 S 集內(nèi)的頂點,迪杰斯特拉算法的時間復(fù)雜度為O(n*n)翘魄。
算法實現(xiàn)
G: 網(wǎng)圖;
v0: V0開始的頂點;
p[v]: 前驅(qū)頂點下標(biāo);
D[v]: 表示從V0到V的最短路徑長度和;
*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
k = 0;
int final[MAXVEX];
for(v=0; v<G.numVertexes; v++)
{
final[v] = 0;
(*D)[v] = G.arc[v0][v];
(*P)[v] = 0;
}
(*D)[v0] = 0;
final[v0] = 1;
(*P)[v0] = -1;
for(v=1; v<G.numVertexes; v++)
{
min=INFINITYC;
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (*D)[w]<min)
{
k=w;
min = (*D)[w];
}
}
final[k] = 1;
for(w=0; w<G.numVertexes; w++)
{
if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
{
(*D)[w] = min + G.arc[k][w];
(*P)[w]=k;
}
}
}
}
三、算法二：Floyd算法
所有頂點之間的最短路徑：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖舀奶，對每一對頂點 vi≠vj暑竟，要求求出vi與vj之間的最短路徑和最短路徑長度。
解決這個問題的一個方法是：每次以一個頂點為源點育勺，重復(fù)執(zhí)行迪杰斯特拉算法n次光羞。這樣绩鸣，便可求得每一對頂點之間的最短路徑∩炊遥總的執(zhí)行時間為O(n3)呀闻。雖然能實現(xiàn)，但是明顯實現(xiàn)起來比較復(fù)雜潜慎。
下面介紹一下由弗洛伊德提出的另一個算法捡多。這個算法的時間復(fù)雜度也是O(n3),但形勢上簡單些。
弗洛伊德算法仍從圖的帶權(quán)鄰接矩陣Edge[i][j]出發(fā)铐炫，其基本思想是：假設(shè)求頂點vi到vj的最短路徑垒手。如果從vi到vj有弧（無向圖稱為邊）倒信，則從vi到vj存在一條長度為Edge[i][j]的路徑科贬，該路徑不一定是最短路徑，尚需n次試探鳖悠。首先考慮路徑（vi 榜掌，v0 ，vj）是否存在（即判別弧(vi 乘综，v0 )和弧(v0 憎账，vj)是否存在）。如果存在,則比較(vi 卡辰，vj)和(vi 胞皱，v0 ，vj)的路徑長度取長度較短者為從vi到vj的中間定點序號不大于0的最短路徑九妈。假如在路徑上再增加一個頂點v1反砌，也就是說，如果（vi 萌朱，…于颖，v1）和（v1，…嚷兔，vj）分別是當(dāng)前找到的中間頂點的序號不大于0的最短路徑,那么（vi ，…做入，v1冒晰，…，vj）就有可能是從vi到vj的中間頂點的序號不大于1的最短路徑竟块。將它和已經(jīng)得到的從vi到vj中間頂點序號不大于0的最短路徑相比較壶运，從中選出中間頂點的序號不大于1的最短路徑之后，再增加一個頂點v2浪秘，繼續(xù)進(jìn)行試探蒋情。依次類推埠况，若vi ，…棵癣，vk）和（vk辕翰，…，vj）分別是從vi到vk和從vk到vj中間頂點的序號不大于k-1的最短路徑,則將（vi 狈谊，…喜命，vk，…河劝，vj）和已經(jīng)找到的從vi到vj且中間頂點序號不大于k-1的最短路徑相比較壁榕，其長度較短者是從vi到vj的中間頂點序號不大于k的最短路徑。這樣赎瞎，經(jīng)過n次比較后牌里，最后求得的必是從vi到vj的最短路徑。按此方法务甥，可以同時求得各對頂點間的最短路徑牡辽。
定義一個 n 階方陣序列：A(-1), A(0), …, A(n-1)
其中:A(-1)[i][j] = Edge[i][j]
A(k) [i][j] = min { A(k-1)[i][j],A(k-1)[i][k] + A(k-1)[k][j]}
k = 0, 1, …, n-1
A(0)[i][j]是從頂點vi到vj, 中間頂點是v0的最短路徑的長度；
A(k) [i][j]是從頂點vi 到vj, 中間頂點的序號不大于k的最短路徑的長度缓呛；
A(n-1)[i]j]是從頂點 vi 到 vj的最短路徑長度催享。
算法實現(xiàn)
Floyd算法，求網(wǎng)圖G中各頂點v到其余頂點w的最短路徑P[v][w]及帶權(quán)長度D[v][w]哟绊。
Patharc 和 ShortPathTable 都是二維數(shù)組;
*/
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
(*D)[v][w]=G.arc[v][w];
(*P)[v][w]=w;
}
}
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
