「图论」最短路模版

求最短路是图论中的一项基本操作

最短路模版题目: Heat Wave

本文介绍一下几种最短路算法（水chao题leng解fan

题目描述

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。 $Farmer\;John$ 此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

$FJ$ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过 $T (1 \le T \le 2,500)$ 个城镇，方便地标号為 $1$ 到 $T$ 。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 $C (1 \le C \le 6,200)$ 条直接连接 $2$ 个城镇的道路。每条道路由道路的起点 $Rs$ ，终点 $Re$ $(1 \le Rs \le T; 1 \le Re \le T)$ ，和花费 $(1 \le Ci \le 1,000)$ 组成。求从起始的城镇 $Ts (1 \le Ts \le T)$ 到终点的城镇 $Te(1 \le Te \le T)$ 最小的总费用。

简化版本:

给定一个无向图，求 S 点到 T 点的最短路径

对于这道题目，我们可以使用图论中的最短路算法

Dijkstra
Bellman-Ford
SPFA
Floyd

Dijkstra

Dijkstra的算法流程：

初始化每个点的 $dist$ 为 $0$ ，其余节点的 $dist$ 为 $INF$ ( $0\text {x}3f$ )
找到一个没有被标记的， $dist$ 最小的节点 $v$ , 然后标记节点 $v$
扫描节点 $v$ 的所有出边 $(from,\;to,\;d)$ , 若 $dist_{to} > dist_{from} + d$ 则用 $dist_{from} + d$ 更新 $dist_{to}$
重复 $2$ 和 $3$ 直到所有点被标记

Dijkstra基于贪心思想qwq，她只适用于长度非负数的图

朴素的Dijkstra的时间复杂度为 $O(mn)$
带堆优化的Dijkstra的时间复杂度为 $O(m\log n)$

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#include <vector>
#include <queue>
#include <set>

#define DEBUG(x) cerr << #x << '=' << x << endl

const int MAXN = 2500 + 5;

struct Node;
struct Edge;

class Node {
public:
    int dist;
    bool used;
    // 用于维护Dijkstra

    Edge *firstEdge;
} node[MAXN];

class Edge {
public:
    Node *s,*t;
    int w;
    Edge *next;
    Edge (Node *s, Node *t, int w) : s(s), t(t), w(w), next(s->firstEdge) {}
};

inline void add (const int &s, const int &t, const int &w) {
    node[s].firstEdge = new Edge(&node[s], &node[t], w);
    node[t].firstEdge = new Edge(&node[t], &node[s], w);
}

inline void init (const int &n) {
    for(int i = 1; i <= n; i++){
        node[i].dist = 0x3f3f3f;
        node[i].used = false;
    }
}

int dijkstra(const int &s,const int &t,const int &n){
    init (n);

    std::priority_queue<std::pair<int, Node*>, std::vector<std::pair<int, Node*> >, std::greater<std::pair<int, Node*> > > q;
    q.push(std::make_pair(node[s].dist = 0, &node[s]));

    while(!q.empty()) {
        Node *v = q.top().second;
        q.pop();
        if(v->used) continue;
        v->used = true;
        for(Edge *is = v->firstEdge; is; is = is->next){
            if(is->t->dist > v->dist + is->w){
                is->t->dist = v->dist + is->w;
                q.push(std::make_pair(is->t->dist, is->t));
            }
        }
    }
    return node[t].dist;
}

int main(int argc, char const *argv[]) {
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    printf("%d", dijkstra(s, t, n));
    return 0;
}

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#include <vector>
#include <queue>
#include <set>

const int MAXM = 6200 + 5;
const int MAXN = 2500 + 5;

struct Edge{
    int v,next,w;
}edge[MAXM * 2];

int firstEdge[MAXN];
int dist[MAXN];
bool inQueue[MAXN];
int cnt;

inline void add(int u,int v,int w){
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = firstEdge[u];
    firstEdge[u] = cnt;
}

inline int dijkstra(int s,int t,int n){
    for(int i = 1;i <= n;i++)
        dist[i] = INT_MAX;
    std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > > q;
    inQueue[s] = true;
    q.push(std::make_pair(s,0));
    dist[s] = 0;
    while(!q.empty()){
        int v = q.top().first;
        int value = q.top().second;
        q.pop();
        for(int e = firstEdge[v]; e;e = edge[e].next){
            //int to = edge[i].v;
            if(dist[edge[e].v] > value + edge[e].w){
                dist[edge[e].v] = value + edge[e].w;
                q.push(std::make_pair(edge[e].v,dist[edge[e].v]));
            }
        }
    }
    return dist[t];
}

int main(int argc, char *const argv[]){
    int n,m,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1;i <= m;i++){
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        add(s,t,w);
        add(t,s,w);
    }
    printf("%d",dijkstra(s,t,n));
    return 0;
}

Bellman-Ford

对于每一条边 $edge$ ，如果 $dist_{from}+d<dist_{to}$ ，则令 $dist_{to}=dist_{from}+d$ 。若上述操作没有对 $dist$ 进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环

显然的 $\text {Bellman-Ford}$ 的时间复杂度为 $O(mn)$

origin[i]表示编号为i这条边的起点编号，
destination[i]表示编号为i这条边的终点编号，
value[i]表示编号为i这条边的权值，

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>

int dis[10010];
int origin[10010],destination[10010],value[10010];//刚刚说过的三个数组

int n,m;

void Bellman_ford(int a) {
    memset(dis, 0x3f, sizeof (dis));//赋初始值
    dis[a] = 0;
    for(int i = 1; i <= n - 1; i++) //更新n - 1次
        for(int j = 1; j <= m; j++) //更新每一条边
            dis[destination[j]] = min (dis[destination[j]], dis[origin[j]] + value[j]); //判断是否更新
} 

int main(int argc, char *const argv[]) {
    std::cin >> n >> m;
    for(int i = 1; i <= m; i++) std::cin >> origin[i] >> destination[i] >> value[i];
    Bellman_ford (1);
    for(int i = 1; i <= n; i++) std::cout << dis[i] << " "; 
}

SPFA

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>

const int MAXM = 6200 + 5;
const int MAXN = 2500 + 5;

struct Edge{
    int v,next,value;
}edge[MAXM * 2];//双向边开2倍

int firstEdge[MAXN];
int cnt;
int dist[MAXN];
bool inQueue[MAXN];

inline void add(int u,int v,int w){
    edge[++cnt].v = v;
    edge[cnt].next = firstEdge[u];
    edge[cnt].value = w;
    firstEdge[u] = cnt;
}

inline int spfa(int s,int t,int n){
    for(int i = 1;i <= n;i++)
        dist[i] = INT_MAX;
    dist[s] = 0;
    inQueue[s] = true;
    std::queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        inQueue[v] = false;
        for(int e = firstEdge[v];e;e = edge[e].next){
            if(dist[edge[e].v] > dist[v] + edge[e].value){
                dist[edge[e].v] = dist[v] + edge[e].value;
                if(!inQueue[edge[e].v]){
                    q.push(edge[e].v);
                    inQueue[edge[e].v] = true;
                }
            }
        }
    }
    return dist[t];
}

int main(int argc, char *const argv[]){
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1;i <= m;i++){
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        add(s,t,w);
        add(t,s,w);
    }
    printf("%d",spfa(s,t,n));
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define inf 2e31-1;
#define DEBUG(x) std::cerr << #x << "=" << x << std::endl
#define MAXN 2500 + 5
struct Node;
struct Edge;
//邻接表存储图
struct Node{
    Edge *firstEdge;
    int dist;
    bool inQueue;
} node[MAXN];
struct Edge{
    Node *s, *t;
    int w;
    Edge *next;
    Edge(Node *s, Node *t, int w) : s(s), t(t), w(w), next(s->firstEdge) {}
};
inline void add(const int &s,const int &t,const int &w){
    node[s].firstEdge = new Edge(&node[s], &node[t],w);
    node[t].firstEdge = new Edge(&node[t], &node[s], w);
}
inline int spfa(const int &s,const int &t,const int &n){ //核心代码
    for (int i = 1; i <= n; i++){
        node[i].dist = inf;
        node[i].inQueue = false;
    }
    queue<Node *> q;
    q.push(&node[s]);
    node[s].dist = 0;
    node[s].inQueue = true;
    while(!q.empty()){
        Node *u = q.front();
        q.pop();
        u->inQueue = false;
        for(Edge *e = u->firstEdge; e; e = e->next){
            Node *v = e->t;
            if(v->dist > u->dist + e->w){
                v->dist = u->dist + e->w;
                    if(!v->inQueue){
                        q.push(v);
                        v->inQueue = true;
                    }
                }
            }
        }
        return node[t].dist;
}
int main(){
    int n,m,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1;i <= m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    printf("%d",spfa(s,t,n));
    return 0;
}

Floyd

Floyd 可以求任意两点间最短路径.

采用了dp的思想， $k$ 是dp中的阶段，必须置于循环体外层!!

Floyd 算法时间复杂度: $O(n^3)$

Code:

for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j];

Floyd那么慢，有什么用呢？

经典问题：传递闭包

在交际网络中，给定 $n$ 个元素和若干对二元关系，且关系具有传递性，同过传递性求出更多元素之间的关系

Code:

for (int k = 1; i <= n; k ++)
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            d[i][j] |= d[i][k] & d[k][j];