我有一個不同位置的圖表：
import networkx as nx
G = nx.Graph()
for edge in Edge.objects.all():
G.add_edge(edge.from_location, edge.to_location, weight=edge.distance)
位置(節點)有不同的型別(廁所,建筑物入口等)我需要找到從某個給定位置到特定型別的任何位置的最短路徑. (例如：從給定節點查找最近的入口.)
在沒有回圈的情況下,Networkx庫中是否有一些方法可以解決這個問題？就像是：
nx.shortest_path(
G,
source=start_location,
target=[first_location, second_location],
weight='weight'
)
如果兩個位置屬于同一型別,則結果將是first_location或second_location的最短路徑.
是否有一些方法也回傳路徑長度？
uj5u.com熱心網友回復：
我們將分三步完成.>第1步：讓我們創建一個虛擬圖來說明>步驟2：繪制圖形和顏色節點以指示邊長和特殊節點型別(廁所,入口等)>步驟3：從任何給定節點(源)計算到所有可到達節點的最短路徑,然后子集到感興趣的節點型別并選擇具有最小長度的路徑.
下面的代碼肯定可以優化,但這可能更容易理解.
第1步：創建圖表
edge_objects = [(1,2, 0.4), (1, 3, 1.7), (2, 4, 1.2), (3, 4, 0.3), (4 , 5, 1.9),
(4 ,6, 0.6), (1,7, 0.4), (3,5, 1.7), (2, 6, 1.2), (6, 7, 0.3),
(6, 8, 1.9), (8,9, 0.6)]
toilets = [5,9] # Mark two nodes (5 & 9) to be toilets
entrances = [2,7] # Mark two nodes (2 & 7) to be Entrances
common_nodes = [1,3,4,6,8] #all the other nodes
node_types = [(9, 'toilet'), (5, 'toilet'),
(7, 'entrance'), (2, 'entrance')]
#create the networkx Graph with node types and specifying edge distances
G = nx.Graph()
for n,typ in node_types:
G.add_node(n, type=typ) #add each node to the graph
for from_loc, to_loc, dist in edge_objects:
G.add_edge(from_loc, to_loc, distance=dist) #add all the edges
第2步：繪制圖表
#Draw the graph (optional step)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
edge_labels = nx.get_edge_attributes(G,'distance')
nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels)
nx.draw_networkx_nodes(G, pos, nodelist=toilets, node_color='b')
nx.draw_networkx_nodes(G, pos, nodelist=entrances, node_color='g')
nx.draw_networkx_nodes(G, pos, nodelist=common_nodes, node_color='r')
plt.show()
步驟3：創建小函式以找到節點型別的最短路徑
def subset_typeofnode(G, typestr):
'''return those nodes in graph G that match type = typestr.'''
return [name for name, d in G.nodes(data=https://bbs.csdn.net/topics/True)
if 'type' in d and (d['type'] ==typestr)]
#All computations happen in this function
def find_nearest(typeofnode, fromnode):
#Calculate the length of paths from fromnode to all other nodes
lengths=nx.single_source_dijkstra_path_length(G, fromnode, weight='distance')
paths = nx.single_source_dijkstra_path(G, fromnode)
#We are only interested in a particular type of node
subnodes = subset_typeofnode(G, typeofnode)
subdict = {k: v for k, v in lengths.items() if k in subnodes}
#return the smallest of all lengths to get to typeofnode
if subdict: #dict of shortest paths to all entrances/toilets
nearest = min(subdict, key=subdict.get) #shortest value among all the keys
return(nearest, subdict[nearest], paths[nearest])
else: #not found, no path from source to typeofnode
return(None, None, None)
測驗：
find_nearest('entrance', fromnode=5)
生產：
(7, 2.8, [5, 4, 6, 7])
含義：距離5最近的“入口”節點為7,路徑長度為2.8,完整路徑為：[5,4,6,7].希望這有助于您前進.請問是否有任何不清楚的地方.
uj5u.com熱心網友回復：
上面的答主是計算的網路內部的最近點，樓主請問最后怎么解決的，如果有大量的點應該怎么解決啊，望請相告轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/87870.html
標籤：其他技術討論專區
上一篇：為什么我maxcapacity出現了兩行?怎么看，求助！
下一篇：滿分單詞