具有路径的自定义成本函数的 Networkx

Question

我有如下所示的情况，其中有一个加权图。

我正在尝试根据自定义函数获取从 A 到 D 的最佳路径，总成本是先前成本的乘积。

A - B - D = 0.6 * 30 = 18
A - C - D = 0.3 * 40 = 12

我想选择第二条路（成本较低）。

如何使用 networkx 库执行此操作？

谢谢

Answer 1

一种方法是遍历所有路径，select 使用自定义函数选择最佳路径。这是粗略的（伪）代码：

from networkx import all_simple_paths


paths = all_simple_paths(G, source, target)
costs = []
for p in paths:
    # obtain the edge weights and evaluate the cost using custom function
    cost = custom_function(p)
    costs.append((cost, p))

# sort the costs and pick the one with the smallest cost
lowest_cost, best_path = sorted(costs)[0]

具有路径的自定义成本函数的 Networkx

Networkx with custom cost function for path

python

graph

networkx