グラフ内のすべてのペアの間の最短パスを計算します。これを達成するために、グラフのすべてのノードペアに対してgraph_toolのall_shortest_paths関数を使用しています。ドキュメンテーションによれば、この関数は与えられた場合にエッジウェイトを尊重することができます。一見、これはうまく動作します。しかし、返された最短パスのリストは不完全であることがわかりました。それは一見最短経路だけを含み、最短経路の完全なセットからの最小量のホップも使用する。ここpython graph_tool：_all_最短パスを取得
が小さい例である：
import graph_tool
import graph_tool.topology
#setup graph
g = graph_tool.Graph()
g.add_vertex(5)
edges = [(0,1),(1,2),(3,2),(0,4),(4,3)]
metrics = [3, 4, 2, 1, 3]
g.edge_properties["metric"] = g.new_edge_property("int")
for i in range(len(metrics)):
e = g.add_edge(*(edges[i]))
g.edge_properties["metric"][e] = metrics[i]
#compute all shortest paths from 0 to 2
paths = graph_tool.topology.all_shortest_paths(g, 0, 2, weights=g.edge_properties["metric"])
for path in paths:
print(path)
print("-"*10)
#increase metric of edge 0-4
g.edge_properties["metric"][g.edge(0,4)] = 2
#recompute all shortest paths from 0 to 2
paths = graph_tool.topology.all_shortest_paths(g, 0, 2, weights=g.edge_properties["metric"])
for path in paths:
print(path)
それはとてもように頂点2に頂点0から2つの経路を形成する5つの頂点と辺を有するグラフ生成：
明らか0 --- 1 --- 2
\ /
\ /
4 --- 3
を、パス[0、1、2]はホップ数の点で[0,4,3,2]よりも短い。メトリックが与えられていない場合、これは正しく認識されます（ここでは説明しません）。
例の冒頭では、エッジがより多くのホップを持つ2番目のパスが「より短い」ような方法で重み付けされています。メトリックの合計は6ですが、もう一方のパスの合計値は7です。したがって、アルゴリズムは[0、4、3、2]を正しく返します。
次に、0と4の間のエッジのメトリックが1増加します。両方のパスが同じ合計値を持ち、両方が返される必要があります。ただし、アルゴリズムは[0、1、2]のみを返します。私は、メトリックを指定したとしても、ホップカウントはまだ何らかの要因を考慮していると仮定することができます。このため、2番目のパスは無視されます。私が見た限りでは、公式文書にこのような動作の言及はありません。
私は何か見落としていますか？おそらく別のライブラリであっても、これを行うための優れた機能はありますか？代わりに、すでにigraphを調べましたが、ノードペアごとに1つの最短パスしか計算できないように見えます。