Why the command "graphallshortestpaths" gives me Inf value for a weighted indirect graph that I know it doesn't have disconnections?

1 view (last 30 days)
I am trying to get the shortest path of all the nodes of a network for a weighted non-negative sparse matrix. When I use "graphallshortestpath", I get some "Inf" values that indicates there is no path between 2 nodes. I tried the same graph with a dense matrix and used Dijkstra's algorithm and I had no "Inf" values at all. So, I don't know why "graphallshortestpath" built in function -that is much more faster because works with sparse matrix- is giving me "Inf" values.
Any ideas, please.
  1 Comment
Christine Tobler
Christine Tobler on 16 Sep 2016
Could you post an example of the graph you are using? I tried an example and I don't see this happening for that case:
>> M = sparse([1 3], [2 4], 1, 4, 4);
>> graphallshortestpaths(M)
ans =
0 1 Inf Inf
Inf 0 Inf Inf
Inf Inf 0 1
Inf Inf Inf 0
>> graphshortestpath(M, 1,'Method','Dijkstra')
ans =
0 1 Inf Inf

Sign in to comment.

Accepted Answer

Christine Tobler
Christine Tobler on 16 Sep 2016
I'm not sure what function you are using to compute Dijkstra with a dense matrix - graphshortestpath for a dense matrix returns an error for me.
I would assume that the problem is that when a graph is represented as a sparse matrix, the assumption is that all zeros stand for edges that do not exist. But when you use a dense matrix, the algorithm might be interpreting every zero entry as an edge with length zero - so every node would be reachable from every other node.

More Answers (0)


Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!