1

我正在使用 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)
4

1 回答 1

3

在dijkstra_path 的文档中，我们知道dijkstra_path(G, source, target, weight='weight')whereweight可能是两个节点和边的函数。这是提供的示例：

权重函数可用于包含节点权重。

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

在这个例子中，我们取边的开始和结束节点权重的平均值，并将其添加到边的权重中。

这将包括每个中间节点的全部值和两个端节点的一半。

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

另一种解决方法是创建一个有向图H，其中边utov的边权重u为G

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

于 2018-03-06T19:45:07.273 回答