Python networkx 加权图在最短路径计算中没有考虑节点的权重？

Question

我正在使用 Python 3 和 Networkx 1.11。

我做了一个加权图，在边和一些节点上有权重，但是当我计算最短路径的权重时，没有考虑节点的权重（下面的代码）。

有人知道如何确保考虑节点权重吗？

谢谢！山姆

import networkx as nx
from matplotlib import pyplot as plt


# Set up a station map
all_stations = ['a','b','c','d','e']
interchange_stations = ['b']
routes = {'a':{'b':2}, 'c':{'b':2}, 'b':{'d':2}, 'd':{'e':2}}
print(routes)


# Make a network graph
G = nx.Graph()

# Add all the nodes (stations)
for station in all_stations:
    weight = 0
    if station in interchange_stations:
        weight = 5
    G.add_node(station, weight=weight)
print(G.nodes(data=True))


# Iterate through each line and add the time between stations  
for name1, value in routes.items():
    for name2, time in value.items():
        if name1 == name2:
            continue
        G.add_edge(name1, name2, weight=time)
print(G.edges(data=True))


# Work out the minimium distance between all stops
route_times = nx.all_pairs_dijkstra_path_length(G)

# Work out the minimum path between all stops
route = nx.all_pairs_dijkstra_path(G)

print(route['a']['e']) # Returns: ['a', 'b', 'd', 'e']
print(route_times['a']['e']) # Returns: 6 (should be 2+2+2+5)

Answer 1

在 documentation for dijkstra_path 中，我们有 dijkstra_path(G, source, target, weight='weight')，其中 weight 可以是两个节点和边的函数。这是提供的示例：

The weight function can be used to include node weights.

def func(u, v, d):
    node_u_wt = G.nodes[u].get('node_weight', 1)
    node_v_wt = G.nodes[v].get('node_weight', 1)
    edge_wt = d.get('weight', 1)
    return node_u_wt/2 + node_v_wt/2 + edge_wt

In this example we take the average of start and end node weights of an edge and add it to the weight of the edge.

这将包括每个中间节点的完整值和两个末端节点的一半。

您可以将函数修改为node_u_wt + edge_wt。然后路径将包括每条边的权重和作为路径中遇到的边的基础的每个节点的权重。（因此它将包括开始和每个中间节点的全部权重，但不包括最终节点）。

另一种解决方法是创建一个有向图 H，其中边 u 到 v 的边权重被指定为 u 的权重之和以及 G

中的边的权重

或者您可以使边的权重为 v 的权重与边的权重之和，只要您对包含基数还是目标数保持一致即可。因此，无论路径是在进入还是离开节点时添加的，路径都会受到惩罚。您可能需要注意路径的最终权重是否包括基节点或目标节点。

Python networkx 加权图在最短路径计算中没有考虑节点的权重？

Python networkx weighted graph not taking into account weight of node in shortest path calculation?

python

shortest-path

networkx

python-3.x

weighted-graph