带有标记边的图中的最短路径
Shortest paths in graph with labeled edges
问题
假设我有一个带有标记节点和边的图形(见图)。我的目标是得到A和D之间所有最短路径的set。
到目前为止我有什么
import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'D')
G.add_edge('B', 'C')
shortest_path = nx.shortest_path(G, 'A', 'D')
在 shortest_path
我得到 ['A', 'B', 'D']
。当然,这个是通过节点表示的最短路径,但是我需要的是:
1) 在我的图中添加边标签
2) 找到所有可能的最短路径的集合。理想情况下,在 shortest_paths
中我希望输出如下:
[ A -> a -> B, B -> b -> D], [A -> a -> B, B -> c -> D]
问题
1) 这可以用 networkx 完成吗?
2) 如果不是,还有哪些其他图形库包含解决此类问题的函数(不一定是 Python)?
您可以将边转换为节点并使用函数 all_shortest_paths()
:
import networkx as nx
G = nx.MultiGraph()
G.add_edge('A', 'B', label='a')
G.add_edge('B', 'D', label='b')
G.add_edge('B', 'D', label='c')
G.add_edge('B', 'C', label='d')
G.add_edge('C', 'D', label='e')
# Convert edges to nodes
g = nx.Graph()
for i, j, label in G.edges(data='label'):
g.add_edge(i, label)
g.add_edge(j, label)
print(list(nx.all_shortest_paths(g, 'A', 'D')))
# [['A', 'a', 'B', 'b', 'D'], ['A', 'a', 'B', 'c', 'D']]
问题
假设我有一个带有标记节点和边的图形(见图)。我的目标是得到A和D之间所有最短路径的set。
到目前为止我有什么
import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'D')
G.add_edge('B', 'C')
shortest_path = nx.shortest_path(G, 'A', 'D')
在 shortest_path
我得到 ['A', 'B', 'D']
。当然,这个是通过节点表示的最短路径,但是我需要的是:
1) 在我的图中添加边标签
2) 找到所有可能的最短路径的集合。理想情况下,在 shortest_paths
中我希望输出如下:
[ A -> a -> B, B -> b -> D], [A -> a -> B, B -> c -> D]
问题
1) 这可以用 networkx 完成吗?
2) 如果不是,还有哪些其他图形库包含解决此类问题的函数(不一定是 Python)?
您可以将边转换为节点并使用函数 all_shortest_paths()
:
import networkx as nx
G = nx.MultiGraph()
G.add_edge('A', 'B', label='a')
G.add_edge('B', 'D', label='b')
G.add_edge('B', 'D', label='c')
G.add_edge('B', 'C', label='d')
G.add_edge('C', 'D', label='e')
# Convert edges to nodes
g = nx.Graph()
for i, j, label in G.edges(data='label'):
g.add_edge(i, label)
g.add_edge(j, label)
print(list(nx.all_shortest_paths(g, 'A', 'D')))
# [['A', 'a', 'B', 'b', 'D'], ['A', 'a', 'B', 'c', 'D']]