Подсчитайте количество всех кратчайших путей для любых двух вершин в графе

Question

Для любой пары различных вершин в данном неориентированном графе G = я хочу найти количество всех кратчайших путей («SP», в сокращении) (нет необходимости или необходимости находить / печатать точные вершинына определенном пути).Например, для следующего графика, представленного в формате списка ребер, есть два SP: (1,3,2) и (1,4,2).

вершина =

1   3
2   4
1   4
2   3
1   8
4   7
3   6
5   2

Я хочу реализовать этот алгоритм на основе алгоритма Флойда-Варшалла, который является известным алгоритмом, основанным на идее динамического программирования, чтобы найтизначение кратчайшего пути для каждой пары вершин в O (N ^ 3), скажем, результатом является двумерный массив a [n] [n].n - количество вершин.Для приведенного выше графика это:

0   2   1   1   3   2   2   1
2   0   1   1   1   2   2   3
1   1   0   2   2   1   3   2
1   1   2   0   2   3   1   2
3   1   2   2   0   3   3   4
2   2   1   3   3   0   4   3
2   2   3   1   3   4   0   3
1   3   2   2   4   3   3   0

Код для построения матрицы графа G и решения для матрицы a выглядит следующим образом:

v = vertex(:,1);
t = vertex(:,2);
G = zeros( max(max(v),max(t)));

% Build the matrix for graph:
for i = 1:length(v)
    G(v(i), t(i)) = G(v(i), t(i)) + 1; 
    G(t(i), v(i)) = G(v(i), t(i)); % comment here is input is bi-directional
end

a = G;
n = length(a);
a(a==0) = Inf;
a(1:n+1:n^2)=0; % diagonal element  to be zero

for k = 1:n
    for i= 1:n
        for j= 1:n %  for j=i+1:n
            if a(i,j) > a(i,k) + a(k,j)
                a(i,j) = a(i,k) + a(k,j);
%                 a(j,i) = a(i,j);
            end
        end
    end
end

Теперь давайте определим двумерный массив b [n] [n] как количество ВСЕХ SP для каждой пары вершин.Например, мы ожидаем, что b [1] [2] = 2. Я написал следующий код в MATLAB (если вы не знакомы с MATLAB, просто обработайте его как псевдокод).Он дает почти правильные значения для всех пар , за исключением нескольких неправильных значений для определенных пар .Например.после запуска cod eb [5] [8] = 0, что неверно ( правильный ответ должен быть 2 )

%% 
% find the number of ALL SP paths for ALL pairs based on the "a" array:
% b is a two-dim array, b(i,j) is the total number of SP for pair( i,j)
b = G;
for k=1:n
    for i=1:n
        for j= i+1:n

            if(i==j)
                continue; % b(i,i)=0
            end

            if (k==j) % the same as : G(k,j)==0
                continue;
            end

            if(k==i && G(k,j)~=0)
                b(i,j) = 1;
                continue;
            end

            if(a(i,j) ~= a(i,k)+G(k,j)) % w(u,v)=G(u,v) in unweighted graph)
                continue;
            end  

            % sigma(s,v) = sigma(s,v) + sigma(s,u);
            b(i,j) = b(i,j) + b(k,i);
        end
    end
end