最短路徑一般是基於網圖來說的帶有權值的連通圖），不帶權值可以考慮權值為1來計算。
最短路徑是指兩頂點之間經過的邊上權值之和最少的路徑，並且我們稱路徑上的第一個頂點是源點，最後一個頂點是終點。
求解最短路徑的兩種算法。迪傑斯特拉算法和弗洛伊德算法。
1、迪傑斯特拉Dijkstra）算法
用來求某個頂點到其余所有頂點的最短路徑
算法介紹
求V0到其余各個頂點的最短路徑。
1）初始化，P={V0}，D0V0到V0的距離）= 0；Di表示V0到Vi頂點的距離，Di = di0,i不等於0，規定如果Vi頂點與V0不直接相連，則Di = 無窮大。
2）尋找下一個目標頂點，即在Di(i不屬於P)中選擇一個點j，是Dj最小，則選擇的點Vj放到P中，Vj所在的路徑是最短路徑。
3）更新Di(i不屬於P），Di = min[Di舊的，更新之前的），Dj + dji ]，更新完所有i(不屬於P)，返回第2步。直達所有頂點存儲到P中。
#define MAXVEX 9
#define INFINITY 65535
typedef int Pathmatirx[MAXVEX];
typedef int ShortPathTable[MAXVEX];
void ShortestPaht_DijkstraMGraph G, int V0, Pathmatirx *P, ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX]; /*final[w]=1表示求得頂點V0至Vw的最短路徑*/
for(v=0;v<G.numVertexes; v++)
{
final[v] = 0;
(*D)[v] = G.matirx[V0][v];
(*P)[v] = 0;
}
(*D)[V0] = 0; /*v0至v0路徑為0*/
final[V0] = 1;/*v0至v0不需要求路徑*/
/*開始主循環，每次求得V0到某個頂點V的最短路徑*/
for(v = 1; v<G.numVertexes; v++)
{
min = INFINITY; /*初始化最短距離*/
for(w=0; w<G.numVertexes; w++) /*尋找離V0最近的頂點*/
{
if(!final[w] && (*D)[w]<min)
{
k = w;
min = (*D)[w]; /*w頂點離v0頂點更近*/
}
}
final[k] = 1; /*將目前找到的最近的頂點置為1*/
for((w = 0; w<G.numVertexes; w++) /*修正當前最短路徑及距離*/
{
/*如果經過V頂點的路徑比現在這條路徑短的話*/
if(!final[w] && (min + G.matirx[k][w] <(*D)[w])
{
/*說明找到了更短的路徑，修改D[w]和P[w]*/
(*D)[w] = min + G.matirx[k][w]; /*修改當前路徑長度*/
(*P)[w] = k;
}
}
}
}
2、弗洛伊德Floyd）算法
用來求解任意頂點到任意頂點的最短路徑。
是一種用於尋找給定的加權圖中頂點間最短路徑的算法
核心思路：
通過一個圖的權值矩陣求出它的每兩點之間的最短路徑。
1）從任意一條單邊路徑開始，所有兩點之間的距離是邊的權，如果兩點之間沒有變相連，則權為無窮大。
2）對於每一點U和V，看看是否存在一個頂點W使得從U到W再到V比已知的路徑更短，如果是更新它。
把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。
定義一個矩陣D用來記錄所插入的點的信息，D[i,j]表示從從Vi到Vj需要經過的點，初始化D[i,j]=j。
把各個頂點插入圖中，比較插點後的距離和原來的距離G[i,j] = min ( G[i,j] ，G[i,k] + G[k,j]）；
如果G[i,j]的值變小，則D[i,j]=k。
在G中包含兩點之間最短路徑的長度的信息，而在D中則包含了最短路徑具體路徑）的信息。
#include <stdio.h>
#define MAXVEX 100
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShorPathTable[MAXVEX][MAXVEX];
/*Floyd算法，求網圖G中各頂點v到其余頂點w的最短路徑P[v][w]及帶權長度D[v][w]*/
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v<G.numVertexes; ++v) /*初始化D與P*/
{
for(w=0; w<G.numVertexes; ++w) /*D[v][w]的值即為對應點間的權值*/
{
(*D)[v][w] = G.matirx[v][w];
(*P)[v][w] = w; /*初始化P*/
}
}
for(k= 0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w) /*如果經過下標為k頂點的路徑比原兩點之間路徑更短*/
{
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];
}
}
}
}
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1293459
