最短路径 之 Dijkstra 算法

• 最短路径 之 Floyd 算法
• 最短路径 之 Bellman 算法

Dijkstra算法是用于求解单源最短路径，
即求指定顶点s到其余各个顶点的最短路径。

这个最短路径我们用一个dis数组来表示，
从算法开始到算法结束这段时间内我们称dis数组内的值为最短路径的“估计值”。

最开始的时候，我们把原点s到自己的最短路径设为0，即dis[s] = 0。
然后若存在原点s能够直接到达顶点i，则把dis[i]设置为s到i的距离即dis[i] = e[s][i]；
如果不存在则把dis[i]设置为“无穷大”

我们把所有的顶点分为两个集合，一个是已知最短路径的顶点集合P，一个是未知最短路径的顶点集合Q。 Dijkstra算法的核心思想就是每次从集合Q中找一个离s最近的顶点u（dis[u]最小），然后把u加入到集合P中，并检索所有以u为起点以v为终点的边（v为与u相连边的终点），判断dis[v] > dis[u] + e[u][v] 是否成立。如果成立则更新dis[v] = dis[u] + e[u][v]（这个判断更新流程称为“松弛”）。

然后就一直重复上述过程，直至集合Q为空，算法结束。

核心代码

// 这里以1为指定顶点s
book[1] = 1;
for (int i = 1; i < n; i++)    // 因为1已经加入了集合P，所以只循环n-1次即可
{
    int u, min=0xffff;
    for (int j = 1; j <= n; j++)
        if(!book[j] && min > dis[j])
        {
            min=dis[j];
            u=j;
        }
    book[u]=1;
    for (int v = 1; v <= n; v++)
        // 松弛的过程
        if(e[u][v] != 0xffff && dis[v] > dis[u] + e[u][v])
            dis[v] = dis[u] + e[u][v]; 
}

Dijkstra算法与顶点关系密切，适用于稠密图，总的时间复杂度是O(N²)。将寻找离s最近的顶点u这一部分代码用堆优化后时间复杂度可以降至O(NlogN)，如果用邻接表储存图的话时间复杂度会降至O((M+N)logN)。
由于Dijkstra算法是一种基于贪心策略的算法，当所有边权为正时，由于不会存在一个路程更短的点，所有已经加入集合P的点的dis值不会再变，基于这个特点再向外扩展的时候才会保证新扩展的路径最短的。如果存在负权边，那么扩展到负权边的时候会产生更短的路径，就有可能破坏了已经更新的点路程不会再改变的性质，最终可能会导致错误的结果。所以Dijkstra不适用于存在负权边的图，也不能处理负权回路。