My problem is to find the shortest path between u and v which are nodes in a directed graph and the edges of the graph have weights.

I have tried using NetworkX, but it is too slow (average 50ms on a graph of 37202 nodes and 79264 edges).

igraph does not seem to provide an API for weighted shortest path.

Is there any other tools available?

Here's the code I'm using. (test_graph.txt is just the graph definition, and test_nodes.txt contains nodes for test)

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")

CodePudding user response：

You should try method get_shortest_paths of the igraph library. It has the weights parameter. You can find documentation here.

CodePudding user response：

As pointed out by @Oleksii , igraph can be used for my problem.

However, the official documentation is not very clear. I give a minimal example below as a reference for anyone who may have the same problem.

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]