带跳过的加权图遍历
Weighted graph traversal with skips
今天洗澡的时候，我有一个想法 - 编写一个算法来遍历加权有向图并找到最短路径，同时允许跳过固定数量的边 s 是多么困难。我开始考虑甚至跳过一次，对于蛮力方法，它似乎将问题乘以图中的边数，因为您必须为边设置为 0 成本的每种情况找到最短路径，然后比较所有图表。我不知道是否有任何算法可以执行此操作，但粗略搜索 google 没有显示任何内容。
我的第一个问题是跳过成本最高的边，但如果您跳过成本最低的边，检查必须找到一条路径也是一个有趣的问题。
这只是为了满足我的好奇心，所以不要着急。
谢谢！
下面是解决这个问题的逻辑。解决这类问题的方法是考虑一个由你要遍历的原始图的两个副本组成的图，我将描述如何创建它。为了您的利益，绘制一个小图形，然后按拓扑排序绘制它（这有助于可视化，但在程序中不是必需的。）接下来，在原始图形上方几英寸处绘制该图形的副本。当您尚未使用 skip 时，您位于该图的底部，而当您使用 skip 时，您位于该图的顶部。让我们将底部图形中的节点称为 A1、A2、A3 ... 并将顶部图形中的节点称为 B1、B2、B3 ... 如果在您的原始图形中，节点 1 连接到节点 2，那么您的新图形具有边 A1->A2、B1->B2 和一个自由连接 A1->B2（边成本为 0）。
考虑以下原始图表，您从黑色节点开始，并希望在蓝色节点结束。
您的新图表将如下所示，您再次从黑色开始并希望转到蓝色节点。
在图表下半部分的每个位置，您都没有使用跳跃，因此可以跳过（移动到图表的顶部）或者可以正常移动，转到底部的另一个节点图.
然后您可以使用任何标准图遍历算法。
今天洗澡的时候，我有一个想法 - 编写一个算法来遍历加权有向图并找到最短路径，同时允许跳过固定数量的边 s 是多么困难。我开始考虑甚至跳过一次，对于蛮力方法，它似乎将问题乘以图中的边数，因为您必须为边设置为 0 成本的每种情况找到最短路径，然后比较所有图表。我不知道是否有任何算法可以执行此操作，但粗略搜索 google 没有显示任何内容。
我的第一个问题是跳过成本最高的边，但如果您跳过成本最低的边，检查必须找到一条路径也是一个有趣的问题。
这只是为了满足我的好奇心，所以不要着急。
谢谢！
下面是解决这个问题的逻辑。解决这类问题的方法是考虑一个由你要遍历的原始图的两个副本组成的图，我将描述如何创建它。为了您的利益，绘制一个小图形，然后按拓扑排序绘制它（这有助于可视化，但在程序中不是必需的。）接下来，在原始图形上方几英寸处绘制该图形的副本。当您尚未使用 skip 时，您位于该图的底部，而当您使用 skip 时，您位于该图的顶部。让我们将底部图形中的节点称为 A1、A2、A3 ... 并将顶部图形中的节点称为 B1、B2、B3 ... 如果在您的原始图形中，节点 1 连接到节点 2，那么您的新图形具有边 A1->A2、B1->B2 和一个自由连接 A1->B2（边成本为 0）。
考虑以下原始图表，您从黑色节点开始，并希望在蓝色节点结束。
您的新图表将如下所示，您再次从黑色开始并希望转到蓝色节点。
在图表下半部分的每个位置，您都没有使用跳跃，因此可以跳过（移动到图表的顶部）或者可以正常移动，转到底部的另一个节点图.
然后您可以使用任何标准图遍历算法。