我希望计算图中所有节点对之间的最短路径。为了实现这一目标，我正在使用graph_tool的all_shortest_paths函数来计算图中每个节点对之间的最短路径。根据文档，如果给定权重，该函数能够考虑边缘权重。乍一看，这似乎很好用。然而，我发现返回的最短路径列表不完整。它似乎只包括最短路径中跳数最少的路径。
它生成一个包含5个顶点和边的图形，形成了2条从顶点0到顶点2的路径，如下所示：
显然，从跳数的角度来看，路径[0,1,2]比[0,4,3,2]更短。如果没有给出度量标准，则可以正确识别（此处未演示）。
在示例的开头，边缘以这样的方式加权，即具有更多跳数的第二个路径“更短”。指标的总和为6，而另一条路径的总值为7。因此，算法正确返回[0,4,3,2]。
然后，将0和4之间的边缘度量增加1。现在两条路径的总值相同，应该都被返回。然而，算法仅返回[0,1,2]。我只能假设跳数仍然以某种方式被考虑在内，尽管我指定了度量标准，这就是为什么忽略了第二个路径的原因。据我所见，官方文档中没有提到这种行为。
我是否忽略了什么？也许有更好的函数可以做到这一点，甚至使用不同的库？我已经研究了igraph作为替代方案，但似乎只能计算每对节点的一个最短路径。
以下是一个小例子:
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)
它生成一个包含5个顶点和边的图形，形成了2条从顶点0到顶点2的路径，如下所示：
0 --- 1 --- 2
\ /
\ /
4 --- 3
显然，从跳数的角度来看，路径[0,1,2]比[0,4,3,2]更短。如果没有给出度量标准，则可以正确识别（此处未演示）。
在示例的开头，边缘以这样的方式加权，即具有更多跳数的第二个路径“更短”。指标的总和为6，而另一条路径的总值为7。因此，算法正确返回[0,4,3,2]。
然后，将0和4之间的边缘度量增加1。现在两条路径的总值相同，应该都被返回。然而，算法仅返回[0,1,2]。我只能假设跳数仍然以某种方式被考虑在内，尽管我指定了度量标准，这就是为什么忽略了第二个路径的原因。据我所见，官方文档中没有提到这种行为。
我是否忽略了什么？也许有更好的函数可以做到这一点，甚至使用不同的库？我已经研究了igraph作为替代方案，但似乎只能计算每对节点的一个最短路径。