最短路徑，其實就是求我們日常生活中，從某點到達某點的最短路徑，Dijkstra用了一種變通的方式，它是求出從源點到達所有點的最短路徑長度。
分析:
這個算法采用的是貪心思想，而貪心算法能否達到最後，有兩個必要不充分條件
1.必須要有最優子結構 2.必須具備貪心選擇屬性
1.最優子結構:
我們設d(i,j)表示從，結點Vi到Vj的最短路徑值，則d（i，j） = d（i，k） + d（k，j）(假設k是最短路上經過的點)。這就是最短路的問題的最優子·結構，因為原問題的最優解，取決於兩個不想交子集的最優解。
2.貪心選擇屬性
我們假設Set（i，j）表示從{d[i],....d[j]}的集合，而d[k]又表示為從源點到結點k的最短距離，則當要要拓展即d[j + 1]時，因該把此時離源點距離最近的選入，這樣Set的補集，就有減少了一個結點，我們接下去要解決的就只是有少了一個結點的子問題，如果把這個補集的元素到源點的距離按照從小到大排序，那麼此時要選的就是最小的。這個就是貪心選擇屬性，它每一次都選則最小的，接著繼續解決下一個子問題（解著下次選擇）。又因為，其實選的時候，我們只需要考慮於已經算出的點的最短距離有鄰接的點，所以我們需要更新所有鄰接點，而其它的點此時的d值為多少，並無關系。所以我們初始話時可以把d都設置為INF,然後記錄下相鄰節點間的權值就夠，也就是說這個貪心選擇，能保證每次選入的點，到達源點的距離是最短的。
代碼如下:
[cpp]
#include <stdio.h>
#include <string.h>
#define INF 1 << 30
#define MAXN 1000
int d[MAXN + 1];
int fa[MAXN + 1];
int vis[MAXN + 1];
int G[MAXN + 1][MAXN + 1];//這裡可以換為Vector數據結構，降低空間復雜度
int n,m;
int main(){
while(scanf("%d%d",&n,&m) != EOF){
for(int i = 1; i <= MAXN ; i++){//初始化圖，為無邊圖
for(int j = 1; j <= MAXN; j++){
G[i][j] = INF;
}
}
for(int i = 1; i <=m; i++){//建立圖
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u][v] = w;
}
d[1] = 0;//源點到自身，距離為0，設源點為V1.
fa[1] = 1;
for(int i = 2; i <= n; i++){
d[i] = INF;
fa[i] = 0;
}
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; i++){
int min = INF,x;
for(int y = 1; y <= n; y++){
if(!vis[y] && d[y] <= min){
min = d[x = y];
}
}
vis[x] = 1;//加入集合Set
for(int y = 1; y <=n; y++){//跟新x的鄰接點，只有邊不為INF才不會改變，邊權值為INF視為不是鄰接點，所以並不會改變
if(d[y] > d[x] + G[x][y]){
d[y] = d[x] + G[x][y];
fa[y] = x;
}
}
}
for(int i = 1; i <= n; i++)
printf("%d\n",d[i]);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#define INF 1 << 30
#define MAXN 1000
int d[MAXN + 1];
int fa[MAXN + 1];
int vis[MAXN + 1];
int G[MAXN + 1][MAXN + 1];//這裡可以換為Vector數據結構，降低空間復雜度
int n,m;
int main(){
while(scanf("%d%d",&n,&m) != EOF){
for(int i = 1; i <= MAXN ; i++){//初始化圖，為無邊圖
for(int j = 1; j <= MAXN; j++){
G[i][j] = INF;
}
}
for(int i = 1; i <=m; i++){//建立圖
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u][v] = w;
}
d[1] = 0;//源點到自身，距離為0，設源點為V1.
fa[1] = 1;
for(int i = 2; i <= n; i++){
d[i] = INF;
fa[i] = 0;
}
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; i++){
int min = INF,x;
for(int y = 1; y <= n; y++){
if(!vis[y] && d[y] <= min){
min = d[x = y];
}
}
vis[x] = 1;//加入集合Set
for(int y = 1; y <=n; y++){//跟新x的鄰接點，只有邊不為INF才不會改變，邊權值為INF視為不是鄰接點，所以並不會改變
if(d[y] > d[x] + G[x][y]){
d[y] = d[x] + G[x][y];
fa[y] = x;
}
}
}
for(int i = 1; i <= n; i++)
printf("%d\n",d[i]);
}
return 0;
}
這段代碼如果要算無向圖，在建立圖時，只要稍微修改下而已。
2013 04 26
By ACReaper
