Question

用Dijkstra算法求最短路径的MATLAB程序

问题描述：边界的范围是a*b，把这a*b的范围网格化，将这介质剖面剖分成M*N个矩形网格单元，从网格的x轴上某一点激发射线，在网格的y轴上接收到从激发点激发的射线（x轴是正方向的，y轴是负方向的）
基本要求：
一 用DIJKSTRA算法求从某一激发点到某一接收点的最短路径（为了提高计算精度，需要在每个网格单元边界上内插S*T个节点），激发点为X轴上某点（源点），接收点可以是y轴上的任一点（目标点）。
二 用户输入源点和目标点后，程序应输出源点到目标点的最短路径，并画出射线穿越图，计算出这条射线经过每个网格的长度和所穿越网格的编号（共有M*N个网格）。
在线等！～ Q859413982

Answer 1

你对图论的知识有了解吧~W是关联矩阵，s和t分别是起始点和终止节点的序号。返回的d为最短的加权路径长度,p为最优路径节点的序号向量。注意，这里W矩阵为0的点权值已经自动设为无穷大了。请参考《高等应用数学问题的 MATLAB一书》。我吧程序赋给你。
你做一个M函数用吧。
function [d,path]=dijkstra(W,s,t)
[n,m]=size(W);ix=(W==0);W(ix)=inf;
if n~=m,error('Square W required');end
visited(1:n)=0; dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;
for i=1:(n-1),%求出每个节点与起始点的关系
ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);
[a,u]=min(vec);visited(u)=1;
for v=1:n,if (W(u,v)+dist(u)<dist(v)),
dist(v)=dist(u)+W(u,v);parent(v)=u;
end;end;end
if parent(t)~=0,path=t;d=dist(t);%回溯最短路径
while t~=s,p=parent(t);path=[p path];t=p;end;
end;
希望对你有用
是否可以解决您的问题？

追问

不要复制粘贴的

Answer 2

这个挺好做的，有现有的算法，递归一下就好了，我现在没有现成的.m文件，不过可以告诉你怎么弄，你自己写一下就好了，c++ 大概3 4百行

追问

我要MATLAB程序写的，会吗？

追答

MATLAB不熟，可以给你传本书看看，是c的，我想很容易转成matlab语言的吧，具体不知道，这个对你很重要吗？