Ⅰ 求A到B之間的最短路徑，怎麼獲取
問題：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法，另外還有著名的啟發式搜索演算法A*，不過A*准備單獨出一篇，其中Floyd演算法可以求解任意兩點間的最短路徑的長度。任意一個最短路演算法都是基於這樣一個事實：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點到B。
(1) 迪傑斯特拉(Dijkstra)演算法按路徑長度(看下面表格的最後一行，就是next點)遞增次序產生最短路徑。先把V分成兩組：
S：已求出最短路徑的頂點的集合
V-S=T：尚未確定最短路徑的頂點集合
將T中頂點按最短路徑遞增的次序加入到S中，依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值或是從V0經S中頂點到Vk的路徑權值之和（反證法可證，說實話，真不明白哦）。
(2) 求最短路徑步驟
初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值， 若存在<V0,Vi>，為<V0,Vi>弧上的權值（和SPFA初始化方式不同），若不存在<V0,Vi>，為Inf。
從T中選取一個其距離值為最小的頂點W(貪心體現在此處)，加入S(注意不是直接從S集合中選取，理解這個對於理解vis數組的作用至關重要)，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個並列for循環，使用最小點更新）。
重復上述步驟，直到S中包含所有頂點，即S=V為止（說明最外層是除起點外的遍歷）。
Ⅱ 利用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演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、
Ⅳ 設計一個演算法，計算出給定二叉樹中任意2 個結點之間的最短路徑。
對於樹中的每一個節點，維護一個dis[i]，代表i節點到根節點路徑長度。
寫一個Lca(x,y)函數，用來返回x節點和y節點的最近公共祖先是哪一個節點。
樹中最近公共祖先很很多種求法：
在信息學競賽中一般使用的是倍增法，或者動態樹。
如果你只是寫一個普通的程序那麼你可以樸素的取查找。當然程序會相對應的慢一點。
演算法流程如下：
k=Lca(x,y);
dist=dis[x]+dis[y]-2*dis[k];//畫個圖就理解拉。
Ⅳ 用弗洛伊德演算法求最短路徑
是地信的題吧，先給你說v1怎麼求，
先找出v1能去的最近的點，為V2，
如果S1i>S12+S2i
修改V1到Vi的距離為S12+S2i
然後去掉V2，在其餘的點中找距V1最近的，按上面的方法修改
最後得到V1與其他各點的最短距離
同樣的方法求出到其他點的最短距離
Ⅵ floyd演算法求最短路徑
Floyd演算法適用於APSP(AllPairsShortestPaths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單
缺點：時間復雜度比較高，不適合計算大量數據。
時間復雜度:O(n^3)；空間復雜度:O(n^2)；
任意節點i到j的最短路徑兩種可能：
直接從i到j；
從i經過若干個節點k到j。
map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。
步驟：
第1步：初始化map矩陣。
矩陣中map[i][j]的距離為頂點i到頂點j的權值；
如果i和j不相鄰，則map[i][j]=∞。
如果i==j，則map[i][j]=0;
第2步：以頂點A(假設是第1個頂點)為中介點，若a[i][j] > a[i][1]+a[1][j]，則設置a[i][j]=a[i][1]+a[1][j]。
Ⅶ floyd演算法求最短路徑怎麼用
Dijkstra演算法
1.定義概覽
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。注意該演算法要求圖中不存在負權邊。
問題描述：在無向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）
2.演算法描述
1)演算法思想：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
2)演算法步驟：
a.初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其餘頂點}，若v與U中頂點u有邊，則<u,v>正常有權值，若u不是v的出邊鄰接點，則<u,v>權值為∞。
b.從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值的頂點k的距離加上邊上的權。
d.重復步驟b和c直到所有頂點都包含在S中。
Ⅷ 求寫最短路徑演算法。由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) .
Ⅸ 數據結構中迪傑斯特拉演算法求最短路徑
dijkstra演算法本身求的是一點到其他所有點的最短距離，而不是具體的路徑，因此還需要一個額外的數組來記錄推導最短距離的過程中經過的每一個結點，這樣才能求出這個最短距離的具體路徑。