軌跡分段演算法最短

A. 求寫最短路徑演算法。由A地到E地，途經B（B1，B2，B3）C（C1，C2，C3）地，基於矩陣乘法求最短路徑。給出步驟

們把求A →E 的最短路分解為四個階段A →B →C→D →E 來求解。每一個階段可以用一個矩陣來表示，這個矩陣稱為權矩陣。相鄰階段的路徑可以用權矩陣的乘積來表示。但這里的矩陣乘法和普通矩陣乘積運算的區別是:普通矩陣乘積其對應元素是相應元素乘積的代數和,這里把元素相乘改為相加,元素的代數和改為取小運算,如果不同層節點間沒有連接,則視它們之間的距離為無窮大. 如果是求極大,改為取大運算,此時如果不同層節點間沒有連接，則視它們的距離為0。
如下：
由A地到B地的距離可表示為：A[2 5 8]
由B地到C地的權矩陣可表示為
[3，6，5；7，10，8；4，9，6]
因此由A到C的權矩陣為[2，5，8][3，6，5；7，10，8；4，9，6]＝[5，8，7]
因此由A到D的權矩陣為[5，8，7)][7，5；3，4；5，2]＝[11 ，9]
由A→E的權矩陣為：[11 ，9][4，2)]=[15,11]
因此從家裡到學校的最短距離為11百米，最近的路徑為從A地出發經過B1地C1地D2地到達E地。

下面我們給出基於「矩陣乘法」求解最短路的演算法:
第一階段:計算出圖中從起始點到終點最短路的長度.
step1 劃分出該網路圖中的層次關系(網路劃分為N 層,起點為第一層,終點為第N 層) ;
step2 依次給出從第i 層到第i + 1 層的權矩陣( i= 1 ,2 , …, N21) ; (若第i 層有m 個頂點;第i + 1 層有n
個頂點, 則從第i 層到第i + 1 層的權矩陣為m *n
階) .
step3 按照我們定義的矩陣乘法計算出最短路的
數值.
第二階段:尋找最短路所經過的中間點.
(利用第一階段中step2 的數據) 計算出從第i 層到
終點的最短路, 對比與i21 層到終點的最短路, 從而確
定出第i 層上最短路所經過的頂點( i = 2 , …, N21) .

B. 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，改培2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題

C. 最短路徑的解決方法

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」， 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有：
Dijkstra演算法
SPFA演算法Bellman-Ford演算法
Floyd演算法Floyd-Warshall演算法
Johnson演算法
A*演算法
所謂單源最短路徑問題是指：已知圖G=（V，E），我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。
首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那麼，從vs沿P到vi的路是從vs到vi的最短路。

D. 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

A*（A-Star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。

公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

E. 數學最短路徑問題最方便的解法是什麼

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」 ，有時被簡稱作「路徑演算法」 。最常用 的路徑演算法有： Dijkstra 演算法、 A*演算法、 SPFA 演算法、 Bellman-Ford 演算法和 Floyd-Warshall 演算法， 本文主要介紹其中的三種。 最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩 結點之間的最短路徑。 演算法具體的形式包括： 確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的 問題。 在無向圖中該問題與確定起點的問題完全等同， 在有向圖中該問題等同於把所有路徑 方向反轉的確定起點的問題。 確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。 全局最短路徑問題：求圖中所有的最短路徑。 Floyd 求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度 O(V^3)。 Floyd-Warshall 演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法， 可以正確處理有向圖或負權的最短路徑問題。 Floyd-Warshall 演算法的時間復雜度為 O(N^3)，空間復雜度為 O(N^2)。 Floyd-Warshall 的原理是動態規劃： 設 Di,j,k 為從 i 到 j 的只以(1..k)集合中的節點為中間節點的最短路徑的長度。 若最短路徑經過點 k，則 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路徑不經過點 k，則 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 Floyd-Warshall 演算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由點 i 到點 j 的代價，當 Di,j 為∞表示兩點之間沒有任何連接。 Dijkstra 求單源、無負權的最短路。時效性較好，時間復雜度為 O（V*V+E） 。 源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV） 。 當是稀疏圖的情況時，此時 E=V*V/lgV，所以演算法的時間復雜度可為 O（V^2） 。若是斐波那 契堆作優先隊列的話，演算法時間復雜度，則為 O（V*lgV + E） 。 Bellman-Ford 求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路） ，時效性較好，時間復雜 度 O（VE） 。 Bellman-Ford 演算法是求解單源最短路徑問題的一種演算法。 單源點的最短路徑問題是指：給定一個加權有向圖 G 和源點 s，對於圖 G 中的任意一點 v， 求從 s 到 v 的最短路徑。 與 Dijkstra 演算法不同的是，在 Bellman-Ford 演算法中，邊的權值可以為負數。設想從我們可以 從圖中找到一個環路（即從 v 出發，經過若干個點之後又回到 v）且這個環路中所有邊的權 值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處 理這個負環路，程序就會永遠運行下去。而 Bellman-Ford 演算法具有分辨這種負環路的能力。 SPFA是 Bellman-Ford 的隊列優化，時效性相對好，時間復雜度 O（kE）（k<<V） 。 。 與 Bellman-ford 演算法類似， SPFA 演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖 中其它所有節點的最短路徑。所不同的是，SPFA 演算法通過維護一個隊列，使得一個節點的 當前最短路徑被更新之後沒有必要立刻去更新其他的節點， 從而大大減少了重復的操作次數。 SPFA 演算法可以用於存在負數邊權的圖，這與 dijkstra 演算法是不同的。 與 Dijkstra 演算法與 Bellman-ford 演算法都不同，SPFA 的演算法時間效率是不穩定的，即它對於不 同的圖所需要的時間有很大的差別。 在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度 僅為 O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為 Bellman-ford 演算法，其時間復雜度為 O(VE)。 SPFA 演算法在負邊權圖上可以完全取代 Bellman-ford 演算法， 另外在稀疏圖中也表現良好。 但是 在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的 Dijkstra 演算法，以及 它的使用堆優化的版本。通常的 SPFA 演算法在一類網格圖中的表現不盡如人意。 

F. 網格中如何求任意兩點間的最短路徑 matlab演算法

function [L,Z]=dijkstra(W,S,T)
%用 Dijkstra 演算法求最短路徑
% 演算法
% 1. 對每個點I指定一個離點S的距離初始值L(I). 在始點S的值為零, 即L(S)=0，其它點的值為Inf.
% 2. 所有的點標記為未走訪的. 置始點S為當前點C.
% 3. 對於當前點C, 考慮它的所有未走訪的相鄰點J, 並更新J的距離值為
% L(J)=min(L(J), L(C)+W(C,J))
% 4. 把當前點C標記為走訪過的點. 走訪過的點C的距離L(C)就是點S到C的最短距離, 而且以後不再檢查走訪過得點了.
% 5. 如果所有的點都是走訪過的點, 完成. 不然, 把未走訪的點中具有最小距離值的點作為下一個當前點C, 轉
N=length(W(:,1));%頂點數
W(find(W==0))=inf;
L=Inf*ones(1,N);
L(S)=0;%L賦初值，在S點為0，其它點為Inf
C=S; %當前點為始點S
Q=1:N;% 未走訪的頂點集
Z=S*ones(1,N);
Z(S)=0;% Z賦初值,因始點 S 無父親點,故把 S 點的Z值改為0
for K=1:N % 更新 L 和 Z 的循環
Q=setdiff(Q,C); %Matlab自帶函數，顯示Q中除了C之外的點集，即當前點 C 未走訪的點集
[L(Q),ind]=min([L(Q);L(C)+W(C,Q)]);%當前點C已走訪了所有的相鄰的未走訪的點，找出與C相鄰的距離最短的點，記錄最短距離和結點的索引值，更新 L
%如果L(Q)
Z(Q(find(ind==2)))=C; %更新Z, 找出Q中索引值為2的結點，將其父親結點更新為C,至此可以確定C已是走訪過的點了
if T&C==T %若 C 點是終點 T, 不用再計算到其它未走訪的點的最短路徑.先判斷C==T，再判斷&
L=L(T); %最短路徑長度；
road=T;%最短路徑終點；
while T~=S%追溯最短路徑上的點
T=Z(T); %從終點往前尋找其父親結點
road=[road,T]; %從終點開始倒序記錄最短路徑上的結點
end
Z=road(length(road):-1:1); %顛倒次序；
return;
end;
[null, mC]=min(L(Q));
if null==Inf
% disp('到值是Inf的點的路不通！');
Z(find(L==Inf))=nan; %NaN或者nan都是「非數」的意思，「0/0」、「∞/∞」、「0*∞」都會產生這種結果
return;
else
C=Q(mC);% 把未走訪的點集Q中與始點距離最近的點作為新的當前點C;
end
end
end