在NetworkX中查找所有节点对之间的最短路径

Question

我正在尝试获取无向无权图中所有节点对之间的最短路径。我目前使用的是nx.all_pairs_shortest_path()，但我不明白为什么它只返回每对节点之间的一条最短路径。我的图中存在循环，因此某些节点之间应该存在多条最短路径。有什么建议吗？

- Shaun Han

---

因为这个函数的作用就是找到每对节点之间的最短路径，所以它只返回一条最短路径。 - Stef

此外，这里可能不是这种情况，但在图中可能存在一个循环，但每对节点之间可能没有多于一条的最短路径。例如，任何具有奇数个节点的循环图都将对每对节点具有唯一的最短路径。 - Stef

Answer 1

遍历图中的所有节点:

results = []
for n1 in G.nodes():
    for n2 in G.nodes():
        shortest_path = nx.single_source_dijkstra(G, source=n1, target=n2, weight=f)
        results.append(shortest_path)
        

- AveragePythonEnjoyer

Answer 2

我可能有点晚，但我刚遇到了同样的问题，这是我的解决方案：

 def all_shortest_paths(G):
    a = list(nx.all_pairs_shortest_path(G))
    all_sp_list = []
    for n in range(len(G.nodes)):
      a1 = a[n][1]
      for k,v in a1.items():
        all_sp_list.append(len(v))
    return all_sp_list

我尝试了其他的方法，但由于我的图有很多节点，所以速度变得非常慢，因此这是我最快的解决方案。

- Igor Michetti

---

在我的情况下，我只需要最短路径长度来绘制直方图。如果你想要最短路径数据，你就需要调整代码。 - Igor Michetti

Answer 3

我自己遇到了这个问题，并在寻找解决方案的过程中来到了这里。不幸的是，networkx没有计算每对节点之间所有最短路径的函数。此外，Igor Michetti的答案并没有给出我想要的结果，但可能可以进行微调。math_noob的答案很好，因为它足够接近我制定解决方案，但问题是它太慢了。

def single_source_shortest_paths(graph,source):
    shortest_paths_dict = {}
    for node in graph:
        shortest_paths_dict[node] = list(nx.all_shortest_paths(graph,source,node))
    return shortest_paths_dict

def all_shortest_paths(graph):
    for source in graph:
        yield source, single_source_shortest_paths(source)

所以我回到networkx文档并尝试最后一次查找是否有任何可用的函数。但是没有，所以我决定自己实现它。所以我首先尝试手动实现所有内容，这有点混乱，只意识到它变得更好了，但不是那么多，所以我决定尝试查看源代码，并发现了一个圣杯，即nx.predecessor函数。

此函数仅对图形和源节点调用，因此它不依赖于目标节点，而且它是做大部分艰苦工作的函数。因此，我只需通过每个源节点调用一次nx.predecessor来重新创建函数single_source_shortest_paths，然后执行与all_shortest_path相同的操作，该操作仅包括使用正确的参数调用另一个函数。

def single_source_shortest_paths_pred(graph,source):
    shortest_paths_dict = {}
    pred = nx.predecessor(graph,source)
    for node in graph:
        shortest_paths_dict[node] = list(nx.algorithms.shortest_paths.generic._build_paths_from_predecessors([source], node, pred))
    return shortest_paths_dict

从时间方面来看，nx.predecessor 占用了大部分执行时间，因此第二个函数的速度约为图中节点数的 n 倍。

- ajreckof

Answer 4

下面的工作代码返回一个字典。键是（源，目标）元组，用于快速查找，值是（最小距离，路径）元组。

import pandas as pd  # dataframes
import networkx as nx  # networks a.k.a graphs
from pprint import pprint  # prettty print


def new_pandas_edgelist():
    return pd.DataFrame(
        {
            "source": ["A", "A", "B", "C"],
            "target": ["B", "C", "D", "D"],
            "distance": [10, 20, 30, 40],
        }
    )


def new_graph(df: pd.DataFrame) -> nx.classes.graph.Graph:
    G = nx.from_pandas_edgelist(df, edge_attr=["distance"], create_using=nx.Graph)
    return G


def every_shortest_path(G):
    return {(src, tgt): a_shortest_path(G, src, tgt) for src in G for tgt in G}


def a_shortest_path(G, source, target, weight="distance"):
    return nx.single_source_dijkstra(G, source, target, weight=weight)


if __name__ == "__main__":
    df_edges = new_pandas_edgelist()
    G = new_graph(df_edges)
    print("")
    print("every shortest path...")
    pprint(every_shortest_path(G))

# every shortest path...
# {('A', 'A'): (0, ['A']),
#  ('A', 'B'): (10, ['A', 'B']),
#  ('A', 'C'): (20, ['A', 'C']),
#  ('A', 'D'): (40, ['A', 'B', 'D']),
#  ('B', 'A'): (10, ['B', 'A']),
#  ('B', 'B'): (0, ['B']),
#  ('B', 'C'): (30, ['B', 'A', 'C']),
#  ('B', 'D'): (30, ['B', 'D']),
#  ('C', 'A'): (20, ['C', 'A']),
#  ('C', 'B'): (30, ['C', 'A', 'B']),
#  ('C', 'C'): (0, ['C']),
#  ('C', 'D'): (40, ['C', 'D']),
#  ('D', 'A'): (40, ['D', 'B', 'A']),
#  ('D', 'B'): (30, ['D', 'B']),
#  ('D', 'C'): (40, ['D', 'C']),
#  ('D', 'D'): (0, ['D'])}

- Tim Madden

---

根据目前的写法，你的答案不清楚。请编辑以添加更多细节，帮助其他人理解它如何回答所提出的问题。你可以在帮助中心找到关于如何撰写好答案的更多信息。 - Community