get_shortest_paths
is not able to handle graphs with negative weights because the underlying C library does not have a corresponding igraph_get_shortest_paths_bellman_ford
function yet. It does have an igraph_get_shortest_paths_dijkstra
, so the Python interface simply checks whether you have weights and if so, redirects the call to igraph_get_shortest_paths_dijkstra
, otherwise it simply calls igraph_get_shortest_paths
(which is the unweighted version in the C layer). In contrast, shortest_paths
works with negative weights because the C library has a function named igraph_shortest_paths_bellman_ford
so it calls the Bellman-Ford implementation when at least one of the edge weights is negative.
Unfortunately the only way out seems to be to implement igraph_get_shortest_paths_bellman_ford
in the C layer and then update the Python interface to handle negative weights appropriately.
Answers to related questions:
igraph does not check whether the graph is a DAG before running any shortest path related function. Yes, shortest paths can be found faster in a DAG but this use-case is so rare that no one bothered to implement the special case so far.
Custom code written in pure Python is likely to be slower than a C implementation, but it depends on your problem. If you meant the Bellman-Ford algorithm in particular, a pure Python implementation is very likely to be slower, but it may still be usable for the graphs you have. You could try the implementation in NetworkX; as far as I know, NetworkX is pure Python and people still use it for graphs with tens of thousands of nodes and edges.