时间戳

首页 > 解决方案 > 如何使用 NetworkX 获得一组路由中两个节点之间的最短路径？

python - 如何使用 NetworkX 获得一组路由中两个节点之间的最短路径？

问题描述

我正在使用 NetworkX 图表来表示一组路线，如下图所示。

路线集

我知道 NetworkX 提供了 shortest_path() 来查找图中两个节点之间的最短路径，但考虑到我可用的一组路线，我想找到最短路径。从一条路线更改为另一条路线也会带来重量。

现在我正在使用不同的图表来表示每条路线，但我不确定这是最好的方法。

例如：节点 3 和 2 之间的最短路径可能是仅使用一条路由[3, 5, 2]或使用两条路由[3, 1]，并且[1, 2]它们之间存在成本。

是否可以使用 NetworkX 来实现这一点shortest_path？

标签： pythonnetworkx

解决方案

按照您拥有多个图的想法，我将创建一个大图，其中包含每个图的副本，但还包括您拥有的图的相应节点之间的边。因此，对于每种边缘颜色，都有一个包含所有这些边缘的图，并且对于原始图中的每个节点，其所有副本之间都有边缘，并伴随着一些成本。现在我们将寻找通过这个更大网络的路径。从代码有点不干净的意义上说，它并不完美，但它会起作用。

import networkx as nx

nodes = [0,1,2,3,4, 5, 10, 11]
rednodes = ['r{}'.format(node) for node in nodes]   #['r0', 'r1', ...]
rededges = [('r0', 'r1'), ('r1', 'r4'), ('r4', 'r3'), ('r3', 'r5'), ('r5', 'r2')]
bluenodes = ['b{}'.format(node) for node in nodes]  
blueedges = [('b1', 'b2')]
orangenodes = ['o{}'.format(node) for node in nodes]
orangeedges = [('o1', 'o3'), ('o3', 'o11'), ('o11', 'o10')]

G = nx.Graph()
G.add_nodes_from(rednodes+bluenodes+orangenodes)

G.add_edges_from(rededges + blueedges + orangeedges, weight = 1)

#here we add edges between the copies of each node
rb_edges = [('r{}'.format(node), 'b{}'.format(node)) for node in nodes] 
ro_edges = [('r{}'.format(node), 'o{}'.format(node)) for node in nodes]
bo_edges = [('b{}'.format(node), 'o{}'.format(node)) for node in nodes]

G.add_edges_from(rb_edges+ro_edges+bo_edges, weight = 0.2)

#This next step is a bit of a hack.
#we want a short path from 0 to 11, but I can't be sure which of the colors I should 
#start in.  So I create a new 0 and 11 node, which connect to its copies with 0 cost.

temporary_edges = [(0, '{}0'.format(c)) for c in ['r', 'b', 'o']] + [(11, '{}11'.format(c)) for c in ['r', 'b', 'o']]
G.add_edges_from(temporary_edges, weight = 0)
best_option = nx.shortest_path(G, 0, 11, weight = 'weight')
G.remove_edges_from(temporary_edges)      #get rid of those edges
G.remove_nodes_from([0, 11])


print(best_option)
> [0, 'r0', 'r1', 'o1', 'o3', 'o11', 11]

推荐阅读