Dijkstra 算法-通过边实现松弛

一个点（源点） 到其余哥哥顶点的最短路径：单元最短路径。

算法步骤如下：
1。将所有的顶点分为两部分：已知最短路程的顶点集合p和未知最短路径的集合顶点集合Q。最开始，已知最短路径的顶点集合p只有源点一个顶点，我们这里可以用一个book数组来记录哪些顶点在集合p中哪些顶点在集合Q中。book[i]=1,表示在p中，=0在Q中

2.设置源点S到自己的最短路径为0，级dis[s] = 0.若存在有源电能直接到达的顶点，则把dis[i] 设为e[s][i],不能到达的，最短路径设为无穷。

3.在集合q的所有顶点中选一个离源点最近的顶点u加入到集合P中。并考察所有以点U为起点的边，对每一条边进行松弛操作，例如u到v的边可以通过u->v松弛到s->v。路径长度就可以用dis[u]+e[u][v]替代。如果这个值比已知的dis[v]小，就用新值替代旧值。
4.重复第3步，如果集合为空，算法结束。

#include <stdio.h>

int main()
{
int e[10][10],dis[10],book[10],i,j,m,t1,t2,t3,u,v,min;
int inf = 99999999;
scanf("%d %d",&n,&m);

//n表示顶点数，m表示边数
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j] = inf;

//读入边
for(int i=1;i<=m;i++)
    {
scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2] = t3;
    }

for(int i=1;i<=n;i++)
        dos[i] = e[i][j];

//初始化dis数组，这里是1号顶点到其余顶点的初始路程
for(int i=1;i<=n;i++)
        dis[i] = e[1][i];

//book数组初始化
for(int i=1;i<=n;i++)
    {
        book[i] = 0;
    }
    book[1] = 1;

//Dijkstra算法核心语句
for(i=1;i<=n-1;i++)
    {
//找到离1号顶点最近的顶点
        min = inf;
for(j=1;j<=n;j++)
        {
if(book[j] == 0 && dis[j]<min)
            {
                min = dis[j];
                u=j;
            }
        }
        book[u] = 1;
for(v=1;v<=n;v++)
        {
if(e[u][v] < inf)
            {
if(dis[v] > dis[u]+e[u][v])
                    dis[v] = dis[u]+e[u][v];
            }
        }
    }

for(i=1;i<=n;i++)
printf("%d",dis[i]);

    getchar();
    getchar();
return 0;

}

代码如上。终于明白了。