目录

• 总目录

1. 最短路
2. Floyd 算法
3. Dijkstra 算法

---

最短路

$Shortest$ $Path$

声明

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

$n$ 为图上点的数目，$m$ 为图上边的数目；

$s$ 为最短路的源点；

定义

在图论中，最短路径 是指在一个加权图中，从起始顶点到目标顶点的所有可能路径中，各边上权值之和最小的那条路径

特殊情况

负环 ：如果图中存在一个环路，且该环路上所有边的权值之和为负数（称为“负环”），那么在这个环里无限循环会使路径总代价不断减小，此时两点之间的最短路径将不存在（趋于无穷小）

---

Floyd 算法

前置知识 ：DP（动态规划）

是一种 多源最短路算法 ，用来求任意两个结点之间的最短路的．

复杂度比较高，但是常数小，容易实现（只有三个 for）．

适用于任何图，不管有向无向，边权正负，但是最短路必须存在．（不能存在负环）

实现

我们定义一个数组 f[k][i][j]，表示只允许经过结点 $1$ 到 $k$ （也就是通过 $1$ 到 $k$ 之中的结点作为中转节点，但 $i$ 或 $j$ 不一定在 $1$ 到 $k$ 之间），结点 $i$ 到结点 $j$ 的最短路长度．

很显然，f[n][i][j] 就是结点 $i$ 到结点 $j$ 的最短路长度

接下来考虑如何求出 f 数组的值．

f[0][i][j] 的数值为： $i$ 与 $j$ ，或 $0$ ，或 $+∞$

定义明细

当 $i$ 与 $j$ 间有直接相连的边的时候，为它们的边权；

当 $i=j$ 的时候为零，因为到本身的距离为零；

当 $i$ 与 $j$ 没有直接相连的边的时候，为 $+∞$

所以 f 数组的状态转移方程为：f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])

其中，f[k-1][i][j] 为不经过 $k$ 点的最短路径，f[k-1][i][k]+f[k-1][k][j] 为经过了 $k$ 点的最短路

即

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

因为第一维（f[k][i][j] 中的 k 维）对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成 f[i][j] = min(f[i][j], f[i][k]+f[k][j])．

部分代码实现

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

综上，时间复杂度是 $𝑂$ $( n^3 )$ ，空间复杂度是 $O$ $( n^2 )$．

---

Dijkstra 算法

Dijkstra 算法于 $1956$ 年发现，$1959$ 年公开发表．是一种求解 非负权图 上单源最短路径的算法．

实现

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

初始化 dis[s]=0 ，其他点的 dis[] 均为 $+\infty$

然后重复这些操作：

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

直到 $T$ 集合为空，算法结束．

时间复杂度

朴素的方法每次执行 操作2 后，直接在 $T$ 集合中暴力寻找最短路长度最小的结点．

操作2 总时间复杂度为 $O(m)$

操作1 总时间复杂度为 $O(n^2)$

全过程的时间复杂度为 $O$ $(n^2 + m)$ $=$ $O$ $(n^2)$．

朴素实现

struct edge {
  int v, w;
};

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

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int fu = 0, t = INT_MAX;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < t) fu = j, t = dis[j];
    vis[fu] = true;
    for (auto fe : e[u]) {
      int fv = fe.v, fw = fe.w;
      if (dis[fv] > dis[fu] + fw) dis[fv] = dis[fu] + fw;
    }
  }
  return ;
}

优先队列优化

可以使用 优先队列 （STL） 维护，通过每次松弛时将结点入队，且弹出时检查该结点是否已被松弛过，若是则跳过

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, INT_MAX, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int fu = q.top().u;
    q.pop();
    if (vis[fu]) continue;
    vis[fu] = 1;
    for (auto fe : e[u]) {
      int v = fe.v, w = fe.w;
      if (dis[fv] > dis[fu] + fw) {
        dis[fv] = dis[fu] + fw;
        q.push({dis[fv], fv});
      }
    }
  }
  return ;
}

综上，

朴素实现 时间复杂度是 $𝑂$ $( n^2 )$

优先队列做法实现 时间复杂度是 $𝑂$ $( m$ $log$ $m )$

---