最短路径问题的实现

最短路径问题的实现4.1 Dijkstra数组实现代码主程序部分close all;clear all;clc;W=zeros(5);index=1,2,3,4,5;W(1,2)=10;W(1,4)=30;W(1,5)=100;W(2,3)=50; W(3,5)=10;W(4,2)=10;W(4,3)=20;W(4,5)=60;for i=1:5 for j=1:5 if i=j & W(i,j)=0 W(i,j)=inf; end endendstart=1;S=start,zeros(1,4);D=index;W(S(1),:);for i=1:4 mid_1,min_1 =Get_min( S,D );S(1,i+1)=mid_1;mid_D=index;W(mid_1,:);D=Get_new(S,mid_D,D,min_1,index);end % S=1,1,1,2,3,4,4,4; % E=2,4,5,3,5,2,3,5; % W=10,30,100,50,10,10,20,60; % G(9,9)=0;% G=sparse(S,E,W); % G(5,5)=0;% P=biograph(G,ShowWeights,on);% H=view(P);% set(H.Nodes(Path),Color,1 0.4 0.4);% edges=getedgesbynodeid(H,get(H.Nodes(Path),ID);% set(edges,LineColor,1 0 0);% set(edges,LineWidth,2.0);函数部分function mid_index,min_D =Get_min( S,D) S=S(S=0); mid_D=D; mid_D(:,S)=; min_D=min(mid_D(2,:); ,mid_index=find(D=min_D); mid_index=min(mid_index); endfunction D = Get_new(S,mid_D,D,min_1,index) W=mid_D; S=S(S=0); col=setdiff(index,S); W(2,:)=W(2,:)+min_1; for i=1:col if W(2,i)2 & isnumeric(varargin1) D = varargin1; varargin(1) = ;end % read in optional PV input argumentsnvarargin = numel(varargin);if nvarargin if rem(nvarargin,2) = 1 error(message(bioinfo:graphshortestpath:IncorrectNumberOfArguments, mfilename); end okargs = method,directed,weights; for j=1:2:nvarargin-1 pname = vararginj; pval = vararginj+1; k = find(strncmpi(pname,okargs,numel(pname); if isempty(k) error(message(bioinfo:graphshortestpath:UnknownParameterName, pname); elseif length(k)1 error(message(bioinfo:graphshortestpath:AmbiguousParameterName, pname); else switch(k) case 1 % method algorithm = find(strncmpi(pval,algorithms,numel(pval); if isempty(algorithm) error(message(bioinfo:graphshortestpath:NotValidMethod, pval) elseif numel(algorithm)1 error(message(bioinfo:graphshortestpath:AmbiguousMethod, pval) end case 2 % directed directed = bioinfoprivate.opttf(pval,okargsk,mfilename); case 3 % weights W = pval(:); end end endend % call the mex implementation of the graph algorithmsif nargout1 if isempty(W) dist,pred = graphalgs(algorithmkeysalgorithm,debug_level,directed,G,S); else dist,pred = graphalgs(algorithmkeysalgorithm,debug_level,directed,G,S,W); endelse if isempty(W) dist = graphalgs(algorithmkeysalgorithm,debug_level,directed,G,S); else dist = graphalgs(algorithmkeysalgorithm,debug_level,directed,G,S,W); endend dist = dist(D); % calculate pathsif nargout1 path = graphpred2path(pred,D);end结果示例：随机生成的有向交通图：val = (1,2) 17 (1,3) 20 (2,4) 60 (3,4) 23 (2,5) 12 (4,5) 44 (3,6) 45 (4,6) 21 (4,7) 15 (5,7) 17 (4,8) 77 (6,8) 17 (6,9) 15 (7,