两种最短路径（测地距离）的算法——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')?
?
?
總結
以上是生活随笔為你收集整理的两种最短路径（测地距离）的算法——Dijkstra和Floyd的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 熵的概念理解
- 下一篇： 【ZJOI2015】幻想乡 Wi-Fi