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 的权重与边的权重之和，只要您对于包含基数还是目标数保持一致即可。因此，无论它是在进入还是离开节点时添加，路径都会受到该惩罚。您可能需要稍微注意路径的最终权重是否包括基本节点或目标节点。