CODEWITHSUNDEEP
matlabshortest-path
SeasonalShot
SeasonalShot

Reputation: 2579

Error in Finding graphallshortestpaths in a matrix

I have a matrix say A=[2 1;3 1;4 1;5 1;1 2;3 2;4 2;1 3;2 3;5 3;1 4;2 4;5 4;1 5;3 5;4 5]; I want to find the graphallshortestpaths in this network.

I have gone through this link http://www.mathworks.com/help/bioinfo/ref/graphallshortestpaths.html

adj_sparse = sparse(test);

distances = graphallshortestpaths(adj_sparse); According to the example , this should return me a matrix of the shortest path. however i am getting an error as 

Error using graphalgs Sparse array should have same number of rows and columns.

Error in graphallshortestpaths (line 85)
    dist = graphalgs('all',debug_level,directed,G);

The Solution given below by @rayryeng works, but only for relatively lesser nodes.

I am able to run this algorithm and get results for some files which are relatively small. but while running this algorithm for larger file, I encountered some "memory running out" problem when i compute a larger file ,say more than 30000 node. (I have a very high config PC though :) ) I heard about a package in Python called igraph which gives the result very fast!. Do we have any similar algorithm in matlab that has been optimized to compute for very large nodes?

Upvotes: 2

Views: 777

Answers (1)

rayryeng
rayryeng

Reputation: 104545

It looks like you're not creating the sparse matrix properly. You are taking the matrix A and converting it into a sparse matrix. I suspect that A is a connectivity matrix where a row denotes an edge between the two nodes. I'm also going to assume that the weights connected to each of your nodes is equal to 1. As such, you need to do this:

A=[2 1;3 1;4 1;5 1;1 2;3 2;4 2;1 3;2 3;5 3;1 4;2 4;5 4;1 5;3 5;4 5];
G = sparse(A(:,1), A(:,2), 1);
graphallshortestpaths(G)

Note that you need to specify the row locations of the sparse matrix to be the first column of A, while the column locations of your sparse matrix is the second column of A. With the above, I get:

ans =

 0     1     1     1     1
 1     0     1     1     2
 1     1     0     2     1
 1     1     2     0     1
 1     2     1     1     0

Upvotes: 2

Related Questions