algorithm - 加权图算法

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 更快，但更简单的图更容易处理。