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)
Show older comments
Jorge Pesantez on 15 Sep 2016
Answered: Christine Tobler on 16 Sep 2016
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.
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);
0 1 Inf Inf
Inf 0 Inf Inf
Inf Inf 0 1
Inf Inf Inf 0
>> graphshortestpath(M, 1,'Method','Dijkstra')
0 1 Inf Inf
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!