https://www.cnblogs.com/alex-wei/p/basic_graph_theory.html
by elbissoPtImaerD @ 2024-04-14 13:22:28
"删除边最短路"（Shortest Path with Edge Deletions）是一个常见的图论问题，其目标是在给定的有向图中找到从源节点到目标节点的最短路径，可以删除最多 k 条边。这个问题可以使用动态规划和 Dijkstra 算法来解决。
以下是一个基于 Dijkstra 算法的解决方案的详细步骤：
1. 构建图：首先，需要将问题转化为有向图的形式。有向图的节点表示图中的顶点，有向边表示图中的边。每条边都有一个权重，表示通过该边的代价。如果我们要求解从节点 A 到节点 B 的最短路径，我们可以使用一个邻接列表或邻接矩阵来表示图。
2.初始化距离数组：初始化一个距离数组 distance，用于记录从源节点到每个节点的当前最短路径长度。初始时，将源节点的距离设为 0，将其他节点的距离设为无穷大。
3. 使用优先队列进行 Dijkstra 搜索： 使用 Dijkstra 算法搜索从源节点到目标节点的最短路径。Dijkstra 算法是一种贪心算法，每次选择当前距离源节点最近的节点进行扩展。我们可以使用优先队列（如 C++ 中的 std::priority_queue）来快速找到当前距离源节点最近的节点。
4. 动态规划更新距离数组： 在 Dijkstra 算法的基础上，我们需要引入一个额外的维度来记录删除边的数量。设立一个三维数组 dp，其中 dp[i][j][k] 表示从源节点到节点 i，删除了 j 条边，且最后一条边的起点是节点 k 的最短路径长度。根据当前节点与上一个节点之间是否有边以及已删除的边数，更新 dp 数组中的值。
5. 遍历所有可能的删除边数量：在使用 Dijkstra 算法进行搜索的同时，遍历所有可能的删除边数量，即从 0 到 k。在每个删除边数量下，更新距离数组中的值。
6. 返回结果：在搜索完成后，距离数组中的值就是从源节点到目标节点的最短路径长度。根据需要，返回相应的最短路径或长度。
这就是解决 "删除边最短路" 问题的基本步骤。实现时需要注意细节和边界情况，以确保算法的正确性和高效性。
by SiuuuCR7 @ 2024-04-14 15:03:41
求点赞加关注
by SiuuuCR7 @ 2024-04-14 15:04:10
@[SiuuuCR7](/user/1339828) 复杂度不对，GPT 回答就别求关注了吧。。
by TLEWA @ 2024-04-14 18:58:13