To boldly go where no one has gone before.

【学习笔记】最短路

2019-05-31 13:23:51


$\text{Floyd}$

$\text{Floyd}$是最暴力的最短路算法,具体思路为枚举中转点,然后枚举另外两个点,用中转点去松弛枚举的两个点。

由于算法特性,常常使用邻接矩阵来存放图的信息。又由于是三层枚举,所以复杂度为$O(n^3)$,并且可以得到任意两点间的最短路长度。对于200以下的小数据是非常不错的选择。

注意:

  1. 由于是邻接矩阵存边,所以建边$(u,v)=w$的时候,应该使用 $dis[u,v]=\min\ (dis[u][v],\ w)$的方法,否则可能会导致之前边的信息被覆盖

  2. 一开始必须先把$dis[u][v]$数组初始化,将到自己的距离设为$0$,否则设为$\text{INF}$,输入完成之后再开始松弛。

  3. 枚举的时候,应该先枚举中转点,这是由算法特性决定的。并且二层枚举的时候,$j$只用枚举到$i$即可,因为$dis[u][v]$是对称的,所以其余的枚举实际上没什么用。这样可以降低常数。

void floyd()
{
    for(int h = 1; h <= v; h++) // attention!
        for(int i = 1; i <= v; i++)
            for(int j = 1; j < i; j++)
                if(G[i][j] > G[i][h] + G[h][j])
                    G[i][j] = G[j][i] = G[i][h] + G[h][j];
    return;
}

int main()
{
    for(int i = 1; i <= v; i++)
        for(int j = 1; j < i; j++)
            G[i][j] = G[j][i] = 0x3f3f3f3f;
    for(int i = 1; i <= e; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        G[a][b] = min(G[a][b], w); // attention!
        G[b][a] = G[a][b];
    }
    floyd();
    return 0;
}

$\text{Dijsktra}$ (堆优化)

算法描述:建立一个以路径长为关键字的小根堆优先队列q,初始化 dis[s] = 0, 将数对$(s,0)$加入优先队列,每次从优先队列中取出当前最短路径估计值最小的点$u$,并对其能到达的店$v$进行松弛,若松弛成功就将更新后的$(v,dis[v])$加入优先队列。重复上述操作,直到优先队列为空。

朴素的 Dijsktra 复杂度为$O(n^2)$,堆优化以后可以跑到$O(nlogn)$。

$\text{SPFA}$

算法描述:建立一个队列q,每次从队首取出节点$u$,并且用$u$当前的最短路径估计值对所有能够到达的点$v$进行松弛。如果松弛能够进行,并且$v$不在队列当中,就把$v$放入队尾。重复上述操作,直到队列为空。

复杂度约为$O(kE)$,其中$k\approx2,E$表示边数。

SPFA 算法可以判断是否出现负环,具体做法为:记录每个点到源点的最短路径上所包含的点数 cnt,初始化 cnt[s] = 1(源点也被包含在内),每次松弛成功就对 cnt 进行更新,也就是 cnt[v] = cnt[u] + 1,如果出现了 cnt[u] > n 的情况,也就是说最短路径上出现了重复的点,很明显就出现了负环。这种算法显然是比以前判断出队次数要快得多的。

最短路树

未完待续…