最短路

标签：松弛 int 短路负环节点 dis

前言

定义

从某一点出发到某一点的最短路

性质

对于边长为正的图：
- 任意两个节点之间的最短路，不会经过重复的节点。
- 任意两个节点之间的最短路，不会经过重复的边。
- 任意两个节点之间的最短路，任意一条的节点数不会超过 \(n\)，边数不会超过 \(n-1\)。

记号

\(n\) 为图上点的数目，\(m\) 为图上边的数目。
\(s\) 为最短路的出发点。
\(D(u)\) 为 \(s\) 点到 \(u\) 点的实际最短路长度。
\(dis(u)\) 为 \(s\) 点到 \(u\) 的估计最短路长度。任何时候有 \(dis(u) \geqslant d(u)\) 。

正文

\(Floyd\) 算法

是用来实现任意两节点之间的最短路的。

复杂度： \(o(n^3)\)

适用于任何图，但不能存在负环。

实现：

示例图：

我们定义一个数组 \(f[k][x][y]\)，表示只允许经过节点 \(1 \to k\) 中，节点 \(x\) 到节点 \(y\) 的路径。

那么 \(f[n][x][y]\) 就是节点 \(x\) 到节点 \(y\) 的最短路长度（此时 \(n\) 个点的子图 \(V'\) 即为图 \(V\) 本身）

特殊的点：

\(f[0][x][y]\):从 \(x \to y\) 的边权，或为 \(0\)，或为 \(+\infty\) 。

\(x\) 与 \(y\) 直接相连：\(x \to y\) 的边权 \(w\)
\(x\) 与 \(y\) 没有直接相连的边：\(+\infty\)
\(x = y\) ：\(0\) 。

主要求和式：

f[k][x][y] = f[k-1][x][y] , f[k-1][x][k] + f[k-1][k][y];

（ \(f[k - 1][x][y]\) 为不经过 \(k\) 点的最短路径，\(f[k-1][x][k] + f[k - 1][k][y]\) 为经过 \(k\) 点的最短路径）

需要枚举任意两点的最短路的话，空间和时间复杂度都是 \(o(n^3)\) 。

实现代码如下：

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
    }
  }
}

优化：空间复杂度：\(o(n^3) \to o(n^2)\)

第一维度对结果无影响，即：

f[k][x][y] = f[k-1][x][y] , f[k-1][x][k] + f[k-1][k][y];

可变为：

f[x][y] = min(f[x][y],f[x][k] + f[k][y]);

实现代码：

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

\(Bellman ford\)算法

\(Bellman–Ford\) 算法是一种基于松弛（ \(relax\) ）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

过程

松弛操作：

对于边 \((u , v)\)，对应下面的松弛操作：\(dis(v)=min(dis(v),dis(u)+w(u,v))\) 。

\(bellman ford\) 算法所做的就是对图上的每一条边进行松弛操作，且当一轮循环中没有成功的松弛操作时，算法停止。

时间复杂度：\(o(nm)\)

特殊情况：如果从 \(S\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。对于最短路存在的图，松弛操作最多只会执行 \(n-1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(S\) 点出发，能够抵达一个负环

负环判断的\(tip\) ：

需要注意的是，以 S 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

实现代码：

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  bool flag;  // 判断一轮循环过程中是否发生松弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int u = 1; u <= n; u++) {
      if (dis[u] == inf) continue;
      // 无穷大与常数加减仍然为无穷大
      // 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
      for (auto ed : e[u]) {
        int v = ed.v, w = ed.w;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          flag = true;
        }
      }
    }
    // 没有可以松弛的边时就停止算法
    if (!flag) break;
  }
  // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
  return flag;
}

列队优化：\(SPFA\)

只有上一次进行过松弛操作，所连接的边，才可能引起下一次的松弛操作。

可以用列队来维护可能引起松弛操作的点。

解释：

如上图，点 \(1\) 为 \(S\) 点，显然只有 \(5\) 和 \(2\) 两点进行了松弛操作，只要用列队存储这两个点，就可以只访问必要的边了。

示例代码：

struct edge {
  int v, w;
};

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

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

\(Dijkstra\) 算法

是一种求解非负权图的单源最短路径的算法

过程

将节点分为两个集合：已确定最短路长度的集合 \((\) 记作 \(S\) 集合 \()\)，和没有确定最短路长度的点集 \((\) 记作 \(T\) 集合 \()\) 。
一开始所有的点属于 \(T\) 集合。

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

然后重复这些操作：

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

直到 \(T\) 集合为 \(empty\)

标签：松弛,int,短路,负环,节点,dis
From： https://www.cnblogs.com/wyl123ly/p/17750799.html

前言

定义

性质

记号

正文