我对经典的“最短路径”问题有一个变体，但我不知道如何解决它。我的图拓扑是这样的：
有一个源和一个汇。
其他节点由字母和下标整数指定（例如，A1,B1,C1,A2,B2,C2,....A30,B30,C30）。每个可能的字母/整数组合都有一个节点。
从源到 A1、B1、C1 中的每一个都有一个零成本有向边。从具有最大整数的每个节点到汇点都有一条零成本有向边（例如，当整数达到 30 时，从 A30 到“最终目标节点”有一条零成本有向边，并且B30 和 C30 的相同边）。
从每个节点有一个有向的加权边到另一个节点的每个其他字母具有更大的整数。
例如，可能存在从 A1 到 B3 和从 A1 到 C10 的有向加权边缘；但是，您不会看到从 A1 到 B3 和 B5 的边，因为目的地都是“B”边。没有边从一个带字母的节点移动到另一个带字母的节点（例如，没有 B3 到 B10），也没有边从具有较大整数的节点移动到具有较低整数的节点（例如，没有 B30至 C10)。
我知道我可以使用 Djikstra 的算法找到从起点到终点的奇异最短路径，但我的目标有些不同。我想要：
1）找到一条从源到接收器的最短路径，该路径访问每个“字母”一次且仅一次。只要我访问所有字母，任何整数组都可以工作。例如。访问source和sink之间的节点集A1、B22和C27是可以接受的；访问 A10、A15、B22 不是。2) 找到两条路径，它们组合起来访问每个字母一次且仅访问一次。如果“字母集”是 ABCDEF，则一条路线可以访问 ABD 和另一条 CEF；但我们不能让一条路线访问 ABCD 而另一条路线访问 DEF，因为 D 会重叠。目标是确定两条找到最短路径的路径——我并不关心总时间，而是关心这个极小值。3) 与 #2 相同的问题，但有 3 条路径、4 条路径等。
我假设我可以制作一个非常复杂的整数程序，但不知道是否有可用的最短路径算法来解决这个问题。如果它是现成的 R 包中的奖励积分。
拉尔夫