最短路径算法

最短路径算法

在日常生活中，我们经常会想从A地到达B地，但是A->B的路线有非常多，我们通常是希望选择最短的那一条路线，因为人都是懒的~，于是就出现了一个常谈的问题——最短路径问题。谈到最短路径，又会常联系到一种数据结构，那就是图。所以，在图（graph）中探讨最短路径是一个经典的问题。

Dijkstra算法，A*算法

经典的问题自然有经典的解法，Dijkstra算法就是一个经典。Dijkstra算法求出的结果，是原点到图中所有点的距离，从单对单扩展多了单对多的距离。A*算法更是一种聪明的算法，它常常应用在游戏中，避开障碍物找到最佳路劲达到终点。

Dijkstra算法

概述:

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。

缺点：

但由于它遍历计算的节点很多，所以效率比较低。

算法思想：

每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。听起来太简单了？实践操作一下就懂了

例子分析

步骤	S集合	U集合
1	选入A，此时S=此时最短路径A→A=0以A为中间点，从A开始找	U= A→B=6，A→C=3，A→其它U中的顶点=∞，发现A→C=3权值为最短
2	选入C，此时S= 此时最短路径A→A=0，A→C=3以C为中间点，从A→C=3这条最短路径开始找	U= A→C→B=5(比上面第一步的A→B=6要短)此时到D权值更改为A→C→B=5，A→C→D=6，A→C→E=7， A→C→其它U中的顶点=∞，发现A→C→B=5权值为最短
3	选入B，此时S=此时最短路径A→A=0，A→C=3，A→C→B=5以B为中间点从A→C→B=5这条最短路径开始找	U= A→C→B→D=10(比上面第二步的A→C→D=6要长) 此时到D权值更改为A→C→D=6，A→C→B→其它U中的顶点=∞，发现A→C→D=6权值为最短
4	选入D，此时S=此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6以D为中间点，从A→C→D=6这条最短路径开始找	U= A→C→D→E=8(比上面第二步的 A→C→E=7要长)此时到E权值更改为A→C→E=7，A→C→D→F=9发现A→C→E=7权值为最短
5	选入E，此时S=此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E为中间点，从A→C→E=7这条最短路径开始找	U= A→C→E→F=12(比上面第四步的 A→C→D→F=9要长)此时到F权值更改为A→C→D→F=9发现A→C→D→F=9权值为最短
6	选入F，此时S=此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6， A→C→E=7，A→C→D→F=9	U集合已空，查找完毕。

算法分析与实现

首先，我们需要一个二维数组来存储这个图（点和边），并初始化它。e【a】[b] = ? 来表示 a点与b点的距离。

仔细想想，按照上面的例子分析。我们需要有两个集合，一个是已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。我们用一个数组来实现。book[ i ] = 1 则表示这个顶点在集合 P 中，如果 book[ i ] = 0 则表示这个顶点在集合 Q 中。

既然要求原点到每个点的距离，那我们也需要有个东西存储结论。这里也用个数组，dis[ i ] 表示 i 到原点的距离！

设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dis[ i ]设为 e[s][ i }。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。

在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即 dis[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。本来到V的距离是dis[v]，到u的距离是dis[u],现在存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dis[u]+e[u]【v】。如果这个值比目前已知的 dis[v]的值要小，我们可以用新值来替代当前 dis[v]中的值。

结束条件，如果集合 Q 为空，算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径

完整的 Dijkstra 算法代码如下：

include <stdio.h>
int main()
{
    int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
    int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);
    //初始化
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) e[i][j]=0;
              else e[i][j]=inf;
    //读入边
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
    }
    //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
    for(i=1;i<=n;i++)
        dis[i]=e[1][i];
    //book数组初始化
    for(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;
}

可以输入以下数据进行验证。第一行两个整数 n m。n 表示顶点个数（顶点编号为 1~n），m 表示边的条数。接下来 m 行表示，每行有 3 个数 x y z。表示顶点 x 到顶点 y 边的权值为 z。

运行结果是

1	0 1 8 4 13 17

算法总结

算法的时间复杂度是 O(N2)

优化方案：

其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用“堆”（以后再说）来优化，使得这一部分的时间复杂度降低到 O(logN)。
对于边数 M 少于 N2 的稀疏图来说（我们把 M 远小于 N2 的图称为稀疏图，而 M 相对较大的图称为稠密图），我们可以用邻接表来代替邻接矩阵，使得整个时间复杂度优化到 O( (M+N)logN )。请注意！在最坏的情况下 M 就是 N2，这样的话 MlogN 要比 N2 还要大。但是大多数情况下并不会有那么多边，因此(M+N)logN 要比 N2 小很多。

参考资料：

【啊哈！算法】系列 7：Dijkstra 最短路算法

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html

https://wenku.baidu.com/view/2284b709f61fb7360a4c6545.html/

最近一次修改：2017.9.5

修改次数：1