最短路

记号

为了方便叙述，这里先给出下文将会用到的一些记号的含义。

$n$ 为图上点的数目， $m$ 为图上边的数目；
$s$ 为最短路的源点；
$D(u)$ 为 $s$ 点到 $u$ 点的实际最短路长度；
$dis(u)$ 为 $s$ 点到 $u$ 点的估计最短路长度。任何时候都有 $dis(u) \geq D(u)$ 。特别地，当最短路算法终止时，应有 $dis(u)=D(u)$ 。
$w(u,v)$ 为 $(u,v)$ 这一条边的边权。

松弛

先介绍一些算法要用到的松弛（Relaxation）操作。

对于边 $(u,v)$ ，松弛操作对应下面的式子： $dis(v) = \min(dis(v), dis(u) + w(u, v))$ 。这么做的含义是显然的：我们尝试用 $S \to u \to v$ （其中 $S \to u$ 的路径取最短路）这条路径去更新 $v$ 点最短路的长度，如果这条路径更优，就进行更新。

多源最短路

Floyd算法

我们用Floyd算法解决多源最短路问题：

int dist[400][400];
void Floyd(int n) {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

四行代码，简洁明了。Floyd本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i到j的最短路径。

单源最短路

例题：https://www.luogu.com.cn/problem/P4779

Bellman-Ford算法

时间复杂度是 $O(nm)$ 。

void Bellman_Ford(int n, int m) {
    for (int j = 0; j < n - 1; ++j)
        for (int i = 1; i <= m; ++i)
            dist[edges[i].to] = min(dist[edges[i].to], dist[edges[i].from] + edges[i].w);
}

SPFA算法

Shortest Path Faster Algorithm (SPFA)），国际上一般认为是队列优化的Bellman-Ford 算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int  long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
int dist[MAXN], inqueue[MAXN];
int head[MAXN];
int cnt = 1;
int n, m, q;
struct Edge {
    int from, to, w, next;
} edges[MAXN];

void add(int u, int v, int w) {//添加一条边u--v
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

void SPFA(int s) {
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
        int p = Q.front();
        Q.pop();
        inqueue[p] = 0;
        for (int e = head[p]; e != 0; e = edges[e].next) {
            int to = edges[e].to;
            if (dist[to] > dist[p] + edges[e].w) {
                dist[to] = dist[p] + edges[e].w;
                if (!inqueue[to]) {
                    inqueue[to] = 1;
                    Q.push(to);
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m >> q;
//    memset(dist, 63, sizeof(dist));
    for (int i = 1; i <= n; ++i)dist[i] = inf;
    dist[q] = 0;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    SPFA(q);
    for (int i = 1; i <= n; ++i) {
        if (dist[i] != inf)cout << dist[i] << ' ';
        else cout << fixed << setprecision(0) << pow(2, 31) - 1 << ' ';
    }
}

Dijkstra算法

Dij用于单源最短路基于一种贪心的思想，适用于一张没有负边的图。若有负边 ~~（有边边）~~ 则要用到上面的两种算法了。

过程

将结点分成两个集合：已确定最短路长度的点集（记为 $S$ 集合）的和未确定最短路长度的点集（记为 $T$ 集合）。一开始所有的点都属于 $T$ 集合。

初始化 $dis(s)=0$ ，其他点的 $dis$ 均为 $+\infty$ 。

然后重复这些操作：

从 $T$ 集合中，选取一个最短路长度最小的结点，移到 $S$ 集合中。
对那些刚刚被加入 $S$ 集合的结点的所有出边执行松弛操作。

证明

实现

// 暴力实现
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
    vis[u] = true;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
    }
  }
}

// 堆优化
struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

例题

L2-001 紧急救援多条最短路，点权和最大

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

struct {
    int to, w, next;
} edge[MAXN * 2];
int head[MAXN], vis[MAXN], dis[MAXN], weight[MAXN], num[MAXN];
int cnt;
int n;
int x, y, m, z;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
priority_queue<pair<int, int>> path[MAXN]; // 点权总和，点编号

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

void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    num[s] = 1;
    path[s].push(make_pair(weight[0], s));
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
                while (!path[v].empty())path[v].pop();
                path[v].push(make_pair(path[u].top().first + weight[v], u));
                num[v] = num[u];
            } else if (dis[u] + w == dis[v]) {
                q.push({dis[v], v});
                path[v].push(make_pair(path[u].top().first + weight[v], u));
                num[v] += num[u];
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    int s, d;
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; ++i)cin >> weight[i];
    memset(head, -1, sizeof(head));
    while (m--) {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    dijkstra(s);
    cout << num[d] << ' ' << path[d].top().first << '\n';
    vector<int> ans;
    for (int i = d; i != s; i = path[i].top().second)ans.push_back(i);
    ans.push_back(s);
    for (auto it = ans.rbegin(); it != ans.rend(); it++)cout << *it << " \n"[it + 1 == ans.rend()];
}

最后更新于2年前

这有帮助吗？