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

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

Answer 1

[Steven Lord]

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.

[nadia nadi]

Dear Steven,

thanks for the explanation, although the command you mentioned are not work in my matlab version, still your answer is useful. my result is not wrong but its for directed graph. I used A|A.' to get adjacency matrix to get the result for undirected graph. so the both result are not wrong. is that true ?

many thanks

[Steven Lord]

As I said, this graph functionality was introduced in MATLAB as part of release R2015b. If you're using an older release, that would explain why they don't work in your release.

As for checking your results, for a small graph like this a picture truly is worth a thousand words. Use the biograph VIEW function to show the graph then trace along the edges to check shortest paths and to ensure that the network graph has the edges you expect it to have.

 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];
 bg = biograph(A|A.');
 view(bg)

There are arrows from node 1 to node 5 and node 5 to node 4, so that's a shorter path than node 1 to 2 to 3 to 4.