创建一个networkx加权图，并找到权重最小的两个节点之间的路径

Question

我有一个关于图论的问题。为了解决这个问题，我想用networkx创建一个加权图。现在，我有一个字典，其中每个键都是一个节点，每个值都是相关的权重（大约在10到20万之间）。在

weights = {node: weight}

我相信我不需要用网络规范化权重。 现在，我通过添加边来创建一个非加权图：

^{pr2}$

从我读到的，我可以增加一个重量的边缘。但是，我希望权重应用于特定节点而不是边。我怎么能做到呢？在

想法：我通过添加加权节点来创建图，然后在节点之间添加边。在

^{3}$

这种方法正确吗？

下一步是寻找权重最小的两个节点之间的路径。我发现了这个函数：networkx.algorithms.shortest_paths.generic.shortest_path，我认为它做得对。但是，它使用边上的权重而不是节点上的权重。有人能给我解释一下这个函数的作用吗，在节点上的wieghts和在边上的权重对于networkx来说有什么区别，以及我如何实现我想要的？谢谢：）

Answer 1

这通常看起来是对的。在

您可以使用bidirectional_dijkstra。如果您知道路径的源节点和目标节点，则速度会显著加快（请参阅底部的注释）。在

要处理边与节点权重的问题，有两个选项。首先要注意的是，您要查找路径上节点的总和。如果我给每个边一个权重w(u,v) = w(u) + w(v)，那么这条边上的权重之和就是w(source) + w(target) + 2 sum(w(v))，其中节点{}是沿途找到的所有节点。任何具有这些边权重的最小权重都将具有节点权重的最小权重。在

所以你可以给每一条边指定两个节点的和的权重。在

for edge in G.edges():
    G.edges[edge]['weight'] = G.nodes[edge[0]]['weight'] + G.nodes[edge[1]]['weight']

但是另一种选择是注意到输入到bidirectional_dijkstra的权重可以是一个函数，它将边作为输入。定义两个节点的权重之和：

^{pr2}$

然后在你的电话里做bidirectional_dijkstra(G, source, target, weight=f)

所以我建议的选择是要么给每条边分配一个等于节点权重之和的权重，要么定义一个函数，只为算法遇到的边赋予这些权重。效率方面，我希望花更多的时间来找出哪个算法比编写两种算法都好。唯一的性能问题是分配所有权重将占用更多内存。假设内存不是问题，那么就用你认为最容易实现和维护的方法。在

---

关于双向dijkstra的一些评论：假设在空间中有两个点相距R，你想找到它们之间的最短距离。dijkstra算法（这是最短路径的默认值）将探索源点距离D内的每个点。基本上，这就像一个气球在第一个点的中心膨胀，直到到达另一个点。这有一个体积（4/3）πR^3。使用bidirectional_dijkstra我们将气球膨胀到每个气球的中心，直到它们接触为止。它们的半径都是R/2。所以体积是（4/3）pi（R/2）^3+（4/3）pi（R/2）^3，这是原始气球体积的四分之一，所以算法探索了四分之一的空间。由于网络可以具有非常高的有效维度，因此节省的成本通常要大得多。在