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

Question

我有一个涉及图论的问题。为了解决这个问题，我想使用 networkx 创建一个加权图。目前，我有一个字典，其中每个键都是一个节点，每个值都是关联的权重（在 10 到 200 000 左右之间）。

weights = {node: weight}

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

def create_graph(data):
    edges = create_edges(data)

    # Create the graph
    G = nx.Graph()

    # Add edges
    G.add_edges_from(edges)

    return G

根据我的阅读，我可以为边缘添加权重。但是，我更喜欢将权重应用于特定节点而不是边缘。我该怎么做？

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

def create_graph(data, weights):
    nodes = create_nodes(data)
    edges = create_edges(data) # list of tuples

    # Create the graph
    G = nx.Graph()

    # Add edges
    for node in nodes:
        G.add_node(node, weight=weights[node])

    # Add edges
    G.add_edges_from(edges)

    return G

这个方法正确吗？

下一步是找到权重最小的2个节点之间的路径。我找到了这个函数：networkx.algorithms.shortest_paths.generic.shortest_path，我认为这是正确的做法。但是，它使用边上的权重而不是节点上的权重。有人可以解释一下这个函数的作用，节点上的权重和边缘上的权重之间的区别是什么 networkx，以及我如何实现我正在寻找的东西？谢谢:)

Answer 1

这通常看起来是正确的。

您可能会使用 bidirectional_dijkstra。如果您知道路径的源节点和目标节点（请参阅底部的评论），速度会明显加快。

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

因此，您可以将权重分配给每条边，使其成为两个节点的总和。

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

但另一种方法是注意输入到bidirectional_dijkstra中的权重可以是一个以边为输入的函数。定义自己的函数，给出两个节点权重之和：

def f(edge):
    u,v = edge
    return G.nodes[u]['weight'] + G.nodes[v]['weight']

然后在您的通话中执行 bidirectional_dijkstra(G, source, target, weight=f)

所以我建议的选择是为每条边分配一个等于节点权重总和的权重，或者定义一个函数，只为算法遇到的边提供这些权重。在效率方面，我预计比编写任何一种算法都需要更多时间来找出哪个更好。唯一的性能问题是分配所有权重将使用更多内存。假设内存不是问题，请使用您认为最容易实现和维护的那个。

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

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

Create a networkx weighted graph and find the path between 2 nodes with the smallest weight

python

graph-theory

networkx