Как подмножить матрицу и найти кратчайший путь между всеми узлами в Matlab?

У меня есть матрица:

       1          2         3         4         5         6    
   1 0.7431    0.2769    0.0000    0.1869    0.2760    0.9597
   2 0.2769    0.0462    0.0344    0.4898    0.6797    0.3404
   3 0.0000    0.0344    0.4387    0.4456    0.6551    0.0000
   4 0.1869    0.4898    0.4456    0.6463    0.1626    0.2238
   5 0.2760    0.6797    0.6551    0.1626    0.1190    0.7513
   6 0.9597    0.3404    0.0000    0.2238    0.7513    0.2551

Целые числа являются индексом. У меня есть хеш-таблица, в которой каждый индекс является человеком. Десятичные дроби — это взаимодействия между индексами. Теперь я хочу подмножить эту матрицу со списком индексов (1, 3, 6), что означает, что мне нужно только взаимодействие между 1, 3 и 6.

Subset:

       1             3              6
    1 0.7431       0.0000          0.9579

    3 0.0000       0.4387          0.0000

    6 0.9579       0.0000          0.2551

Между некоторыми людьми нет взаимодействия, например. человек 1 и 3 или человек 3 и 6. Но 1 взаимодействует с 2, 4, 5 и 6, которые взаимодействуют с 3. Таким образом, 1 взаимодействует с 3 через 2, 4, 5 или 6. Это может быть 1-> 2-> 4 ->3 или 1->4->3 что-то в этом роде. Я хочу найти кратчайший путь для тех двух узлов, которые не имеют прямого взаимодействия. Я хочу подмножить исходную матрицу, а затем найти кратчайший путь между узлами, которые не взаимодействуют. Извините, ребята, я не ясно выразился.


person Gray    schedule 23.02.2016    source источник
comment
Что вы подразумеваете под расстояниями между всеми узлами и кратчайшими путями?   -  person mikkola    schedule 23.02.2016
comment
Можете ли вы привести небольшой числовой пример? Я с @mikkola, где я не понимаю, чего ты хочешь.   -  person rayryeng    schedule 23.02.2016
comment
Является ли это матрицей весов в полном графе? Если да, то почему у вас ненулевые значения по диагонали?   -  person gariepy    schedule 23.02.2016
comment
Спасибо за дополнительную информацию, которая помогает, но, например, все еще сбивает с толку ненулевой вес взаимодействия (1,1).   -  person gariepy    schedule 23.02.2016


Ответы (1)


Думаю, вам стоит взглянуть на алгоритм Дейкстры:

Существует алгоритм обмена файлами Mathworks, который вычисляет алгоритм Дейкстры здесь:

http://www.mathworks.com/matlabcentral/fileexchange/36140-dijkstra-algorithm

Я использовал его для расчета кратчайших путей раньше... он довольно эффективен и гарантированно оптимален. На самом деле нет необходимости подмножать матрицу... если есть узлы, которые вы не хотите учитывать, просто не помещайте их в свою матрицу.

person gariepy    schedule 23.02.2016