dijkstra算法_求解图论中的两点间最短路径_matlab源码

%%Dijkstra算法 %%vi为结点，ei为边，L为路径长度 function Dijkstra %%输入信息 n=input('请输入结点的个数n='); m=input('请输入边的条数m='); for k=1:m bian(k).qianqu=input('边的前驱','s'); bian(k).houji=input('边的后继','s'); bian(k).value=input('边的权重'); end for k=1:n dian(k).name=strcat('v',num2str(k)); dian(k).biaohao='t'; end %%初始化 dian(1).L=0; dian(1).qianqu=0; dian(1).biaohao='p'; for k=1:m if bian(k).qianqu=='v1' dian(str2num(bian(k).houji(2))).L=bian(k).value; dian(str2num(bian(k).houji(2))).qianqu=dian(1).name; end if bian(k).houji=='v1' dian(str2num(bian(k).qianqu(2))).L=bian(k).value; dian(str2num(bian(k).qianqu(2))).qianqu=dian(1).name; end end for k=1:n if isempty(dian(k).L) dian(k).L=inf; end end %%求解最短途径 log=n-1;min=inf; while log for k=2:n if dian(k).biaohao=='t' if min>dian(k).L mins=k; min=dian(k).L; end end end dian(mins).biaohao='p'; for k=1:m if bian(k).qianqu==strcat('v',num2str(mins))&dian(str2num(bian(k).houji(2))).biaohao~='p' if dian(str2num(bian(k).houji(2))).L>(dian(str2num(bian(k).qianqu(2))).L+bian(k).value) dian(str2num(bian(k).houji(2))).L=dian(str2num(bian(k).qianqu(2))).L+bian(k).value; dian(str2num(bian(k).houji(2))).qianqu=dian(mins).name; end end if bian(k).houji==strcat('v',num2str(mins))&dian(str2num(bian(k).qianqu(2))).biaohao~='p' if dian(str2num(bian(k).qianqu(2))).L>(dian(str2num(bian(k).houji(2))).L+bian(k).value) dian(str2num(bian(k).qianqu(2))).L=dian(str2num(bian(k).houji(2))).L+bian(k).value; dian(str2num(bian(k).qianqu(2))).qianqu=dian(mins).name; end end end min=inf;log=log-1; end dian(n).L dian(n).name p=dian(str2num(dian(n).qianqu(2))); for k=1:(n-2) p.name p=dian(str2num(p.qianqu(2))); end p.name