架構
- 一、最短路問題概述
- 二、單源最短路問題
-
- 2.1 Dijkstra算法
-
- 2.1.1 算法流程
- 2.1.2 求解某城到各個城鎮距離（無向圖）
- 2.1.3 求解某兩城間最小距離
- 2.2 數學規劃法
-
- 2.2.1數學規劃法求解最短路問題
-
- 有向圖最短路問題
- 無向圖最短路問題
- 三、多源最短路問題
一、最短路問題概述
最短路問題即是尋找同一個網絡中的兩個節點之間的一條通路，使“消耗”在這條通路上的權重最小的問題，這裡的權重可替換為最小距離、最短時間、最小成本等。常見的最短路問題可以展現為如下形式：“已知連接配接若幹個城鎮的鐵路網絡，在這個網絡的兩個指定城鎮間，找一條最短鐵路線。”
在明确最短路問題的定義之後，我們接下來需要将最短路問題通過數學形式表示出來。最短路問題發生在二維空間的一張“網絡”中，故需要包含三方面資訊：節點資訊（存在有哪些城鎮？）、邊資訊（連接配接各個城鎮的鐵路有哪些？）、權重資訊（各個城鎮之間的鐵路長度是多少？）。我們使用鄰接矩陣将上述三方面統一的表示在一個矩陣中：
顯然鄰接矩陣元素 w i j w_{ij} wij儲存着 i i i與 j j j節點之間通路的資訊（是否存在通路？通路的權重是多少？）。當節點間不存在通路連接配接時，我們使用0或無窮作為該位置的元素值，然而事實上，直接使用無窮指派是更直接的做法。注意：在有向圖問題中，鄰接矩陣是一個主對角線為0的方陣，此時 w i j w_{ij} wij與 w j i w_{ji} wji意義不同；而在無向圖問題中，鄰接矩陣是一個對角陣。
二、單源最短路問題
指定一個節點作為起點（源），求其到其餘各節點的最短距離，這樣的問題被稱為單源最短路問題。解決單源最短路的方法大體分為兩種：Dijkstra算法、數學規劃法。
2.1 Dijkstra算法
Dijkstra算法的思想核心是：任一節點到起點的最短路徑在一定程度上是相似的，且越靠近起點的位置路徑的相似程度就越高。這個思想不難了解，小明與小張住在一個小區，小明住在5号樓3單元3樓，小張住在5号樓2單元6樓，那麼小明與小張從小區門口到自家樓下這段路的最短路徑是完全一樣的。由此我們可以推斷：起點到某一節點的最短路徑有很大機率是在已存在的最短路徑上延伸的。
2.1.1 算法流程
我們已經知道，起點到各個節點的最短路徑在開始的數個節點是大機率相似的，我們稱這部分相似的節點集合為 P P P集（我們也可以叫它“已經曆點集”），顯然 P P P集是由數個與起點直接/間接存在最短路徑的優質節點組成的。我們需要做的是不斷将 P ˉ \bar{P} Pˉ集（未經曆點集）中的節點 x x x到起點的直接距離 l 1 l_{1} l1（原距離）與 x x x通過 P P P集作為中轉到達起點的間接距離 l 2 l_{2} l2（延伸距離）進行比較，選擇二者中較小者作為該節點下一次疊代的路徑長度，在如此周遊一遍 P ˉ \bar{P} Pˉ集後，選擇其中路徑最短者納入 P P P集組成已存在的最短路徑，進行下一輪的比較，如此往複直至所有節點被納入 P P P中。
Dijkstra算法的流程可以通過以下方式進行描述，但是稍有些晦澀：
此處 u 0 u_{0} u0是指起點， v v v指未經曆的節點， S i S_{i} Si指 P P P集， S ˉ i \bar{S}_{i} Sˉi指第 i i i次疊代産生的 P ˉ \bar{P} Pˉ集， V V V集是節點集， ∣ V ∣ |V| ∣V∣指節點集中節點個數， l ( x ) l(x) l(x)指 x x x節點到起點的距離。
2.1.2 求解某城到各個城鎮距離（無向圖）
例1 某公司在六個城市 c 1 , c 2 , . . . , c 6 , c_{1},c_{2},...,c_{6}, c1,c2,...,c6,中有分公司，從 c i c_{i} ci到 c j c_{j} cj的直接航程票價記在下述矩陣的 ( i , j ) (i, j) (i,j) 位置上（ ∞ \infty ∞表示無直接航路）。請幫助該公司設計一張城市 c 1 c_{1} c1 到其它城市間的票價最便宜的路線圖。
[ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 ] \left[\begin{array}{cccccc}{0} & {50} & {\infty} & {40} & {25} & {10} \\ {50} & {0} & {15} & {20} & {\infty} & {25} \\ {\infty} & {15} & {0} & {10} & {20} & {\infty} \\ {40} & {20} & {10} & {0} & {10} & {25} \\ {25} & {\infty} & {20} & {10} & {0} & {55} \\ {10} & {25} & {\infty} & {25} & {55} & {0}\end{array}\right] ⎣⎢⎢⎢⎢⎢⎢⎡050∞4025105001520∞25∞1501020∞4020100102525∞20100551025∞25550⎦⎥⎥⎥⎥⎥⎥⎤
首先規定幾個變量：
| 變量名 | 意義 |
|---|---|
| p b ( i ) pb_{(i)} pb(i) | 表示 i i i頂點是否已經成為 P P P集的成員，0-1邏輯表示 |
| i n d e x 1 ( i ) index1_{(i)} index1(i) | 節點納入 P P P集的順序。 i i i位置上存放着第 i i i個納入 P P P集的節點序号 |
| i n d e x 2 ( i ) index2_{(i)} index2(i) | 存放着路徑中 i i i節點前一節點的序号資訊，通過該變量可以找出路徑連線 |
| d ( i ) d_{(i)} d(i) | i i i位置上存放着由起點到第 i i i點最短通路的值 |
下面直接給出Matlab求解代碼：
%%%%%%%%鄰接矩陣初始化%%%%%%%%%%
clc,clear
a=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';%無向圖，鄰接矩陣為對角陣
a(find(a==0))=inf;
%%%%%%%%%初始距離設定，無需更改%%%%%%%%%%
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;
temp=1;%起點的設定，需要更改！
%%%%%%Dijkstra算法部分，無需更改%%%%%%
while sum(pb)<length(a)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp];
temp2=find(d(index1)==d(temp)-a(temp,index1));
index2(temp)=index1(temp2(1));
end
d, index1, index2
2.1.3 求解某兩城間最小距離
對于已知網絡的鄰接矩陣（有向/無向圖）問題，參考司守奎模組化書有以下函數可以直接給出某兩城間最短距離。
function [mydistance,mypath]=mydijkstra(a,sb,db);
% 輸入： a—鄰接矩陣(aij)是指i到j之間的距離，可以是有向的
% sb—起點的标号, db—終點的标号
% 輸出： mydistance—最短路的距離, mypath—最短路的路徑
n=size(a,1); visited(1:n) = 0;
distance(1:n) = inf; % 儲存起點到各頂點的最短距離
distance(sb) = 0; parent(1:n) = 0;
for i = 1: n-1
temp=distance;
id1=find(visited==1); %查找已經标号的點
temp(id1)=inf; %已标号點的距離換成無窮，這樣就可以隻在未經曆點集中尋找最小值了
[t, u] = min(temp); %找标号值最小的頂點
visited(u) = 1; %标記已經标号的頂點，将最小點納入已經曆點集中
id2=find(visited==0); %查找未标号的頂點
for v = id2
if a(u, v) + distance(u) < distance(v)
distance(v) = distance(u) + a(u, v); %修改标号值
parent(v) = u;
end
end
end
mypath = [];
if parent(db) ~= 0 %若終點不是直接連接配接到起點的
t = db; mypath = [db]; %開始列印路徑
while t ~= sb %若該節點不是起點
p = parent(t);
mypath = [p mypath]; %逐個回溯列印路徑
t = p;
end
end
mydistance = distance(db);
return
2.2 數學規劃法
我們也可以從數學規劃的角度來解決單源最短路問題，我們仍然使用鄰接矩陣來表示網絡的資訊
W i j = { Weight, v i v j ∈ E ∞ ， Others \mathcal{W}_{i j}=\left\{\begin{array}{c}{\text { Weight,\qquad}v_{i} v_{j} \in E} \\ { \infty，\qquad\text { Others}}\end{array}\right. Wij={ Weight,vivj∈E∞， Others
其中 E E E表示網絡中通路的集合。若要求得某個網絡中1節點到 n n n節點的最短路徑，我們可以建立以下數學規劃模型：
決策變量 x i j x_{ij} xij是邏輯變量，對于通路 v i v j v_{i} v_{j} vivj若它存在于1節點到 n n n節點的最短路徑上 x i j x_{ij} xij值為1，反之為0。目标函數也很好了解，使路徑上所有通路的權值最小即是求得最短路徑。而第一個限制條件的了解稍複雜些，它限制了從起點到結束點的路徑是一條不重複的、沒有分叉的連線。
我們首先對限制的左側進行分析:
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i ∈ E n x j i \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i} vivj∈Ej=1∑nxij−vjvi∈Ej=1∑nxji
∑ j = 1 v i v j ∈ E n x i j \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j} ∑vivj∈Ej=1nxij對 j j j進行累加，表示的是以 i i i城作為起點的通路個數之和；同理 ∑ j = 1 v j v i ∈ E n x j i \sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i} ∑vjvi∈Ej=1nxji表示的是以 i i i城作為終點的通路個數之和。是以限制左側的意義是：以 i i i節點作為起點的通路個數與以 i i i節點作為終點的通路個數之差。
根據常識我們知道，當i節點作為整個路徑的始端時，隻有1條通路以i城作為起點，沒有通路以i城作為終點，即 ∑ j = 1 v i v j ∈ E n x i j = 1 \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}=1 ∑vivj∈Ej=1nxij=1， ∑ j = 1 v j v i ∈ E n x j i = 0 \sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i}=0 ∑vjvi∈Ej=1nxji=0。故我們可以得到：
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i ∈ E n x j i = 1 i = 1 \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i}=1\qquad i=1 vivj∈Ej=1∑nxij−vjvi∈Ej=1∑nxji=1i=1
同理，當i節點作為整個路徑的末端時，沒有通路以i城作為起點，隻有1條通路以i城作為終點，即 ∑ j = 1 v i v j ∈ E n x i j = 0 \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}=0 ∑vivj∈Ej=1nxij=0， ∑ j = 1 v j v i ∈ E n x j i = 1 \sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i}=1 ∑vjvi∈Ej=1nxji=1，易得：
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i ∈ E n x j i = − 1 i = n \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i}=-1\qquad i=n vivj∈Ej=1∑nxij−vjvi∈Ej=1∑nxji=−1i=n
而當i節點作為一條不分叉路徑中間的一個節點時，以i城作為起點的通路數與以i城作為終點的通路數相等，即 ∑ j = 1 v i v j ∈ E n x i j = ∑ j = 1 v j v i ∈ E n x j i \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}=\sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i} ∑vivj∈Ej=1nxij=∑vjvi∈Ej=1nxji，亦即
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i ∈ E n x j i = 0 i ≠ 1 , n \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i} \in E}^{n} x_{j i}=0 \qquad i\neq1,n vivj∈Ej=1∑nxij−vjvi∈Ej=1∑nxji=0i=1,n
綜合上述結論，我們便得到了第一條限制：
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i = E n x j i = { 1 , i = 1 − 1 , i = n 0 , i ≠ 1 , n \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i}=E}^{n} x_{j i}=\left\{\begin{array}{ll}{1,} & {i=1} \\ {-1,} & {i=n} \\ {0,} & {i \neq 1, n}\end{array}\right. vivj∈Ej=1∑nxij−vjvi=Ej=1∑nxji=⎩⎨⎧1,−1,0,i=1i=ni=1,n
而當我們想求解某兩個節點 x 1 , x 2 ( x 1 , x 2 ∈ C ) x_{1},x_{2}(x_{1},x_{2}\in C) x1,x2(x1,x2∈C)之間的最短路徑時，隻需要相應的更改限制條件為下述形式即可：
∑ j = 1 v i v j ∈ E n x i j − ∑ j = 1 v j v i = E n x j i = { 1 , i = x 1 − 1 , i = x 2 0 , i ≠ x 1 , x 2 \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{i j}-\sum_{j=1 \atop v_{j} v_{i}=E}^{n} x_{j i}=\left\{\begin{array}{ll}{1,} & {i=x_{1}} \\ {-1,} & {i=x_{2}} \\ {0,} & {i \neq x_{1}, x_{2}}\end{array}\right. vivj∈Ej=1∑nxij−vjvi=Ej=1∑nxji=⎩⎨⎧1,−1,0,i=x1i=x2i=x1,x2
2.2.1數學規劃法求解最短路問題
規劃類問題使用 l i n g o lingo lingo求解會很友善，下面分别給出使用 l i n g o lingo lingo求解有向圖和無向圖最短路問題的示例。二者的思路整體一緻，但在鄰接矩陣和限制條件的構造上有細微的不同。
有向圖最短路問題
例2 使用 l i n g o lingo lingo求解 A — D A—D A—D的最短路問題。
直接給出 l i n g o lingo lingo求解代碼。
model:
sets:
cities/A,B1,B2,C1,C2,C3,D/;
roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,
B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;!隻有有通路的的需要有意義
endsets
data:
w=2 4 3 3 1 2 3 1 1 3 4;!按照序号順序賦權值
enddata
[email protected](cities); !城市的個數;
[email protected](roads:w*x);!目标函數
!!!!!!!!!!!限制條件部分!!!!!!!!!!!通過更改邏輯符号後的n與1的值可以自由設定起點與終點
@for(cities(i)|i #ne#1 #and# i #ne#n:@sum(roads(i,j):x(i,j))[email protected](roads(j,i):x(j,i)));
@sum(roads(i,j)|i #eq#1:x(i,j))=1;
@sum(roads(i,j)|j #eq#n:x(i,j))=1;
!可以省略一個限制條件，上一條限制已經限定了決策變量隻能取0或1
end
無向圖最短路問題
例3 使用 l i n g o lingo lingo求解 v 1 — v 11 v_{1}—v_{11} v1—v11的最短路。
注意無向圖的鄰接矩陣是一個對角陣， l i n g o lingo lingo代碼如下：
model:
sets:
cities/1..11/;
roads(cities,cities):w,x;
endsets
data:
w=0;
enddata
calc:
w(1,2)=2;w(1,3)=8;w(1,4)=1;
w(2,3)=6;w(2,5)=1;
w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;
w(4,7)=9;
w(5,6)=3;w(5,8)=2;w(5,9)=9;
w(6,7)=4;w(6,9)=6;
w(7,9)=3;w(7,10)=1;
w(8,9)=7;w(8,11)=9;
w(9,10)=1;w(9,11)=2;w(10,11)=4;
@for(roads(i,j):w(i,j)=w(i,j)+w(j,i));
@for(roads(i,j):w(i,j)[email protected](w(i,j) #eq# 0, 1000,w(i,j)));!相當于給無通路元素賦無窮大
endcalc
[email protected](cities); !城市的個數;
[email protected](roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#
n:@sum(cities(j):x(i,j))[email protected](cities(j):x(j,i)));
@sum(cities(j):x(1,j))=1;
@sum(cities(j):x(j,1))=0; !不能回到頂點1;
@sum(cities(j):x(j,n))=1;
@for(roads:@bin(x));
end
可以發現，在 l i n g o lingo lingo代碼中，無向圖問題比有向圖問題增加了一個限制條件
∑ j = 1 v i v j ∈ E n x j 1 = 0 \sum_{j=1 \atop v_{i} v_{j} \in E}^{n} x_{j 1}=0 vivj∈Ej=1∑nxj1=0
究其原因，是因為在使用 l i n g o lingo lingo編寫代碼時并沒有嚴格按照數學模型來構造限制條件，導緻在求解無向圖問題時傳回到原點的通路也會被納入求解範圍内，故需要加入限制條件進行限制。而有向圖在構造鄰接矩陣時規定了隻有下三角陣有意義，故不會出現這種問題。此處不必過分深究。
三、多源最短路問題
最常見的求解多源最短路問題的方法是Floyd算法，這部分内容日後補充。
[2019.9.2 補充] 這部分很簡單，就是求解圖中每一對節點之間的最短路。（開學了，暫時沒時間補。水一波……）