why the command of finding the all short paths for graph ( graphallshortestpaths ) give me wrong numbers
11 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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
0 commentaires
Réponse acceptée
Steven Lord
le 12 Oct 2015
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.
2 commentaires
Steven Lord
le 13 Oct 2015
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.
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange
Produits
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!