2023年7月30日发(作者：)

两种最短路径（测地距离）的算法——Dijkstra和Floyd 从某顶点出发，沿图的边到达另⼀顶点所经过的路径中，各边上权值之和最⼩的⼀条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。最短路径问题是图论研究中的⼀个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：（1）确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。适合使⽤Dijkstra算法。（4）全局最短路径问题- 求图中所有的最短路径。适合使⽤Floyd-Warshall算法。Dijkstra算法⼜称迪杰斯特拉算法，是⼀个经典的最短路径算法，主要特点是以起始点为中⼼向外层层扩展，直到扩展到终点为⽌，使⽤了⼴度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到⼀个最短路径树。时间复杂度为O(N^2)实例：

抽象步骤：1.将起点A放⼊集合中，A点的权值为0,因为A->A=0。2.与起点A相连的所有点的权值设置为A->点的距离，连接不到的设置为⽆穷。并且找出其中最⼩权值的B放⼊集合中（此时A->B必定为最⼩距离）。3.与B点相连的所有点的权值设置为B->点的距离，并且找出其中最⼩权值的C点放⼊集合中（此时C的权值必定为其最⼩距离）。4.重复步骤3，直⾄所有点加⼊集合中。便能得到所有点与A点的最短距离。 Floyd算法全称Floyd-Warshall算法，⼜称佛洛依德算法，是解决任意两点间的最短路径的⼀种算法，但是时间复杂度⽐迪杰斯特拉要⾼，时间复杂度为O(N^3)，空间复杂度为O(N^2)。

简单案例：

算法的思路：

通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引⼊两个矩阵，矩阵D中的元素a[i][j]表⽰顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表⽰顶点i到顶点j经过了b[i][j]记录的值所表⽰的顶点。 假设图G中顶点个数为N，则需要对矩阵D和矩阵P进⾏N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。接下来开始，对矩阵D进⾏N次更新。 第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表⽰”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离”> “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！我们先初始化两个矩阵：第⼀步：以v1为中阶，更新两个矩阵

第⼆步：以v2为中阶，更新两个矩阵 第三步：以v3为中阶，更新两个矩阵

第四步：以v4为中阶，更新两个矩阵

第五步：以v5为中阶，更新两个矩阵第六步：以v6为中阶，更新两个矩阵

第七步：以v7为中阶，更新两个矩阵各个顶点的最短路径对近邻图的构建通常有两种做法，⼀种是指定近邻点个数，例如欧⽒距离最近的k 个点为近邻点，这样得到的近邻图称为k近邻图;另⼀种是指定距离阀值ε，距离⼩于ε的点被认为是近邻点，这样得到的近邻图称为ε近邻图.两种⽅式均有不⾜，例如若近邻范围指定得较⼤，则距离很远的点可能被误认为近邻，这样就出现"短路"问题;近邻范围指定得较⼩，则圈中有些区域可能与其他区域不存在连接，这样就出现"断路"问题.短路与断路都会给后续的最短路径计算造成误导.

Floyd算法计算测地距离（matlab实现）

内容借鉴了他⼈⽂章，具体出处已经忘了。好久前⾃⼰在matlab上实现的，今天总结写⼀下。这是最短路径Floyd的主程序（借⽤他⼈的）：function [dist,mypath,o]=myfloyd(a,sb,db);% 输⼊：a—邻接矩阵(aij)是指i 到j 之间的距离，可以是有向的% sb—起点的标号；db—终点的标号% 输出：dist—最短路的距离；% mypath—最短路的路径n=size(a,1); path=zeros(n);for i=1:nfor j=1:nif a(i,j)~=infpath(i,j)=j; %j 是i 的后续点endendendfor k=1:nfor i=1:nfor j=1:nif a(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);endendendenddist=a(sb,db);o=a;mypath=sb; t=sb;while t~=dbtemp=path(t,db);mypath=[mypath,temp];t=temp;endreturn

这是Floyd例⼦的实现程序，调⽤主程序完成的（⾃⼰写的）：

clccleara=[0 12 inf inf inf 16 1412 0 10 inf inf 7 infinf 10 0 3 5 6 infinf inf 3 0 4 inf infinf inf 5 4 0 2 816 7 6 inf 2 0 914 inf inf inf 8 9 0];[n,m]=size(a);for i=1:n for j=i:n [dist,mypath,o]=myfloyd(a,i,j); if i~=j c=num2str(mypath); fprintf('v%dv%d,dist=%d，path=%sn', i,j, dist,c) end endend在瑞⼠卷上画出测地距离（⾃⼰写的）：clc;clear all;close all;%⽤mds对瑞⼠卷降维%瑞⼠卷的⽣成图N=1000;t=(3*pi/2)*(1+2*rand(1,N));s=21*rand(1,N);X=[t.*cos(t);s;t.*sin(t)];plot3(X(1,:),X(2,:),X(3,:),'.')%计算距离矩阵个X=X';[m,n]=size(X);D=zeros(m,m);for i=1:m for j=i:m D(i,j)=norm(X(i,:)-X(j,:)); D(j,i)=D(i,j); endend%计算矩阵中每⾏前k个值的位置并赋值（先按⼤⼩排列）W1=zeros(m,m);k=8;for i=1:mA=D(i,:);t=sort(A(:));%对每⾏进⾏排序后构成⼀个从⼩到⼤有序的列向量[row,col]=find(A<=t(k),k);%找出每⾏前K个最⼩数的位置for j=1:kc=col(1,j); W1(i,c)=D(i,c); %W1(i,c)=1;%给k近邻赋值为距离endendfor i=1:m for j=1:m if W1(i,j)==0&i~=j W1(i,j)=inf; end endend%计算测地距离，o是每个点到其他点的测地距离矩阵[dist,mypath,o]=myfloyd(W1,50,400);distmypath[col,rol]=size(mypath)X1=[];for i=1:rol ding=mypath(1,i); X1=[X1;X(ding,:)];endplot3(X(:,1),X(:,2),X(:,3),'.')hold onplot3(X1(:,1),X1(:,2),X1(:,3),'o-r')