『壹』 圖論中求任意兩點之間的最短路徑用lingo怎麼實現，求lingo源程序
請參考：（10個點的最短路徑），源頂點編號為10，
!最短路問題;
model:
data:
n=10;
enddata
sets:
cities/1..n/: F; !10個城市;
roads(cities,cities)/
1,2 1,3
2,4 2,5 2,6
3,4 3,5 3,6
4,7 4,8
5,7 5,8 5,9
6,8 6,9
7,10
8,10
9,10
/: D, P;
endsets
data:
D=
6 5
3 6 9
7 5 11
9 1
8 7 5
4 10
5
7
9;
enddata
F(n)=0;
@for(cities(i) | i #lt# n:
F(i)=@min(roads(i,j): D(i,j)+F(j));
);
!顯然，如果P(i,j)=1,則點i到點n的最短路徑的第一步是i --> j，否則就不是。
由此，我們就可方便的確定出最短路徑;
@for(roads(i,j):
P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0)
);
end
結果是，
F( 1) 17.00000
F( 2) 11.00000
F( 3) 15.00000
F( 4) 8.000000
F( 5) 13.00000
F( 6) 11.00000
F( 7) 5.000000
F( 8) 7.000000
F( 9) 9.000000
F( 10) 0.000000
『貳』 最短路徑 - Dijkstra演算法
演算法每次都查找距離起始點最近的點，那麼剩下的點距離起始點的距離一定比當前點大。
1.選定A節點並初始化，如上述步驟3所示
2.執行上述 4、5兩步驟，找出U集合中路徑最短的節點D 加入S集合，並根據條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合
3.這時候 A->B, A->C 都為3，沒關系。其實這時候他倆都是最短距離，如果從演算法邏輯來講的話，會先取到B點。而這個時候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) ，如圖所示這時候A->B距離 其實為 A->D->B
思路就是這樣，往後就是大同小異了
演算法結束
（圖片來源於網路）
Dijkstra演算法保證能找到一條從初始點到目標點的最短路徑，只要所有的邊都有一個非負的代價值。在上圖中，粉紅色的結點是初始結點，藍色的是目標點，而類菱形的有色區域則是Dijkstra演算法掃描過的區域。顏色最淡的區域是那些離初始點最遠的，因而形成探測過程（exploration）的邊境（frontier）。因而Dijkstra演算法可以找到一條最短的路徑，但是效率上並不高。
數據結構--Dijkstra演算法最清楚的講解
『叄』 matlab求最短路，運行dijkstra函數
在使用Matlab求解最短路徑問題時，可以藉助Dijkstra演算法。首先，打開Matlab環境，運行或直接按Win+R鍵，輸入notepad，將以下代碼復制進去：
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [d,DD]=dijkstra(D,s) % Dijkstra最短路演算法Matlab程序用於求從起始點s到其它各點的最短路 % D為賦權鄰接矩陣 % d為s到其它各點最短路徑的長度; % DD記載了最短路徑生成樹 [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0; dd=zeros(1,m); dd(1,s)=1; y=s; DD=zeros(m,m); DD(y,y)=1; counter=1; while length(find(dd==1))
接著，將該文件保存為dijkstra.m，保存路徑最好選擇Matlab的工作路徑。此文件保存後，即可在Matlab中調用dijkstra函數來計算最短路徑。在實際應用中，輸入的D矩陣應為賦權鄰接矩陣，表示圖中各節點之間的連接關系和權重。通過運行dijkstra函數，可以得到從起始點s到其他所有節點的最短路徑長度和最短路徑生成樹。
在編寫dijkstra.m文件時，需要注意以下幾點：
1. D矩陣的構建。根據實際問題，構建賦權鄰接矩陣D。矩陣中的元素D(i,j)表示從節點i到節點j的邊權值，若無直接連接，則設為無窮大。
2. 起始點s的選擇。確定起始節點s，作為求解最短路徑的起點。
3. 演算法執行流程。通過while循環不斷更新最短路徑，直到找到所有節點的最短路徑。
通過合理設置D矩陣和起始點s，可以有效地利用Dijkstra演算法求解復雜的最短路徑問題。值得注意的是，Dijkstra演算法適用於無負權邊的情況，因此在實際應用中需確保輸入數據的正確性。
在應用過程中，可以結合具體問題，對dijkstra函數進行適當修改和擴展，以適應不同的需求。同時，Matlab提供了豐富的繪圖功能，可以在求得最短路徑後，繪制出路徑圖，直觀地展示最短路徑的走向。
總之，通過編寫和使用dijkstra.m文件，可以方便地在Matlab中求解最短路徑問題，為實際應用提供了有力的支持。