%% ************求任意两点间最短路*************** % W 表示图的权值矩阵 // % P 为两顶点k1,k2之间的最短路，顶点以经过次序进行排序 // % u 为最短路的长度 // %% function [P u] = n2shorf(W,k1,k2) n = length(W); U =W; m = 1; while m <= n for i = 1:n for j = 1:n if U(i,j) > U(i,m) + U(m,j); U(i,j) = U(i,m) + U(m,j); end end end m = m+1; end u = U(k1,k2); % 求任给定两个顶点间的最短路所包含的顶点 P1 = zeros(1,n); k = 1; P1(k) = k2; V = ones(1,n)*inf; kk = k2; while kk ~=k1 for i = 1:n V(1,i) = U(k1,kk) - W(i,kk); if V(1,i) == U(k1,i) P1(k+1) = i; kk = i; k = k+1; end end end k = 1; wrow = find(P1~=0); for j = length(wrow):(-1):1 P(k) = P1(wrow(j)); k = k+1; end
