最短路径问题的实现

1、最短路径问题的实现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:5for j=1:5if i=j && W(i,j)=0 W(i,j)=inf;endstart=1;S=start,zeros(1,4);D=index;W(S(1),:);for i=1:4 mid_1,min_1 =Get_mi

2、n( 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.

3、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_n

4、ew(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:colif W(2,i)<D(2,i)D(2,i)=W(2,i);endend4.2 Dijkstra 堆实现代码主程序部分close all ;clear all ;clc;S=1 1 2 2 3 3 4 4 4 4 5 6 6 7 8;% startE=2 3 5 4 4 6 5 7 8 6 7 8 9 9 9;% endW=17 20 12 60 23 45 44 15 77 21 17 17 15 3

5、710;%G(9,9)=0;G=sparse(S,E,W);G(9,9)=0;P=biograph(G, 'ShowWeights' , 'on' );H=view(P);Dist=cell(9,1);Path=cell(9,1);i=1;for j=1:9Distj,Pathj=graphshortestpath(G,i,j,'Method' , 'Dijkstra' );end% set(H.Nodes(Path),'Color',125 125 125/255);%edges=getedgesbynodeid

6、(H,get(H.Nodes(Path),'ID');% set(edges,'LineColor',1 0 0);% set(edges,'LineWidth',2.0);函数部分function dist,path,pred =graphshortestpath(G,S,varargin)algorithms = 'bfs' , 'dijkstra' , 'bellman-ford' , 'acyclic' ; algorithmkeys = 'spb' , &#

7、39;dij' , 'bel' , 'spa' ;debug_level = 0;% set defaults of optional input argumentsD = 1:length(G); % will return shortest path to all other nodesW = ;% no custom weightsalgorithm = 2;% defaults to dijkstradirected = true;% find out signature of input argumentsif nargin>2 &

8、;& isnumeric(varargin1)D = varargin1;varargin(1) = ;end% read in optional PV input argumentsnvarargin = numel(varargin);if nvararginif rem(nvarargin,2) = 1error(message( 'bioinfo:graphshortestpath:IncorrectNumberOfArguments' , mfilename);endokargs = 'method' , 'directed'

9、, 'weights' ; for j=1:2:nvarargin-1pname = vararginj;pval = vararginj+1;k =find(strncmpi(pname,okargs,numel(pname);if isempty(k)error(message( 'bioinfo:graphshortestpath:UnknownParameterName', pname);elseiflength(k)>1error(message('bioinfo:graphshortestpath:AmbiguousParameterN

10、ame', pname);elseswitch (k)case 1 % 'method'algorithm =find(strncmpi(pval,algorithms,numel(pval);if isempty(algorithm)error(message('bioinfo:graphshortestpath:NotValidMethod' , pval)elseif numel(algorithm)>1error(message('bioinfo:graphshortestpath:Ambiguou sMethod' , p

11、val)endcase 2 % 'directed'directed =bioinfoprivate.opttf(pval,okargsk,mfilename);case 3 % 'weights'W = pval(:);endendendend% call the mex implementation of the graph algorithmsif nargout>1if isempty(W)dist,pred =graphalgs(algorithmkeysalgorithm,debug_level,di rected,G,S);elsedist,

12、pred =graphalgs(algorithmkeysalgorithm,debug_level,di rected,G,S,W);endelseif isempty(W)dist =graphalgs(algorithmkeysalgorithm,debug_level,di rected,G,S);elsedist =graphalgs(algorithmkeysalgorithm,debug_level,di rected,G,S,W);endend dist = dist(D);% calculate pathsif nargout>1path = graphpred2path(pred,D);end结果示例：随机生成的有向交通图：val =(1,(2) 17(1,(3) 20(1,(4) 60(3,4)23(1,(5) 12(4,(5) 44(3,6