Dijkstra算法（單源最短路徑，其邊的權值為非負數），其定義為以固定的一個頂點作為源點，求源點到其他頂點的最短路徑。
一：
集合S表示已經加入最短路徑的頂點，集合T則表示未加入最短路徑的頂點。
二：
為了求源點v0到各個頂點vi的最段短路徑需要設置3個數組，即S[n],path[n],dist[n];
1.S[n]:S[i]=0時表示vi為加入到集合S中，S[i]=1則表示已經加入到集合S中的頂點。初始時S[v0]=1,其余的均為0.
2.path[n]:path[i]表示v0-->vi這條路徑中vi的前一個頂點的序號。
3.dist[n]:dist[i]表示當前找到的v0-->vi的最短路徑的長度，初始時dist[i]=Edge[v0][i].Edge[n][n]表示該圖的鄰接矩陣。
三：
該算法需要做3個步驟：
1：在diat[n]中查找S[i]!=1,且dist[i]最小的頂點u.
2:將S[u]修改為1，表示u加入到集合S中。
3:修改T中每個頂點的vk的dist及path的值，當u--vk有邊且Edge[u][k]<INF（INF為無窮大）且dist[u]+Edge[u][k]<dist[k]時，dist[k]=dist[u]+Edge[u][k],path[k]=u.
四：
主要代碼：
有向圖為例：
#include<stdio.h>
#include<string.h>
#define MAXN 20
#define INF 1000000
int n;
int Edge[MAXN][MAXN];
int S[MAXN];
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0)
{
int i,j,k;
for(i=0;i<n;i++)//對s,dist,path進行初始化 關鍵步驟一
{
dist[i]=Edge[v0][i];
S[i]=0;
if(i!=v0&&dist[i]<INF)
path[i]=v0;
else
path[i]=-1;
}
S[v0]=1;dist[v0]=0;//起初S集合中只有源點 特別注意
for(i=0;i<n-1;i++)//查找最小路徑的頂點u; 關鍵步驟二
{
int min=INF,u=v0;
for(j=0;j<n;j++)
{
if(!S[j]&&dist[j]<min)
{
u=j;
min=dist[j];
}
}
S[u]=1;//表示找到的最小路徑的頂點 特別注意呀
for(k=0;k<n;k++)//對未加入最小路徑的頂點的dist和path的值進行修改 關鍵步驟三
{
if(!S[k]&&Edge[u][k]<INF&&dist[u]+Edge[u][k]<dist[k])
{
dist[k]=dist[u]+Edge[u][k];
path[k]=u;
}
}
}
}
int main()
{
int i,j;
int u,v,w;
scanf("%d",&n);
while(1)
{
scanf("%d %d %d",&u,&v,&w);
if(u==-1&&v==-1&&w==-1)
break;
Edge[u][v]=w;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
Edge[i][j]=0;
else if(Edge[i][j]==0)
Edge[i][j]=INF;
}
}
Dijkstra(0);
int shortest[MAXN];//為了記錄路徑
for(i=1;i<n;i++)
{
printf("%d\t",dist[i]);
memset(shortest,0,sizeof(shortest));
int k=0;
shortest[k]=i;
while(path[shortest[k]]!=0)
{
k++;
shortest[k]=path[shortest[k-1]];
}
k++;
shortest[k]=0;
for(j=k;j>0;j--)
printf("%d->",shortest[j]);
printf("%d\n",shortest[0]);
}
return 0;
}
