两种最短路径（测地距离）的算法——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:n
for j=1:n
if a(i,j)~=inf
path(i,j)=j; %j 是i 的后续点
end
end
end
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=path(i,k);
end
end
end
end
dist=a(sb,db);
o=a;
mypath=sb; t=sb;
while t~=db
temp=path(t,db);
mypath=[mypath,temp];
t=temp;
end
return

这是Floyd例子的实现程序，调用主程序完成的（自己写的）：

clc
clear
a=[0	12 inf	inf	inf	16	14
12	0	10	inf	inf	7	inf
inf	10	0	3	5	6	inf
inf	inf	3	0	4	inf	inf
inf	inf	5	4	0	2	8
16	7	6	inf	2	0	9
14	inf	inf inf	8	9	0];[n,m]=size(a);
for i=1:nfor j=i:n[dist,mypath,o]=myfloyd(a,i,j);if i~=jc=num2str(mypath);fprintf('v%dv%d,dist=%d，path=%s\n', i,j, dist,c)endend
end

在瑞士卷上画出测地距离（自己写的）：

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:mfor j=i:mD(i,j)=norm(X(i,:)-X(j,:));D(j,i)=D(i,j);end
end
%计算矩阵中每行前k个值的位置并赋值（先按大小排列）
W1=zeros(m,m);
k=8;
for i=1:m
A=D(i,:);
t=sort(A(:));%对每行进行排序后构成一个从小到大有序的列向量
[row,col]=find(A<=t(k),k);%找出每行前K个最小数的位置
for j=1:k
c=col(1,j);W1(i,c)=D(i,c); %W1(i,c)=1;%给k近邻赋值为距离
end
end
for i=1:mfor j=1:mif W1(i,j)==0&i~=jW1(i,j)=inf;endend
end
%计算测地距离，o是每个点到其他点的测地距离矩阵
[dist,mypath,o]=myfloyd(W1,50,400);
dist
mypath[col,rol]=size(mypath)
X1=[];
for i=1:rolding=mypath(1,i);X1=[X1;X(ding,:)];
end
plot3(X(:,1),X(:,2),X(:,3),'.')
hold on
plot3(X1(:,1),X1(:,2),X1(:,3),'o-r')