算法学习笔记之图论：最短路问题

mastertravels77

多源最短路

Dijkstra

在Dijkstra算法中，我们将节点分为「已经求得最短路的点」和「还未求得最短路的点」两个集合。算法须求得所有点的最短路，故需循环n次。 在每次循环中从「还未求得最短路的点」中，找出其中距离源点最近的一个点，用这个点更新源点到其它所有点的距离。算法复杂读为O(n^2);
核心代码如下
int dijkstra(){
    dist[1] = 0;

    for(int i = 0;i < n;i++){
        auto t = -1;
        for(int j = 1;j <= n;j++){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        st[t] = true;

        for(int j = 1;j <= n;j++){
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        }
    }

    if(dist[n] == INF)return INF;
    else return dist[n];
}

注：
在最后用t更新其它节点时，那些比t先求得最短路的点其实不会被更新。
Dijkstra算法无法处理含有副权边的情况，原因见下。

考虑反例:
1        1       1
1───────2───────3────── 5
│                  ▲
│                  │
│                  │
└───────────4─────┘
      3            -2根据Dijkstra算法，求得的路径为1->3->5,路径长度为3，但如果走1->4->3->5，长度为2,所以在存在副权边时，Dijkstra算法无法求得正确解。
主要是因为Dijkstra算法每次从「还未求得最短路的点」(即st为false)的点中选取距离源点最近的点(即dist最小)。
初始化阶段所有点的dist最初始化为正无穷,dist[1]被初始化为0;
在第一次循环中，会取t==1,更新过后，dist[1]=0,dist[2]=1,dist[4]=3
在第二次循环中，会取t==2,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3
在第三次循环中，会取t==3,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3,dist[5]=3
在第四次循环中，会取t==4,更新过后，dist[1]=0,dist[2]=1,dist[3]=1,dist[4]=3,dist[5]=3
在第五次循环中，会取t==5,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3,dist[5]=3
堆优化版Dijkstra

void dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>> que;
    que.push({0,1});
    dist[1] = 0;

    while(!que.empty()){
        auto curr = que.top();
        que.pop();

        auto t = curr.second;
        auto dis = curr.first;        

        if(st[t])continue;
        else st[t] = true;


        for(int i = h[t];i != -1;i = ne){
            auto j = e;
            if(dist[j] > dist[t] + w){
                dist[j] = dist[t] + w;
                que.push({dist[j],j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)cout << -1;
    else cout << dist[n];
}
插入数据修改小根堆的时间复杂度为 O(logn)，总的复杂度为O(mnlogn),稀疏图m可以看作n，最后的时间复杂度为O(nlog)。 当图是绸密图时,m比大n x阶，复杂度为(m^x nlogn),显然不如前者。
Bellmen_ford算法

bellman-ford算法对所有边进行(n-1)松弛操作，只要算法中没有负权回路，bellman-ford算法就能求出最短路。复杂度为O(nm)
该算法与dijkstra算法的思路非常相象，不同之处在于一个对点操作，一个对边操作。
void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i = 0;i < n - 1;i++){
        memcpy(last,dist,sizeof dist);
        for(int j = 0;j < m;j++){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b],last[e.a] + e.c);
        }
    }
}
SPFA

仔细看一看bellman-ford算法我们就会发现，在循环当中，有很多边根本不会被更新，只有与一条边相邻的边被更新之后，这条边才会被更新，这提醒我们可以使用queue对算法进行优化。
int spfa(){
    queue<int> que;
    que.push(1);
    dist[1] = 0;
    st[1] = true;

    while(!que.empty()){
        auto curr = que.front();
        que.pop();
        st[curr] = false;

        for(int i = h[curr];i != -1;i = ne){
            auto j = e;
            if(dist[j] > dist[curr] + w){
                dist[j] = dist[curr] + w;
                if(!st[j]){
                    que.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}
一般情况下复杂度为O(m),不过可以构造出一些特殊的数据，使得最坏复杂度为O(nm)
多源最短路

Floyd算法

每次选一个点k做中间结点，对于两点，尝试i-k-j时候比i-j要小。
void floyd(){
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                d[j] = min(d[j],d[k]+d[k][j]);
            }
        }
    }
}
Reference: