• Floyd 算法（多源汇正权最短路）适用于求任意节点之间的最短路，需要三层循环枚举中转点 i、枚举起点 j 和枚举终点 k，时间复杂度最高。
• Bellman Ford 算法（单源负权最短路）在每一轮迭代中，尝试对图上每一条边进行松弛，直到没有松弛操作时结束。
• Dijkstra 算法（单源正权最短路）：在每一轮迭代中，使用确定集中最短路长度最小的节点去松弛相邻节点，由于负权边会破坏贪心策略的选择，无法处理负权问题；稀疏图小顶堆的写法更优，稠密图朴素写法更优。

最短路算法FloydBellman-FordDijkstraJohnson最短路类型每对结点之间的最短路单源最短路单源最短路每对结点之间的最短路作用于任意图任意图非负权图任意图能否检测负环？能能不能能时间复杂度O(n^3)O(nm)O(mlgn)最小堆O(nmlgm)

其中 n 是节点数，m 是边数。

问题结构化

1、概括问题目标

计算从 start 到 target 节点的最小代价。

2、观察数据特征

• 数据大小：节点数据范围的上界是 10^5，相比于节点范围，特殊路径最多只有 200 条，特殊路径是稀疏的。

3、分析问题要件

以 start 为起点，target 为终点，在每次操作可以从 from 节点移动到 to 节点，花费的代价是 |x2 - x1| + |y2 - y1|，另外二维平面中有一些特殊路径，花费的代价是特殊的。

4、提高抽象程度

• 曼哈顿距离：花费的代价是 |x2 - x1| + |y2 - y1| 就是两个节点之间的曼哈顿距离；
• 正权边：「从 from 节点移动到 to 节点的代价 x」等价于「从 from 节点到 to 节点的边权为 x」；
• 有向边：由于题目描述特殊路径只能从 (x1, y1) 走到 (x2, y2)，因此题目是有向边；
• 是否为决策问题？由于每次操作有多种移动位置选择，因此这是决策问题，准确来说是最短路问题；
• 总结：这是一道图的单源正权有向边的最短路问题。

5、具体化解决方案

如何解决图的单源正权最短路问题？

这道题只需要计算从 start - target 之间的最短路问题，而且边是非负权边，符合 Dijkstra 算法的应用场景。Dijkstra 算法的本质是贪心 + BFS，我们需要将所有节点分为 2 类，在每一轮迭代中，我们从 “候选集” 中选择距离起点最短路长度最小的节点，由于该点不存在更优解，所以可以用该点来 “松弛” 相邻节点。

• 1、确定集：已确定（从起点开始）到当前节点最短路径的节点；
• 2、候选集：未确定（从起点开始）到当前节点最短路径的节点。

需要考虑哪些节点？

这道题没有限制只能走特殊路径，那么是不是二维平面上所有节点都需要考虑在呢？其实需要，结合「三角不等式」观察，我们发现两个点连续走两次曼哈顿距离没有意义，也就是说，目标路径一定是在起点、终点和特殊路径节点中间移动。

• 策略 1：从 from 到 to 走曼哈顿距离；
• 策略 2：先从 from 走到特殊路径起点，走完特殊路径后再走曼哈顿距离；
• 策略 3（没有意义）：先从 from 走曼哈顿距离到 x，再从 x 走曼哈顿距离到 to。

如何表示二维节点？

最简单的方法是通过位移将 (x, y) 压缩为一个唯一整数，由于这道题的坐标范围最大到 10^5，所以应该转化到长整型。

val U = 100000L // 数值上界 + 1压缩：val key = x * U + y还原：val x = (key / U).toInt()val y = (key % U).toInt()

至此，我们可以使用朴素 Dijkstra 算法模拟问题。

是否有优化空间？

朴素 Dijkstra 的每轮迭代中需要遍历 n 个节点寻找候选集中的最短路长度。事实上，这 n 个节点中有部分是 “确定集”，有部分是远离起点的边缘节点，每一轮都遍历显得没有必要。我们使用小顶堆记录候选集中最近深度的节点。不过，这道题是稠密图，朴素 Dijkstra 优于 Dijkstra + 最小堆。

继续挖掘三角不等式性质：

由于连续走两次曼哈顿距离没有意义，那我们甚至不需要把特殊路径的起点考虑到图中，或者说直接可以使用 specialRoads 数组，而不需要建图的步骤。

6、答疑

• 这道题的数据范围到 10^5，而特殊路径最多只有 200 条，不是应该算稀疏图？

这个观点混淆了稠密图的定义，稠密或稀疏取决于边数相对于节点数的大小。简单来说，在节点数固定的情况下，边数越大则图越稠密。在这道题中，每个节点都存在到其他所有节点的路径，因此不仅是稠密图，甚至是完全图。

题解一（朴素 Dijkstra）

• 使用 Dijkstra 算法解决最短路问题。

class Solution {    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {        // 单源正权最短路        val U = 100001L // 数值上界 + 1        val INF = 0x3F3F3F3F        val startL = start<0> * U + start<1>        val targetL = target<0> * U + target<1>        if (startL == targetL) return 0                // 1、节点与最短路长度        val nodes = HashMap<Long, Int>()        // 1.1 特殊路径上的节点        for (road in specialRoads) {            // 过滤无意义的特殊路径（路径花费大于曼哈顿距离）            nodes * U + road<1>> = INF            nodes * U + road<3>> = INF        }        // 1.2 起点节点与终点节点        nodes = INF        nodes = 0 // 起点可能为终点，如果开头不做特判需要注意顺序        // 2、建有向图（邻接表）<from -> <to -> cost>>        val graph = HashMap<Long, HashMap<Long, Int>>()        // 2.1 节点之间的路径（双向边）        for ((from, _) in nodes) {            graph = HashMap<Long, Int>()            val fromX = (from / U).toInt()            val fromY = (from % U).toInt()            for ((to, _) in nodes) {                if (from == to) continue                val toX = (to / U).toInt()                val toY = (to % U).toInt()                graph!! = Math.abs(toX - fromX) + Math.abs(toY - fromY)            }        }        // 2.2 特殊路径（单向边）        for (road in specialRoads) {            val from = road<0> * U + road<1>            val to = road<2> * U + road<3>            graph!! = Math.min(graph!!.getOrDefault(to, INF), road<4>) // 特殊路径的花费可能更长        }        // 3、访问标记        val visit = HashSet<Long>()        // 4、朴素 Dijkstra        while (true) {            // 寻找候选集中最短路长度最短的节点            var minNode = -1L            var minDis = -1            for ((to, dis) in nodes) {                if (visit.contains(to)) continue                if (minDis == -1 || dis < minDis) {                    minDis = dis                    minNode = to                }            }            // println("minNode=$minNode, minDis=$minDis")            // 找到目标点的最短路长度            if (minNode == targetL) return minDis            // 访问标记            visit.add(minNode)            // 松弛相邻节点            for ((to, cost) in graph!!) {                // println("to=$to, cost=$cost")                if (minDis + cost < nodes!!) {                    nodes = minDis + cost                }            }        }        return -1 // 必然有解    }}

复杂度分析：

• 时间复杂度：O(n^2) 其中 n 是 specialRoads 特殊路径数组的长度；
• 空间复杂度：O(n^2) 图空间 + 标记数组空间。

题解二（Dijkstra 优化）

• 优化：剪去图空间。

class Solution {    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {        // 单源正权最短路        val U = 100001L // 数值上界 + 1        val INF = 0x3F3F3F3F        val startL = start<0> * U + start<1>        val targetL = target<0> * U + target<1>        if (startL == targetL) return 0        // 1、节点与最短路长度        val nodes = HashMap<Long, Int>()        // 起点节点与终点节点        nodes = INF        nodes = 0 // 起点可能为终点，如果开头不做特判需要注意顺序        // 2、访问标记        val visit = HashSet<Long>()        // 3、朴素 Dijkstra        while (true) {            // 寻找候选集中最短路长度最短的节点            var minNode = -1L            var minDis = -1            for ((to, dis) in nodes) {                if (visit.contains(to)) continue                if (minDis == -1 || dis < minDis) {                    minDis = dis                    minNode = to                }            }            // println("minNode=$minNode, minDis=$minDis")            // 找到目标点的最短路长度            if (minNode == targetL) return minDis            // 访问标记            visit.add(minNode)            val minNodeX = (minNode / U).toInt()            val minNodeY = (minNode % U).toInt()            // 1、直接到终点            nodes = Math.min(nodes!!, minDis + Math.min(nodes!!, (target<1> - minNodeY) + (target<0> - minNodeX)))            // 2、先经过特殊路径（minNode -> 特殊路径的起点 -> 特殊路径的终点）            for (road in specialRoads) {                val specialTo = road<2> * U + road<3>                if (specialTo == minNode) continue // 重复路径                val specialDis = minDis + Math.abs(road<0> - minNodeX) + Math.abs(road<1> - minNodeY) + road<4>                if (specialDis < nodes.getOrDefault(specialTo, INF)) {                    nodes = specialDis                }            }        }        return -1 // 必然有解    }}

复杂度分析：

• 时间复杂度：O(n^2) 其中 n 是 specialRoads 特殊路径数组的长度；
• 空间复杂度：O(n) 标记数组空间。

题解三（Dijkstra + 最小堆）

附赠一份 Dijkstra + 最小堆的代码：

class Solution {    fun minimumCost(start: IntArray, target: IntArray, specialRoads: Array<IntArray>): Int {        // 单源正权最短路        val U = 100000L // 数值上界 + 1        val INF = 0x3F3F3F3F        val startL = start<0> * U + start<1>        val targetL = target<0> * U + target<1>        if (startL == targetL) return 0        // 1、节点与最短路长度        val nodes = HashMap<Long, Int>()        // 起点节点与终点节点        nodes = INF        nodes = 0 // 起点可能为终点，如果开头不做特判需要注意顺序        // 2、最小堆        val heap = PriorityQueue<Long>() { l1, l2 ->            nodes.getOrDefault(l1, INF) - nodes.getOrDefault(l2, INF)        }        heap.offer(startL)        heap.offer(targetL)        // 3、Dijkstra        while (!heap.isEmpty()) {            // 候选集中最短路长度最短的节点            val minNode = heap.poll()            val minDis = nodes!!            // println("minNode=$minNode, minDis=$minDis")            // 找到目标点的最短路长度            if (minNode == targetL) return minDis            val minNodeX = (minNode / U).toInt()            val minNodeY = (minNode % U).toInt()            // 1、直接到终点            val newDirectToTarget = minDis + Math.min(nodes!!, (target<1> - minNodeY) + (target<0> - minNodeX))            if (newDirectToTarget < nodes!!) {                nodes = newDirectToTarget                heap.offer(targetL)            }            // 2、先经过特殊路径（minNode -> 特殊路径的起点 -> 特殊路径的终点）            for (road in specialRoads) {                val specialTo = road<2> * U + road<3>                if (specialTo == minNode) continue // 重复路径                val specialDis = minDis + Math.abs(road<0> - minNodeX) + Math.abs(road<1> - minNodeY) + road<4>                if (specialDis < nodes.getOrDefault(specialTo, INF)) {                    nodes = specialDis                    heap.offer(specialTo)                }            }        }        return -1 // 必然有解    }}

复杂度分析：

• 时间复杂度：O(m·lgm) 其中 n 是 specialRoads 特殊路径数组的长度，m 是边数，由于这道题是完全图，所以有 m = n^2；
• 空间复杂度：O(n) 标记数组空间。

近期周赛最短路问题：

• 2612. 最少翻转操作数（Hard）
• 2608. 图中的最短环（Hard）
• 2577. 在网格图中访问一个格子的最少时间（Hard）

Q4. 字典序最小的美丽字符串（Hard）

https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/

题目描述

如果一个字符串满足以下条件，则称其为 美丽字符串 ：

• 它由英语小写字母表的前 k 个字母组成。
• 它不包含任何长度为 2 或更长的回文子字符串。

给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。

请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。

对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。

• 例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

示例 1：

输入：s = "abcz", k = 26输出："abda"解释：字符串 "abda" 既是美丽字符串，又满足字典序大于 "abcz" 。可以证明不存在字符串同时满足字典序大于 "abcz"、美丽字符串、字典序小于 "abda" 这三个条件。

示例 2：

输入：s = "dc", k = 4输出：""解释：可以证明，不存在既是美丽字符串，又字典序大于 "dc" 的字符串。

提示：

• 1 <= n == s.length <= 105
• 4 <= k <= 26
• s 是一个美丽字符串

问题结构化

1、概括问题目标

构造一个满足条件的目标字符串，命名为「美丽字符串」。

2、分析问题要件

• 字符集：题目要求目标字符串仅能使用小写字母表的前 k 个字母，例如 k = 4 只能使用 {a, b, c, d}；
• 美丽字符串（限制回文）：题目要求目标字符串不包含长度大于 1 的回文子串；
• 字典序更大：题目要求目标字符串的字典序大于字符串 s；
• 字典序最小：题目要求返回字典序最小的方案；

3、观察数据特征

• 数据量：数据量的上界是 10^5，这要求算法的时间复杂度不能高于 O(n^2)；
• 输入字符串 s 本身就是「美丽字符串」。

4、观察测试用例

以 s = “abcz”, k = 26 为例：

• 修改 ‘z’：无法修改 ’z’ 获得字典序更高的字母；
• 修改 ‘c’：可以修改 ‘c’ 为 ’d’ 得到 “abdz”，且构成「美丽字符串」；
• 修改 ‘a’ 或 ’b’：也可以构造「美丽字符串」，但字典序不会优于 “abdz”。

5、提高抽象程度

• 权重：字典序的规则中，字符串越靠前的位置对排序的影响权重越大，例如序列 ”ba“ 的字典序大于 ”az“；
• 提升：为了构造字典序更大的「美丽字符串」，我们需要将字符串中的某个字母修改为字母序更大的字母，例如将 ‘a’ 提升到 ‘b’ 或 ‘z’；
• 下一个排列：题目要求目标字符串的字典序大于字符串 s，又是所有方案中字典序最小的，问题模型类似经典题目「31. 下一个排列」，可以借鉴；
• 是否为决策问题：由于每次提升操作有多种位置选择，因此这是个决策问题，准确来说是一个构造问题。
• 总结：这是一个构造问题，要求构造满足条件的「下一个美丽字符串」。

6、具体化解决手段

如何构造满足条件的「下一个美丽字符串」？

由于题目要求构造字典序最小的方案，那么将 s 提升为字母序更大的下一个字母是最优的，例如将 ’a’ 提升到 ‘b’ 优于提升到 ‘z’。除非在 s 已经是字典序最大的字母 ‘z’ 时，我们需要提升它的前一个字母 s，例如将 ”az“ 提升为 ”bz“ 优于 “cz”。

阶段一：提升 swhile (i 从后往前遍历) {  for (c in s + 1 until 'a' + k) { // 枚举字符集    if (存在回文信息) continue    s = c // 确定有效性    // 记录下标 i  }  // 无法提升 s，尝试提升 s}阶段二：// 将  = c    break  }}

class Solution {    fun smallestBeautifulString(s: String, k: Int): String {        val n = s.length        val U = 'a' + k        val sArray = s.toCharArray()        var pos = -1        outer@ for (i in n - 1 downTo 0) {            // 尝试提升字母序            for (c in sArray + 1 until U) {                // 验证有效性（只需要验证左边）                if ((i > 0 && c == sArray) || (i > 1 && c == sArray)) continue                sArray = c                pos = i                break@outer            }        }        // 无法构造        if (pos < 0) return ""        for (i in pos + 1 until n) {            for (c in 'a' until U) {                // 验证有效性（只需要验证左边）                if ((i > 0 && c == sArray) || (i > 1 && c == sArray)) continue                sArray = c                break            }        }        return String(sArray)    }}