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]

四：

主要代码：

有向图为例：

#include
#include
#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 {
dist[i]=Edge[v0][i];
S[i]=0;
if(i!=v0&&dist[i] path[i]=v0;
else
path[i]=-1;
}
S[v0]=1;dist[v0]=0;//起初S集合中只有源点 特别注意
for(i=0;i {
int min=INF,u=v0;
for(j=0;j {
if(!S[j]&&dist[j] {
u=j;
min=dist[j];
}
}
S[u]=1;//表示找到的最小路径的顶点 特别注意呀
for(k=0;k {
if(!S[k]&&Edge[u][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 {
for(j=0;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 {
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;
}