Dijkstra算法（單源最短路徑）
單源最短路徑問題，即在圖中求出給定頂點(diǎn)到其它任一頂點(diǎn)的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。
一.最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)
該性質(zhì)描述為：如果P(i,j)={Vi....Vk..Vs...Vj}是從頂點(diǎn)i到j(luò)的最短路徑，k和s是這條路徑上的一個中間頂點(diǎn)，那么P(k,s)必定是從k到s的最短路徑。下面證明該性質(zhì)的正確性。
假設(shè)P(i,j)={Vi....Vk..Vs...Vj}是從頂點(diǎn)i到j(luò)的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j(luò)的最短路徑相矛盾。因此該性質(zhì)得證。
二.Dijkstra算法
由上述性質(zhì)可知，如果存在一條從i到j(luò)的最短路徑(Vi.....Vk,Vj)，Vk是Vj前面的一頂點(diǎn)。那么(Vi...Vk)也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點(diǎn)V0，首先選擇其直接相鄰的頂點(diǎn)中長度最短的頂點(diǎn)Vi，那么當(dāng)前已知可得從V0到達(dá)Vj頂點(diǎn)的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據(jù)這種思路，
假設(shè)存在G=<V,E>，源頂點(diǎn)為V0，U={V0},dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點(diǎn)。
1.從V-U中選擇使dist[i]值最小的頂點(diǎn)i，將i加入到U中；
2.更新與i直接相鄰頂點(diǎn)的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})
3.知道U=V，停止。
代碼實(shí)現(xiàn):
/*Dijkstra求單源最短路徑 2010.8.26*/
#include <iostream>
#include<stack>
#define M 100
#define N 100
using namespace std;
typedef struct node
{
int matrix[N][M]; //鄰接矩陣
int n; //頂點(diǎn)數(shù)
int e; //邊數(shù)
}MGraph;
void DijkstraPath(MGraph g,int *dist,int *path,int v0) //v0表示源頂點(diǎn)
{
int i,j,k;
bool *visited=(bool *)malloc(sizeof(bool)*g.n);
for(i=0;i<g.n;i++) //初始化
{
if(g.matrix[v0][i]>0&&i!=v0)
{
dist[i]=g.matrix[v0][i];
path[i]=v0; //path記錄最短路徑上從v0到i的前一個頂點(diǎn)
}
else
{
dist[i]=INT_MAX; //若i不與v0直接相鄰，則權(quán)值置為無窮大
path[i]=-1;
}
visited[i]=false;
path[v0]=v0;
dist[v0]=0;
}
visited[v0]=true;
for(i=1;i<g.n;i++) //循環(huán)擴(kuò)展n-1次
{
int min=INT_MAX;
int u;
for(j=0;j<g.n;j++) //尋找未被擴(kuò)展的權(quán)值最小的頂點(diǎn)
{
if(visited[j]==false&&dist[j]<min)
{
min=dist[j];
u=j;
}
}
visited[u]=true;
for(k=0;k<g.n;k++) //更新dist數(shù)組的值和路徑的值
{
if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k])
{
dist[k]=min+g.matrix[u][k];
path[k]=u;
}
}
}
}
void showPath(int *path,int v,int v0) //打印最短路徑上的各個頂點(diǎn)
{
stack<int> s;
int u=v;
while(v!=v0)
{
s.push(v);
v=path[v];
}
s.push(v);
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
}
int main(int argc, char *argv[])
{
int n,e; //表示輸入的頂點(diǎn)數(shù)和邊數(shù)
while(cin>>n>>e&&e!=0)
{
int i,j;
int s,t,w; //表示存在一條邊s->t,權(quán)值為w
MGraph g;
int v0;
int *dist=(int *)malloc(sizeof(int)*n);
int *path=(int *)malloc(sizeof(int)*n);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
g.matrix[i][j]=0;
g.n=n;
g.e=e;
for(i=0;i<e;i++)
{
cin>>s>>t>>w;
g.matrix[s][t]=w;
}
cin>>v0; //輸入源頂點(diǎn)
DijkstraPath(g,dist,path,v0);
for(i=0;i<n;i++)
{
if(i!=v0)
{
showPath(path,i,v0);
cout<<dist[i]<<endl;
}
}
}
return 0;
}