algorithm - 图中没有重复的最短路径

Question

我有一个有向图，每个节点都包含一个字母，每条边都有权重。我想找到从开始节点到结束节点的最短路径，它没有显示不按顺序显示的字母并且其中包含所有字母。例如：

I have those nodes: 1 - start node, 2- end node, 3 - 'A' letter, 4 - 'B' letter, 5 - 'B' letter, 6 - 'A' letter, 7 - 'B' letter.
And the edges are: 1 -> 3, 1 -> 4, 3 -> 5, 4 -> 5, 5 -> 6, 5-> 7, 6 -> 2, 7 -> 2.

图表如下所示：

对我来说唯一有效的路径是：

1 -> 3 -> 5 -> 7 -> 2 ('ABB'), 1 -> 4 -> 5 -> 6 -> 2 ('BBA').

我想选择“BBA”，因为它是最短的。如果我尝试使用 dijkstra，当我到达节点号 6 时，我的路径将通过节点号 3 和 5。然后我会将边的权重 (5 -> 6) 设置为这条路径的 Infinity 所以它不会走这条路。但是，因为它已经知道到节点 5 的最短路径是通过节点 3，所以它将选择路径“ABB”。我怎样才能得到正确的路径？

编辑：我想要找到的是一条路径，同一个字母只能在 1 组中访问。我的意思是，如果我已经访问了一个“A”组，然后又去了“B”组，我就不能再去另一个“A”组了。我可以这样旅行：

A->A->C->B->B

标签： algorithmdijkstra

Answer 1

约束

好的，我相信这两个约束如下：

1. 路径必须至少包含字母表中的每个字母一次，并且
2. 整个路径必须按字母顺序或反向字母顺序访问节点。

而且我相信字母表可以更大，例如AZ。

所以首先，让我们按字母顺序解决它。如果我们能做到这一点，那么我们只需要为逆字母顺序做等效的算法。

修正图

所以我们修改图表，使其具有以下规则：

• 每个节点 N 的出边只能连接到具有相同字母或紧随其后的字母的节点（例如，“A”节点只能将您发送到“A”节点或“B”节点，而不能连接到“C”节点，“D”节点等），否则我们可以按非字母顺序访问节点和/或跳过路径中的字母。
• 起始节点的出边只能连接到具有字母表第一个字母的节点（例如“A”节点），否则我们不能在整个字母路径中包含“A”。
• 末端节点的入边只能来自具有字母表最后一个字母的节点（例如，您的示例中的“B”节点），否则我们无法在整个字母路径中包含最后一个字母。

所以在上图中，我们只保留字母图的以下边：1 -> 3、3 -> 5、5 -> 7 和 7 -> 2。

同样，对于反向字母图，我们只保留以下边：1 -> 4, 4 -> 5, 5 -> 6, 5 -> 7, 6 -> 2。请注意，节点 7 将不再有任何出边.

完成此操作后，从开始到结束的任何路径（在修改后的图表中）都必须是有效路径，因为：

1. 路径必须至少包含字母表中的每个字母一次（没有跳过任何字母并且第一个节点是第一个字母并且最后一个节点是最后一个字母），并且
2. 整个路径按字母顺序访问节点（因为每个单独的边都是按字母顺序）。

鉴于此，常规 Dijkstra 应该在这个修改后的图表上完美运行。

最终框架

鉴于上述情况，您的整个算法如下：

1. 创建两个修改后的图表：一个按字母顺序排列，一个按字母顺序排列。
2. 在每个修改后的图上运行 Dijkstra。
3. 选择两者之间的最佳解决方案。