Python 高效加权最短路径查找包

Question

我的问题是找到 u 和 v 之间的最短路径，它们是有向图中的节点并且图的边具有权重。

我试过使用 NetworkX，但速度太慢（在 37202 个节点和 79264 条边的图形上平均 50 毫秒）。

igraph 似乎没有为加权最短路径提供 API。

还有其他可用的工具吗？

这是我正在使用的代码。（test_graph.txt只是图定义，test_nodes.txt包含测试节点）

import networkx as nx
import random
from tqdm import tqdm
import time

G = nx.DiGraph()
with open("test_graph.txt") as f:
    for l in f:
        l = l.strip().split("\t")
        G.add_edge(int(l[0]), int(l[1]), length=float(l[2]))

nodes = [int(i) for i in open("test_nodes.txt")]
N = 1000
for _ in tqdm(range(N)):
    u, v = random.sample(nodes, 2)
    cnt = 0
    total = 0
    try:
        t = time.time()
        nx.shortest_path(G, u, v, weight="length")
        total += time.time() - t
        cnt += 1
    except nx.NetworkXNoPath:
        pass
print(f"{cnt/N*100:.2f} found, average {total/cnt:.6f}s")

Answer 1

您应该尝试 igraph 库的方法 get_shortest_paths。它有 weights 参数。您可以找到文档 here.

Answer 2

正如@Oleksii 所指出的，igraph 可用于解决我的问题。

不过官方文档不是很清楚。我在下面给出一个最小的例子作为可能有同样问题的人的参考。

import igraph

# define edges and their weights
edges=[(0,1),(1,2),(0,2)]
weights=[1,1,3]

# create directed graph
# use directed=False for undirected graph
G=igraph(edges, directed=True)

# set edge attributes
G.es['weight']=weights

# find shortest path from 0 to 2
# use predefined 'weight' attribute as weights
# the result is [[0,1],[1,2]]
path=G.get_shorted_paths(0,2,weights='weight')[0]

Python 高效加权最短路径查找包

Python package for efficient weighted shortest path finding

python

graph

python-3.x