加权图算法

Question

我有一个加权的有向图，有多条边从相同节点的结尾处开始。例如。从节点A到节点B的多条边。

要获得到某个节点的所有路径以及这些路径的相关成本，最佳搜索算法是什么？

Answer 1

因为您想要所有的路径，所以我将使用简单的广度优先搜索。但是，我也建议您将所有平行边折叠为具有权重列表的单个边。

一旦您获得了所有不同的路径(即，访问的节点都不同的所有路径)，您就可以为每条路径计算所有可能的替代并行路由。

因此，如果你有以下几条边：

A -> C  (5)
A -> C  (3)
A -> B  (7)
B -> C  (1)
B -> C  (4)

第一步是将其转换为：

A -> C (5,3)
A -> B (7)
B -> C (1,4)

对此图的广度优先搜索将产生A和B之间的以下路径：

A -> B (7)
A -> C -> B (5,3) + (1,4)

因此，对于第二条路径，您将获得以下开销：

5 + 1 
5 + 4
3 + 1
3 + 4

这本身不会比在原始图上执行BFS更快，但更简单的图更容易处理。

Answer 2

如果您必须输出每条路径的开销，那么没有什么比普通的DFS (或BFS)更好的了。由于该问题是输出敏感的，并且您可能只有O(E + V)路径，因此在大O表示法方面，您无法完成任何更好的工作。

Answer 3

如前所述，您可以使用深度优先搜索等进行强制/回溯。

不要期望为此找到任何捷径--如果你的图足够密集，可能会有很多路径，甚至仅仅是找出其中有多少路径就是#P-complete (即:不可处理)。

(如果您的问题不同-可能允许重复的节点，或者您只想找到最短路径或类似的东西，那么可能会有易于处理的解决方案)