数学建模中,给出非常多的节点,求这些节点的最短路径（类似一条线的路径）,应该用什么算法好?老师说不要用蚁群算法,遗传算法之类太悬的算法

Question

数学建模中,给出非常多的节点,求这些节点的最短路径（类似一条线的路径）,应该用什么算法好?
老师说不要用蚁群算法,遗传算法之类太悬的算法

Answer 1

下面是我自己编写的一段代码,用来求过包含两千多个点的最短路,速度很快,比遗传、蚁群快而且最短路更短.你可以试试看,有问题再问我.
function [S,len]=short(P)
% 此程序用来求相同类型点间的最短路
% P表示某一类型的点的坐标矩阵
% p是最短路径
% d是路径权值和
%建立权值矩阵
n=length(P);%求该类型点的数量
W=zeros(n,n);
for i=1:n %计算权值并填充权值矩阵,由于各点联通,此权值矩阵就是该图的最短路矩阵
for j=(i+1):n
W(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
for i=2:n
for j=1:(i-1)
W(i,j)=W(j,i);
end
end
%求通过所有点的最短路
%先求从i点至j点,必须通过指定其他n-2个点的最短路,选出其中的的最短路
S=zeros(1,n);
S(1)=1; %先插入1,2点,以此为基准,每次插进一个新点
S(2)=2;
d1=2*W(1,2);
for i=3:n %新加入的点的标号
d1i=zeros(1,i); %插入第i个点,有i中可能的距离,其中最小值将为该轮的d1
for j=1:i %新加入点的位置,插入第i个点是有i个空位可供选择
if j==1 %在第一个空位插入
d1i(j)=d1+W(i,S(1))+W(i,S(i-1))-W(S(1),S(i-1)); %插入点在首端时,距离为原距离与第i点与上一次插入后的第1位置的点之间距离之和
end
if j>1 & j