Ошибка в поиске графических объектов в матрице

Question

У меня есть матрица: 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]; Я хочу найти graphallshortestpaths в этой сети.

Я прошел через эту ссылку http://www.mathworks.com/help/bioinfo/ref/graphallshortestpaths.html

adj_sparse = разреженный (тест);

дистанции = graphallshortestpaths (adj_sparse); В соответствии с примером, это должно вернуть мне матрицу кратчайшего пути. однако я получаю сообщение об ошибке, как

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); 

Решение приведено ниже в @rayryeng работ, но только для относительно меньших узлов.

---

Я могу запустить этот алгоритм и получить результаты для некоторых файлов, которые относительно малы. но при запуске этого алгоритма для более крупного файла я столкнулся с некоторой ошибкой «» с ошибкой », когда я вычисляю более крупный файл, скажем, более 30000 узлов. (У меня очень высокий конфигурационный ПК, хотя :)) Я слышал о пакете в Python под названием igraph, который дает результат очень быстро !. У нас есть какой-либо аналогичный алгоритм в matlab, который был оптимизирован для вычисления для очень больших узлов?

Answer 1

Похоже, что вы не создаете разреженную матрицу должным образом. Вы принимаете матрицу A и преобразуете ее в разреженную матрицу. Я подозреваю, что A является матрицей связности, где строка обозначает границу между двумя узлами. Я также буду считать, что вес, связанный с каждым из ваших узлов равно 1. Таким образом, вы должны сделать это:

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) 

Обратите внимание, что вам необходимо указать расположение строк на разреженной матрице чтобы быть первым столбцом A, а расположение столбцов вашей разреженной матрицы - это второй столбец A. С приведенным выше, я получаю:

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