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

all pathsall short pathsBioinformatics Toolboxerrorsparse matrix

Dear,
I'm trying to find all short paths between vertices so I used graphallshortestpaths,
but for my matrix
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];
I got error for using the command
graphallshortestpaths(A)
Error using graphalgs
Input argument should be a sparse array.
Error in graphallshortestpaths (line 85)
    dist = graphalgs('all',debug_level,directed,G);
Error in FitnessDiameter (line 92)
p=graphallshortestpaths(A)
so I used this code
[r,c]=find(A);
edgelist=[r,c];
edgelist = unique(edgelist, 'rows');
sz = max(edgelist(:));
DG = sparse(edgelist(:,1), edgelist(:,2), 1, sz, sz);% correct
matrix=full(DG)
%view(biograph(DG,[],'ShowWeights','on'));
p=graphallshortestpaths(DG)
I got result, but I got this matrix
P = [0     1     2     3     1
     1     0     1     2     2
     3     4     0     1     2
     2     3     1     0     1
     1     2     3     4     0];
and its wrong because the result should be symmetric matrix.
    P = [0     1     2     3     1
         1     0     1     2     1
         2     1     0     1     2
         3     2     1     0     1
         1     1     2     1     0];
I don't know why.
It doesn't mentioned which type of matrix this command work. I have sparse matrix, and I want to find all short paths so I can find the diameter.
can anyone help me please.
thanks for any help.
Nadia

Best Answer

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.
Related Question