利用MATLAB实现路径优化问题

Question

平面上有若干个固定点，已知任意两点之间的距离，规定一个起点，从起点出发，求不限终点，经过所有点的一条最短路径。

Answer 1

你好，确定起始点的最短路径问题只需要距离矩阵和起始点编号即可：

function [d,index1]=mydijkstra2(a,sb)
%从起点出发，寻找遍历所有点的最短路径
% 输入：a—邻接矩阵，a（i，j)是指i到j之间的距离，可以是有向的
% sb—起点的标号
% 输出：d—从起点开始便利所有标号的最短路距离, index1—从起点开始便利所有标号的最短路路径
%pb用来存放P标号信息 index1为标号顶点顺序 index2标号顶点索引
a(a==0)=inf;
pb(1:length(a))=0;pb(sb)=1;index1=sb;index2=ones(1,length(a));
%d用来存放最短通路的值
d(1:length(a))=inf;d(sb)=0;
temp=sb;%最新的P标号的起点
while sum(pb)<length(a)
    tb=find(pb==0);
    d(tb)=min(d(tb),d(temp)+a(temp,tb));
    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));%可能有多个点同时达到最小值，只取其中一个
    pb(temp)=1;
    index1=[index1,temp];
    temp2=find(d(index1)==d(temp)-a(temp,index1));
    index2(temp)=index1(temp2(1));
end
end

举个栗子

a=[0 50 Inf 40 25 10
50 0 15 20 Inf 25
Inf 15 0 10 20 Inf
40 20 10 0 10 25
25 Inf 20 10 0 55
10 25 Inf 25 55 0]; % 距离矩阵
sb = 2; % 从第二个点出发
[d,index1]=mydijkstra2(a,sb)

结果：

d =

    35     0    15    20    30    25


index1 =

     2     3     4     6     5     1

可见最终的路径是这么走的2 →3 →4→6→5→1
而且最短路径长度是 35+0+15 +20+30+25=125
如有帮助还望题主给个采纳支持一下答主答题哟，谢谢啦