0

我想在加权图中计算 Dijkstra 的最短路径以计算weights的平均值。我没有在网上找到任何有用的东西，所以请帮助我，因为我认为这不仅对我有用。

我有一个字典列表：

list_of_dictionaries=  [
    {"RA":"1","RB":"2","SPEED":"100"}
    ...
    {"RA":"1","RB":"8250","SPEED":"150"}
    {"RA":"2","RB":"3","SPEED":"120"}
    ...
    {"RA":"2","RB":"8250","SPEED":"150"}
    ...
    ...
    {"RA":"350","RB":"351","SPEED":"130"}
    ...
    ...        
]

我创建了一个加权无向图，然后使用 Dijkstra 最短路径来计算平均速度（而不是总速度）。开始吧：

import networkx as nx
graph = nx.Graph()
for row in list_of_dictionaries:
     source = row['RA']
     target = row['RB']
     if not graph.has_node(source):
        graph.add_node(source)
     if not graph.has_node(target):
        graph.add_node(target)
     graph.add_edge(source, target, speed=float(row['SPEED']))

我检查了图表是否已连接，它是！现在我首先得到包含节点列表（不是边）的路径，然后我一次取两个节点，我在图中检查用两个节点创建的边的权重（速度） 。我对路径中的所有节点重复此过程，然后计算平均速度。

这当然非常耗时且效率低下

tot_speed = 0.0
path = nx.dijkstra_path(graph, source, target, 'speed')

for k, node in enumerate(path[:-1]):
    n1 = path[k]
    n2 = path[k + 1]
    speed = graph[n1][n2]['speed']
    tot_speed += speed
avg_speed = tot_speed / len(path)-1

如您所见，这不是一个好方法，主要有两个问题：

1）如果我尝试nx.dijkstra_path(graph, 1, 1, 'speed')我会遇到麻烦，因为 avg_speed 公式中的分母为零。

2）for循环真的很乱

如果你有更好的想法，请告诉我你的观点。谢谢。

4

0 回答 0