我可以使用什么算法来查找图中指定节点类型之间的最短路径？

Question

这就是问题：

我有 n 个点（p1、p2、p3、.. pn），每个点都可以以确定的成本 x 连接到任何其他点。

每个点都属于一组点类型中的一个（例如“A”“B”“C”“D”...）。

该方法的输入是我想要遵循的路径，例如“ABCADB”。

输出是连接我在输入中给出的类型的点的最短路径，例如“p1-p4-p32-p83-p43-p12”，其中p1是A型，p4是B型，p32是C型型，p83 为 A 型，p43 为 D 型，p12 为 B 型。

“简单”的解决方案包括计算所有可能的路径，但计算成本非常高！

有人能找到更好的算法吗？

正如我在标题中所说，我不知道它是否存在！

更新：

阻止我使用 Dijkstra 和其他类似算法的关键点是我必须根据类型链接点。

作为输入，我有一个类型数组，我必须按该顺序链接。

这是肯特·弗雷德里克（Kent Fredric）的图像（非常感谢），它描述了初始情况（红色允许链接）！

一个现实生活中的例子：

一个人想早上参观教堂，去餐馆，最后下午参观博物馆。

地图上有 6 座教堂、30 家餐厅和 4 家博物馆。

他希望教堂-休息区-博物馆的距离尽可能小。

Answer 1

有许多算法比计算所有可能的路径做得更好。 广度优先搜索是我想到的算法系列的基本起点， 最佳优先搜索 是合适的，因为您已经定义了顶点成本，并且如果可以的话要获取有关您的问题空间的更多信息，您可以使用 A* 或 Dijkstra 算法。 （在每种情况下，从允许的起始节点集中查找路径。）

重新编辑：您的路径约束（需要满足的节点类型数组）不会阻止您使用这些算法；您可以使用这些算法。 恰恰相反，它可以帮助他们更好地工作。 您只需要以允许合并路径约束的方式实现它们，将搜索中每个步骤可用的顶点限制为给定约束的有效顶点。

Answer 2

这就是我目前解释您的问题的方式。

红色箭头是我手动跟踪符合给定排序约束的路径。

未提供成本，但假设所有链路都会产生成本，并且链路成本不同。

如果这准确地描述了您要解决的场景，请这么说，以便其他人可以更好地回答问题。

Answer 3

在修改您的问题时，您似乎要求每个字母一个节点 - 在这种情况下，这是一个简单的动态编程解决方案：计算每对节点之间满足序列开头的所有长度为 1 的最短路径。 然后，对于所有节点对来说，拥有 k 个所有此类路径，那么构造 k+1 就很简单了。

Answer 4

这是动态编程解决方案的伪代码：

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

您的最小成本路径是 min(d[n][0..m])

您可以将 d 表的大小减少到 2 行，但这会混淆解决方案

Answer 5

据我了解你的问题，你需要有向图中的最短路径。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 应该给你一个主意。

问候，简

Answer 6

1. 计算每个等价块内的所有最短路径对。
2. 现在构建一个没有类间边的图，但类之间的边与该类内的最短路径匹配，通向另一个类的特定节点。

希望这一点是清楚的。

这个解决方案不是特别有效，但显然是多项式的。

Answer 7

您可以使用 Floyd–Warshall 算法。 这是维基百科给出的伪代码：

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

我必须为关于同一问题的算法课程编写一个程序。 这个算法很有魅力！ 祝你好运。

Answer 8

正如 Jan 提到的，你只需要一个普通的无聊最短路径算法（比如 Dijkstra 的或 Floyd 的算法）； 但是，您需要转换输入图，以便输出路径遵循您的路径约束。

给定路径约束：A - B - A

创建一个新图 G 并使用新标签将 A 中的所有顶点插入到 G 中像a_01。 然后将 B 中的所有顶点插入到 G 中，并将 A 顶点与 B 顶点连接起来（边应该是指向新插入的节点）从原始图中复制成本。 然后，您可以使用 A（以及任何其他路径组件）重复此步骤，将新插入的顶点连接到 B 中的顶点。 因此，您创建一个图形，其中只有存在的路径满足路径约束。 然后您可以使用普通的最短路径算法。

关键的见解是，当您重新访问一个类时，您实际上正在访问一组不同的节点，并且您只需要连接相邻节点类的边。