求一个matlab的dijkstra算法 关于最佳距离的问题

dijkstra\u7b97\u6cd5\u5728matlab\u4e0a\u7684\u95ee\u9898

graphshortestpath\u662f\u751f\u7269\u4fe1\u606f\u5de5\u5177\u7bb1\uff08Bioinformatics Toolbox\uff09\u4e2d\u7684\u51fd\u6570\u3002MATLAB 7.0\uff08R14\uff09\u4e2d\u5305\u542b\u7684\u751f\u7269\u4fe1\u606f\u5de5\u5177\u7bb1\u5e94\u8be5\u662f1.1\u7248\uff0c\u4f46graphshortestpath\u51fd\u6570\u662f2.4\u7248\u624d\u52a0\u5165\u7684\u65b0\u51fd\u6570\uff0c\u5bf9\u5e94\u7684MATLAB\u7248\u672c\u662f7.3\uff082006b\uff09\u3002
\u6700\u597d\u7684\u89e3\u51b3\u529e\u6cd5\u662f\u5b89\u88c5\u4e00\u4e2a\u65b0\u7248\u7684MATLAB\uff0c\u56e0\u4e3a\u5f80\u5f80\u4e00\u4e2a\u5de5\u5177\u7bb1\u4e2d\u7684\u51fd\u6570\u8c03\u6574\u4f1a\u6d89\u53ca\u5230\u591a\u4e2a\u51fd\u6570\uff0c\u5982\u679c\u7ee7\u7eed\u4f7f\u7528\u65e7\u7248\uff0c\u5373\u4f7f\u628a\u8fd9\u4e2a\u51fd\u6570\u4f20\u7ed9\u4f60\uff0c\u4e5f\u5341\u4e4b\u516b\u4e5d\u4e0d\u80fd\u4f7f\u7528\u3002

\u6211\u5728\u53e6\u4e00\u4e2a\u63d0\u95ee\u4e2d\u7684\u56de\u7b54\u63d0\u4f9b\u4e86MATLAB\u4e0b\u8f7d\uff0c\u4f9b\u53c2\u8003\uff1a
http://zhidao.baidu.com/question/577883207.html

\u987a\u4fbf\u8bf4\u4e00\u53e5\uff0c\u5f88\u4e45\u5f88\u4e45\u4ee5\u524d\u6211\u7528\u8fc7\u4e00\u6bb5\u65f6\u95f47.0\uff0c\u786e\u4fe1\u5b83\u5b58\u5728\u6bd4\u8f83\u4e25\u91cd\u7684BUG\uff0c\u6240\u4ee5\u73b0\u5728\u5b81\u53ef\u7528\u66f4\u65e9\u76846.5\u4e5f\u4e0d\u75287.0\uff08\u4f46\u65b0\u4e00\u4e9b\u7684\u7248\u672c\u6bd4\u5982\u4e0a\u9762\u63d0\u4f9b\u7684\u4e24\u4e2a\u6ca1\u95ee\u9898\uff09\u3002

\u8fd9\u4e2a\u7b97\u6cd5\u7b97\u8d77\u59cb\u70b9\u5230\u5176\u4ed6\u70b9\u7684\u6700\u77ed\u8def\u5f84\u3002
function [d,index1,index2]=Dijkf(a)
%\u4e24\u70b9\u95f4\u6700\u77ed\u8ddd\u79bb\u7684Dijkstra\u7b97\u6cd5
% a\u8868\u793a\u56fe\u7684\u6743\u503c\u77e9\u9635
% d\u8868\u793a\u6240\u6c42\u6700\u77ed\u8def\u7684\u6743\u548c
% index1 \u8868\u793a\u6807\u53f7\u9876\u70b9\u7684\u987a\u5e8f
% index2 \u8868\u793a\u6807\u53f7\u9876\u70b9\u7d22\u5f15
% \u8d77\u59cb\u70b9\u4e3a\u7b2c\u4e00\u4e2a\u70b9
%\u53c2\u6570\u521d\u59cb\u5316
M=max(max(a));
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1:length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
%\u66f4\u65b0l\uff08v\uff09\uff0c\u540c\u65f6\u8bb0\u5f55\u9876\u70b9\u987a\u5e8f\u548c\u9876\u70b9\u7d22\u5f15
while sum(pb)<length(a)
tb=find(pb==0); %\u7b2ci\u6b21\u5faa\u73af\u5904\u7406\u7b2ci+1\u4e2a\u9876\u70b9
d(tb)=min(d(tb),d(temp)+a(temp,tb)); %\u66f4\u65b0l\uff08v\uff09
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp]; %\u8bb0\u5f55\u6807\u53f7\u987a\u5e8f
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index; %\u8bb0\u5f55\u6807\u53f7\u7d22\u5f15
end

\u4e0b\u9762\u8fd9\u4e2a\u7528\u6765\u6c42\u4efb\u610f\u4e24\u70b9\u95f4\u7684\u6700\u77ed\u8ddd\u79bb\uff0c\u8fd8\u80fd\u7b97\u51fa\u8def\u7ebf\u3002
function [P,u]=n2shorf(W,k1,k2)
%\u6c42\u4efb\u610f\u4e24\u70b9\u6700\u77ed\u8def\u5f84\u7b97\u6cd5
% P \u4e3a\u4e24\u70b9k1,k2\u95f4\u7684\u6700\u77ed\u8def\uff0c\u9876\u70b9\u4ee5\u7ecf\u8fc7\u6b21\u5e8f\u8fdb\u884c\u6392\u5e8f
% u \u4e3a\u6700\u77ed\u8def\u7684\u957f\u5ea6
% \u521d\u59cb\u5316
n=length(W);
U=W;
m=1;
% \u5229\u7528\u6c42\u6700\u77ed\u8def\u7684Floyd\u7b97\u6cd5\uff0c\u6c42\u6700\u77ed\u8def\u77e9\u9635
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);%\u6700\u77ed\u8ddd\u79bb
% \u6c42\u4efb\u610f\u7ed9\u5b9a\u4e24\u4e2a\u9876\u70b9\u89c1\u7684\u6700\u77ed\u8def\u5305\u542b\u7684\u9876\u70b9
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
end

看这个文档的 例9 ，是Dijkstra算法求解最短路的例题，附有Matlab源程序。
http://lxy.sjzu.edu.cn/jmzt/jpk/jch/51.doc
另外，任意两个点之间的距离也可以考虑用Floyd算法，上述文档3.2节例10是它的Matlab源程序。

图论工具箱：http://www.matlabsky.com/thread-295-1-1.html
基本图论函数库：http://www.matlabsky.com/thread-299-1-1.html
Dijkstra最短路径：http://www.matlabsky.com/thread-297-1-1.html
Kruskal最小生成树：http://www.matlabsky.com/thread-296-1-1.html
Prims算法：http://www.matlabsky.com/thread-300-1-1.html
A星优化算法：http://www.matlabsky.com/thread-298-1-1.html

Floyd算法

推荐这个， 简单快捷

自己实现也非常容易

扩展阅读：摩天轮matlab地址2020 ... code网站免费 ... 国外免费源码共享网站 ... matlab仿真下载的网站 ... python网站入口 ... matlab免费版去哪里下 ... matlab免费代码网站 ... matlab各种符号大全 ... 免费下载matlab源码的网站 ...