最短路径算法

浏览数：114 / 时间：2015年06月08日

Dijkstra算法：

基本思想是：每次找到离源点最近的一个点，然后以改点为中心扩展，最终得到源点到其余所有点的最短路径。

基本步骤：

1、将所有的顶点分为两部分，一部分是已知最短路程的顶点集合P，另一部分是未知最短路程的顶点集合Q。最开始时，第一部分P只有源点一个顶点，我们可以使用book数组标记哪些点在第一不部分中。book[i]=1 就表示这个顶点i在集合P中。

2、设置源点s到自己的最短路径为0，即dis[s]=0，若存在有源点能够直接到达的顶点i，则把dis[i]设为e[s][i]，同时把其他不能直接到源点的顶点的点距离设置为正无穷。

3、在集合Q中选择一个离源点路程最近的顶点u，即dis[u]最小，加入到集合P中，并考察所有顶点u能够到达的点的路程值是否需要更新。如存在一条从u到v的边，那么可以通过将边u》v添加到尾部来拓展一条从s到v的路径，这条路径的长度为dis[u]+e[u][v].如果这个值dis[u]+e[u][v].比目前已知的dis[v]的值要小，我们则更新dis[v]的值为dis[u]+e[u][v]。

4、重复3，直到Q集合为空。算法结束。

其核心部分代码如下：

//存在有源点能够直接到达的顶点i，则把dis[i]设为e[s][i]，同时把其他不能直接到源点的顶点的点距离设置为正无穷
for(i = 1; i <= n; i++)
    dis[i]=e[1][i];

//最开始时，第一部分P只有源点一个顶点
for(i = 1; i <= n; i++)
    book[i] = 0;
book[1] = 1;

//Dijkstra算法核心语句
for(i = 1; i<=n-1; i++)    //还需要往P集中中添加n-1个顶点
{
    //找到离源点最近的顶点
    min = 999999;
    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] < 999999 && dis[v] > dis[u]+e[u][v])
            dis[v] = dis[u]+e[u][v];
    }
}