MATLAB: The command “graphallshortestpaths” gives me Inf value for a weighted indirect graph that I know it doesn’t have disconnections

adjacencygraph theorygraphallshortestpathjohnsonMATLABmatrixsparse matrix

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.

Thanks,

Best Answer

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.

Related Solutions

MATLAB: How to get the nodes/vertices traversed from graphallshortestpaths function

I understand that you want to get the shortest path to be traversed between two nodes. However, as the doc suggests, "graphallshortestpaths" would return only the distance matrix. However, you can use the "graphshortestpath" function to find the distance and shortest path. This function allows you to use different methods to calculate the path. Assuming you do not have any negative edges, it would not be much additional complexity to use the function between every pair of vertices to mimic "graphallshortestpaths". For more details, refer here .

MATLAB: Why the command of finding the all short paths for graph ( graphallshortestpaths ) give me wrong numbers

Your adjacency matrix represents a directed graph. It's possible to go directly from node 2 to node 3 since A(2, 3) is 1 but it is not possible to go directly from node 3 to node 2 since A(3, 2) is 0. The shortest path from 3 to 2 is in fact of length 4: 3 --> 4 --> 5 --> 1 --> 2. Using the graph algorithm functionality introduced into MATLAB in release R2015b:

 A=[1 1 0 0 1
   1 1 1 0 0
   0 0 0 1 0
   0 0 1 1 1
   1 0 0 0 0];
 D = digraph(A);
 shortestpath(D, 2, 3) % Returns [2 3]
 shortestpath(D, 3, 2) % Returns [3 4 5 1 2]
 plot(D) % If you follow the arrows, you have to go around the circle to get from 3 to 2

If you wanted all the edges to be two-way streets, your adjacency matrix would be A|A.'. When I create a graph using that adjacency matrix and ask for the shortest path I get what you're expecting.

 G = graph(A|A.');
 shortestpath(G, 2, 3)
 shortestpath(G, 3, 2)
 plot(G) % No arrows. There is an edge you can take in either direction between 2 and 3.

The DISTANCES function for the new graph algorithm functionality is the equivalent of GRAPHALLSHORTESTPATHS for a biograph. The output of DISTANCES for the digraph D agrees with the result you say is incorrect. The output of DISTANCES for the graph G almost agrees with your desired result, but the shortest path from 1 to 4 (and vice versa) is of length 2 not 3 [1 --> 5 --> 4] and the shortest path from 2 to 5 (and vice versa) is of length 2 not 1 [2 --> 1 --> 5.] These paths are easy to see in the plot of G.

Best Answer

Related Solutions

MATLAB: How to get the nodes/vertices traversed from graphallshortestpaths function

MATLAB: Why the command of finding the all short paths for graph ( graphallshortestpaths ) give me wrong numbers

Related Question