具有另一个约束的最短路径
Shortest path with another constraint
给定一个加权无向图，我需要找到两个节点之间的最短路径，实际上是一个经典的最短路径问题。但是还有一个约束：每个节点包含一个"reduction"值，可以用来减少一次遍历的后续边的成本（不仅相邻，而且减少不是累积的）。因此，您可以使用之前经过的节点之一中的 "Reduction" 来降低边的成本（每条边的最终成本不能小于 0）。
请注意，一旦我们通过缩减遍历了一个节点，我们就可以再次将其用于所有后续边（不仅是相邻的，而且它的可用时间不受限制）。减少不累积。
让我们考虑一下这张图：
在此图中，从节点 1 到节点 5 的最短路径是：
- 1 -> 4 成本为 13 (15-2)
- 4 -> 3 成本为 0 (12-12)
- 3 -> 5 成本为 0 (10-12) 在这种情况下，我们重用节点 4 的缩减，因为它大于节点 3 的缩减（我们遍历了节点 n°4 然后我们可以无限量地降低成本 12)。它是 0 而不是 -2，因为边的权重不能为负。
那么从节点1到节点5的总花费为13 + 0 + 0 = 13
为了解决这个问题，我试过使用经典的Dijkstra/Bellman-Ford但是没有用，你能帮我解决这个问题吗？
这似乎可以通过 Bellman-Ford 的变体来解决。
到给定节点的每条路径都可以总结为一对 (C, D)，其中 C 是该路径的成本（折扣后），D 是该路径上可用的最佳折扣因子。由于一旦访问该节点，折扣就可以无限次重复使用，因此始终使用迄今为止在该路径上看到的最大折扣是有意义的。例如，路径 (1 -> 4 -> 3) 的成本 C = 13，折扣 D = 12。
未折扣问题的复杂之处在于，我们无法从成本中判断 "best" 到源和目标之间节点的路径是什么。在您的示例中，路径 (1 -> 2 -> 3) 的成本低于 (1 -> 4 -> 3)，但后者具有更好的折扣，这就是为什么从 1 到 5 的最佳路径是 (1 -> 4 -> 3 -> 5).
而不是记录到每个节点的最低成本路径（在 Bellman-Ford 算法中），我们需要记录从源到该节点的所有 "feasible" 路径。如果没有其他已知路径具有更低的成本和更好的折扣，则可以说一条路径是可行的。算法终止后，我们可以从源到目的地的所有可行路径中选择成本最小的路径，忽略折扣。
(Edit: 我最初建议可以使用 Djikstra 但我认为这不是那么简单。我不确定我们是否可以选择 "the closest" unvisited node in任何有意义的方式，这样我们就可以保证找到最小路径。其他人可能会看到如何让它工作......）
我想你可以使用 Dijkstra-type 算法。 Dijkstra 算法可以被认为是计算包含从源顶点到所有其他顶点的最短路径的最小生成树。我们称其为 "Dijkstra tree"，它包含从给定源顶点开始的所有最短路径。
Dijkstra 不断地向当前树添加新的顶点。对于下一个顶点，他选择最接近当前树的顶点。从 wikipedia 看到这个动画：
因此，当 Dijkstra 将新顶点 v 添加到（当前树的）已插入顶点 u 时，必须考虑 {u, v} 的边权重。在您的情况下，成本不仅仅是 {u, v} 的边权重，而是沿着当前树中到 u 的最短路径减去 vertex-reductions 总和的权重。所以你必须记住顶点中这棵 "Dijkstra" 树的路径上的顶点减少总和。
给定一个加权无向图，我需要找到两个节点之间的最短路径，实际上是一个经典的最短路径问题。但是还有一个约束：每个节点包含一个"reduction"值，可以用来减少一次遍历的后续边的成本（不仅相邻，而且减少不是累积的）。因此，您可以使用之前经过的节点之一中的 "Reduction" 来降低边的成本（每条边的最终成本不能小于 0）。
请注意，一旦我们通过缩减遍历了一个节点，我们就可以再次将其用于所有后续边（不仅是相邻的，而且它的可用时间不受限制）。减少不累积。
让我们考虑一下这张图：
在此图中，从节点 1 到节点 5 的最短路径是：
- 1 -> 4 成本为 13 (15-2)
- 4 -> 3 成本为 0 (12-12)
- 3 -> 5 成本为 0 (10-12) 在这种情况下，我们重用节点 4 的缩减，因为它大于节点 3 的缩减（我们遍历了节点 n°4 然后我们可以无限量地降低成本 12)。它是 0 而不是 -2，因为边的权重不能为负。
那么从节点1到节点5的总花费为13 + 0 + 0 = 13
为了解决这个问题，我试过使用经典的Dijkstra/Bellman-Ford但是没有用，你能帮我解决这个问题吗？
这似乎可以通过 Bellman-Ford 的变体来解决。
到给定节点的每条路径都可以总结为一对 (C, D)，其中 C 是该路径的成本（折扣后），D 是该路径上可用的最佳折扣因子。由于一旦访问该节点，折扣就可以无限次重复使用，因此始终使用迄今为止在该路径上看到的最大折扣是有意义的。例如，路径 (1 -> 4 -> 3) 的成本 C = 13，折扣 D = 12。
未折扣问题的复杂之处在于，我们无法从成本中判断 "best" 到源和目标之间节点的路径是什么。在您的示例中，路径 (1 -> 2 -> 3) 的成本低于 (1 -> 4 -> 3)，但后者具有更好的折扣，这就是为什么从 1 到 5 的最佳路径是 (1 -> 4 -> 3 -> 5).
而不是记录到每个节点的最低成本路径（在 Bellman-Ford 算法中），我们需要记录从源到该节点的所有 "feasible" 路径。如果没有其他已知路径具有更低的成本和更好的折扣，则可以说一条路径是可行的。算法终止后，我们可以从源到目的地的所有可行路径中选择成本最小的路径，忽略折扣。
(Edit: 我最初建议可以使用 Djikstra 但我认为这不是那么简单。我不确定我们是否可以选择 "the closest" unvisited node in任何有意义的方式，这样我们就可以保证找到最小路径。其他人可能会看到如何让它工作......）
我想你可以使用 Dijkstra-type 算法。 Dijkstra 算法可以被认为是计算包含从源顶点到所有其他顶点的最短路径的最小生成树。我们称其为 "Dijkstra tree"，它包含从给定源顶点开始的所有最短路径。
Dijkstra 不断地向当前树添加新的顶点。对于下一个顶点，他选择最接近当前树的顶点。从 wikipedia 看到这个动画：
因此，当 Dijkstra 将新顶点 v 添加到（当前树的）已插入顶点 u 时，必须考虑 {u, v} 的边权重。在您的情况下，成本不仅仅是 {u, v} 的边权重，而是沿着当前树中到 u 的最短路径减去 vertex-reductions 总和的权重。所以你必须记住顶点中这棵 "Dijkstra" 树的路径上的顶点减少总和。