圖線路演算法
① 百度地圖的路徑搜索演算法
這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(BFS)、深度優先搜索演算法(DFS)、A* 演算法的優缺點。
關鍵詞:最短路徑演算法；廣度優先演算法；深度優先演算法；A*演算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路徑問題是地理信息系統（GIS）網路分析的重要內容之一，而且在圖論中也有著重要的意義。實際生活中許多問題都與「最短路徑問題」有關, 比如: 網路路由選擇, 集成電路設計、布線問題、電子導航、交通旅遊等。本文應用深度優先演算法，廣度優先演算法和A*演算法，對一具體問題進行討論和分析，比較三種算的的優缺點。
在地圖中最短路徑的搜索演算法研究中，每種演算法的優劣的比較原則主要遵循以下三點:[1]
(1)演算法的完全性：提出一個問題，該問題存在答案，該演算法能夠保證找到相應的答案。演算法的完全性強是演算法性能優秀的指標之一。
(2)演算法的時間復雜性: 提出一個問題，該演算法需要多長時間可以找到相應的答案。演算法速度的快慢是演算法優劣的重要體現。
(3)演算法的空間復雜性:演算法在執行搜索問題答案的同時，需要多少存儲空間。演算法佔用資源越少，演算法的性能越好。
地圖中最短路徑的搜索演算法:
1、廣度優先演算法
廣度優先演算法(Breadth-First-Search)，又稱作寬度優先搜索，或橫向優先搜索，是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型,Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。廣度優先演算法其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
廣度優先搜索演算法偽代碼如下：[2-3]
BFS(v)//廣度優先搜索G，從頂點v開始執行
//所有已搜索的頂點i都標記為Visited(i)=1.
//Visited的初始分量值全為0
Visited(v)=1;
Q=[];//將Q初始化為只含有一個元素v的隊列
while Q not null do
u=DelHead(Q);
for 鄰接於u的所有頂點w do
if Visited(w)=0 then
AddQ(w,Q); //將w放於隊列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
這里調用了兩個函數：AddQ(w,Q)是將w放於隊列Q之尾；DelHead(Q)是從隊列Q取第一個頂點，並將其從Q中刪除。重復DelHead(Q)過程，直到隊列Q空為止。
完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
時間復雜度：最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間復雜度為,其中|V|是節點的數目，而 |E| 是圖中邊的數目。
空間復雜度：因為所有節點都必須被儲存，因此BFS的空間復雜度為，其中|V|是節點的數目，而|E|是圖中邊的數目。另一種說法稱BFS的空間復雜度為O(B),其中B是最大分支系數，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。[4-5]
2、深度優先演算法
深度優先搜索演算法（Depth First Search）英文縮寫為DFS，屬於一種回溯演算法，正如演算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。[6]其過程簡要來說是沿著頂點的鄰點一直搜索下去，直到當前被搜索的頂點不再有未被訪問的鄰點為止，此時，從當前輩搜索的頂點原路返回到在它之前被搜索的訪問的頂點，並以此頂點作為當前被搜索頂點。繼續這樣的過程，直至不能執行為止。
深度優先搜索演算法的偽代碼如下：[7]
DFS(v) //訪問由v到達的所有頂點
Visited(v)=1;
for鄰接於v的每個頂點w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率比較低，在數據規模變大時，這種演算法就顯得力不從心了。[8]關於深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝，也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。
BFS:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是內存耗費量大（需要開大量的數組單元用來存儲狀態）。
DFS：對於解決遍歷和求所有問題有效，對於問題搜索深度小的時候處理速度迅速，然而在深度很大的情況下效率不高。
3、A*演算法
1968年的一篇論文，「P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968」。[9]從此，一種精巧、高效的演算法——A*演算法問世了，並在相關領域得到了廣泛的應用。A* 演算法其實是在寬度優先搜索的基礎上引入了一個估價函數,每次並不是把所有可擴展的結點展開,而是利用估價函數對所有未展開的結點進行估價, 從而找出最應該被展開的結點,將其展開,直到找到目標節點為止。
A*演算法主要搜索過程偽代碼如下：[10]
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的估價值;
將起點放入OPEN表;
while(OPEN!=NULL) //從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
endif
for(當前節點n 的每個子節點X)
算X的估價值;
if(X in OPEN)
if(X的估價值小於OPEN表的估價值)
把n設置為X的父親;
更新OPEN表中的估價值; //取最小路徑的估價值;
endif
endif
if(X inCLOSE)
if( X的估價值小於CLOSE表的估價值)
把n設置為X的父親;
更新CLOSE表中的估價值;
把X節點放入OPEN //取最小路徑的估價值
endif
endif
if(X not inboth)
把n設置為X的父親;
求X的估價值;
並將X插入OPEN表中; //還沒有排序
endif
end for
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
end while(OPEN!=NULL)
保存路徑，即 從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
A *演算法分析：
DFS和BFS在展開子結點時均屬於盲目型搜索，也就是說，它不會選擇哪個結點在下一次搜索中更優而去跳轉到該結點進行下一步的搜索。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用於問題規模不大的搜索問題中。而A*演算法與DFS和BFS這類盲目型搜索最大的不同，就在於當前搜索結點往下選擇下一步結點時，可以通過一個啟發函數來進行選擇，選擇代價最少的結點作為下一步搜索結點而跳轉其上。[11]A *演算法就是利用對問題的了解和對問題求解過程的了解, 尋求某種有利於問題求解的啟發信息, 從而利用這些啟發信息去搜索最優路徑.它不用遍歷整個地圖, 而是每一步搜索都根據啟發函數朝著某個方向搜索.當地圖很大很復雜時, 它的計算復雜度大大優於D ijks tr a演算法, 是一種搜索速度非常快、效率非常高的演算法.但是, 相應的A*演算法也有它的缺點.啟發性信息是人為加入的, 有很大的主觀性, 直接取決於操作者的經驗, 對於不同的情形要用不同的啟發信息和啟發函數, 且他們的選取難度比較大,很大程度上找不到最優路徑。
總結：
本文描述了最短路徑演算法的一些步驟，總結了每個演算法的一些優缺點，以及演算法之間的一些關系。對於BFS還是DFS，它們雖然好用，但由於時間和空間的局限性，以至於它們只能解決規模不大的問題，而最短或最少問題應該選用BFS,遍歷和求所有問題時候則應該選用DFS。至於A*演算法，它是一種啟發式搜索演算法，也是一種最好優先的演算法，它適合於小規模、大規模以及超大規模的問題，但啟發式搜索演算法具有很大的主觀性，它的優劣取決於編程者的經驗，以及選用的啟發式函數，所以用A*演算法編寫一個優秀的程序，難度相應是比較大的。每種演算法都有自己的優缺點，對於不同的問題選擇合理的演算法，才是最好的方法。
參考文獻：
[1]陳聖群,滕忠堅,洪親,陳清華.四種最短路徑演算法實例分析[J].電腦知識與技術(學術交流),2007(16):1030-1032
[2]劉樹林,尹玉妹.圖的最短路徑演算法及其在網路中的應用[J].軟體導刊,2011(07):51-53
[3]劉文海,徐榮聰.幾種最短路徑的演算法及比較[J].福建電腦，2008(02）:9-12
[4]鄧春燕.兩種最短路徑演算法的比較[J].電腦知識與技術，2008（12）：511-513
[5]王蘇男,宋偉,姜文生.最短路徑演算法的比較[J].系統工程與電子技術,1994(05)：43-49
[6]徐鳳生,李天志.所有最短路徑的求解演算法[J].計算機工程與科學,2006(12)：83-84
[7]李臣波,劉潤濤.一種基於Dijkstra的最短路徑演算法[J].哈爾濱理工大學學報,2008(03)：35-37
[8]徐鳳生.求最短路徑的新演算法[J].計算機工程與科學,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亞松.VC++實現基於Dijkstra演算法的最短路徑[J].科技信息(科學教研),2008(18)：36-37
[11] 楊長保,王開義,馬生忠.一種最短路徑分析優化演算法的實現[J]. 吉林大學學報(信息科學版),2002(02)：70-74
② 用Dijkstra演算法求圖中從頂點a到其他各頂點間的最短路徑，並寫出執行演算法過程中各步的狀態。
迪克斯加（Dijkstra）演算法(最短路徑演算法)是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中任意兩個頂點之間的最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
迪科斯徹演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0）， 同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到v的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到u的路徑。這條路徑的長度是d+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d達到它最終的值的時候每條邊(u,v)都只被拓展一次。
演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找權值最小的點為node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各點的權值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.
③ 利用Dijkstra演算法求有向網圖的最短路徑
v1到v2：10為最短路徑；
v1到v3：7為最短路徑；
v1到v4:8為最短路徑；
v1到v5：v1->
v2
->
v5
=10+6=
16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15;
15為最短路徑；
v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13為最短路徑；
v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；
v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35為最短路徑
④ 圖文解析 | Dijkstra單源最短路徑演算法
給定 加權有向圖 G=(V,E,W)，每條邊的權值w為 非負數 ，表示兩個頂點間的距離。
源點s∈V。
求：從s出發到其他各個頂點的最短路徑。
如上圖所示，以1為源點，計算到其餘各個頂點的最短距離（我已用紅線標出）。下面列出了最終解：
S集合 ：當從s到x（x ∈V ）的最短路徑找到時，則x ∈S。當所有頂點都進入S集合時，演算法結束。
初始：S=｛s｝，當S=V時演算法結束。
從s到u相對於S的最短路徑 ：指從s到u且僅經過S中頂點的最短路徑。
dist[u]:從s到u相對於S的最短路徑長度
short[u]:從s到u最短路徑的長度（演算法最終解）
dist[u] ≥ short[u]
Dijkstra演算法採用貪心演算法模式，演算法過程就是通過計算dist[u],不斷擴充S集合，同時dist[u]會不斷優化改善，直到dist[u] = short[u]，並將其放到S中，當所有頂點都放入S集合時，演算法結束。
輸入：加權有向圖G=(V,E,W)
V={1,2,…,n}, s=1
輸出：從s到每個頂點的最短路徑
輸入：G=(V,E,W)，源點1
V={1,2,3,4,5,6}
初始S集合只有1，計算直接從1能到達的頂點的距離，其他不能從1號頂點直接到達的頂點都記為無窮大。雀輪睜此時從dist[u]里找出最短距離的頂點（6號），並將其放進S集合。
S={1}
dist[1] = 0
dist[2] = 10
dist[6 ] = 3
dist[3] = ∞
dist[4] = ∞
dist[5] = ∞
當把6號頂點放進S集合後，經由6號頂點出發到達的頂點的最短距離可能會被優化更新，因為該演算法的思想很「貪心」，誰更短我要誰！比如1->6->2要比1->2距離更短，所以dist[2]被更頃歲新為5，從專業術語上講，這個「更新」過程叫做鬆弛，其他點同理。然桐喚後從dist[u]里找出最短的路徑的那個頂點（5號），並放進S集合里。
S={1,6}
dist[1] = 0
dist[6] = 3
dist[2] = 5
dist[4] = 9
dist[5] = 4
dist[3] = ∞
後面的操作步驟其實就是重復上面的操作。即當S集合里有個新的頂點後，就可能會更新其他點的最短距離，更新一遍後，找出當前最短距離的dist[u]，並將該頂點放進S集合。後面不重復闡述。
S={1,6,5}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = ∞
S={1,6,5,2}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4,3}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
當有向圖中的所有頂點都進入了S集合後，演算法結束，此時的dist[u]的值其實就是最初我們找出的那個最終解short[u]，所以，演算法結束時，dist[u]=short[u],得到最終解。