Существует ли функция графика, которая дает все самые короткие пути для взвешенных неистовых графиков? ⇐ Python

[Anonymous]

Я работаю с взвешенным неориентированным графом в graph_tool и хотел бы найти все кратчайшие пути между двумя узлами. Первоначально я пытался передавать dist_map all_shortest_paths () , но после более тщательного прочтения документации я понял, что этот подход не работает, как я ожидал. Я чувствую, что, возможно, упускаю что -то очевидное. Вот пример: < /p>
import graph_tool.all as gt

g = gt.Graph({0: [1,2], 1:[4], 2:[3],3:[4]}, directed=False)
edge_weights = g.new_edge_property("float", 0)
edge_weights[g.edge(0,1)] = 20

source_node = g.vertex(0)
target_node = g.vertex(4)

full_dist_map = gt.shortest_distance(g, source=source_node, weights=edge_weights)

print("\nFinding all shortest weighted paths using all_shortest_paths:")
weighted_shortest_paths_generator = gt.all_shortest_paths(g, source=source_node, target=target_node, dist_map=full_dist_map)
for path in weighted_shortest_paths_generator:
print(path) # Would like to have [0, 2, 3, 4]

print("\nFinding one shortest weighted path using shortest_path:")
path_vertices, _ = gt.shortest_path(g, source=source_node, target=target_node, weights=edge_weights)
print([int(v) for v in path_vertices]) # Should print [0, 2, 3, 4]
< /code>
output: < /p>
Finding all shortest weighted paths using all_shortest_paths:
[0 1 4]

Finding one shortest weighted path using shortest_path:
[0, 2, 3, 4]


Подробнее здесь: https://stackoverflow.com/questions/795 ... eighted-un