は、3つの項目のマップのための最良のデータ構造は何である

Question

レッツ・sayIi持って与えられた値（起源、運命、距離）：

A ~ B = 5 
B ~ C = 10 
A ~ C = 20 

そして私はCへの最短の道を見つけたい（中この場合A→B、B→C）。

これらの値を保存/検索するのに最適なデータ構造は何ですか？

Answer 1

networkxを使用して重み付きグラフを表し、 dijkstra_pathを使用して最短経路を見つけることができます。

例：

#!/usr/bin/env python 

import networkx as nx 

G=nx.Graph() 

G.add_edge('a','b',weight=5) 
G.add_edge('b','c',weight=10) 
G.add_edge('a','c',weight=20) 

print(nx.dijkstra_path(G,'a','c')) 

これは出力として与える：

['a', 'b', 'c']

を私はdijkstraアルゴリズムは、すべての人に頂点からの最短経路問題のための最善の方法だと思いますし、複雑さの項に関しては、O（nlogn）であり、nは頂点の数である。

もちろん、最短経路アルゴリズムは、負の円がない場合（最短経路問題が意味を持たない場合）にのみ機能します。