圖論與最短路在數學建模中的應用

一、圖論模型

• 圖 $G=(V,E)$

  • $V$：頂點集合
  • $E$：邊集合

• 每條邊 $(u,v)$ 賦予權值 $w(u,v)$，可用 鄰接矩陣 或 鄰接表 表示。

二、最短路問題的數學形式

目標：尋找從源點 $s$ 到目標點 $t$ 的路徑 $P$，使得路徑權值和最小。

$$d(s,t)=\underset{P\in \mathcal{P}(s,t)}{\min }\sum _{(u,v)\in P}w(u,v)$$

其中：

• $\mathcal{P}(s,t)$：所有從 $s$ 到 $t$ 的可行路徑集合
• $w(u,v)$：邊的權值

三、最短路算法

1. Dijkstra 算法

   • 適用于 非負權圖
   • 貪心策略：逐步擴展源點集合，選取最近節點

2. Bellman-Ford 算法

   • 允許 負權邊

   • 動態規劃思想：

     dk(v)=min?{dk?1(v),min?(u,v)∈E(dk?1(u)+w(u,v))} d_k(v) = \min\{ d_{k-1}(v), \min_{(u,v)\in E} (d_{k-1}(u)+w(u,v)) \} dk?(v)=min{dk?1?(v),(u,v)∈Emin?(dk?1?(u)+w(u,v))}

   • 可檢測負環

3. Floyd-Warshall 算法

   • 適合 全源最短路

   • 遞推公式：

     $$d^{(k)}(i,j)=\min (d^{(k?1)}(i,j),d^{(k?1)}(i,k)+d^{(k?1)}(k,j))$$

四、MATLAB 實現

1. Dijkstra 算法

INF = 1e9;
G = [0 4 2 INF INF;4 0 1 5 INF;2 1 0 8 10;INF 5 8 0 2;INF INF 10 2 0];n = size(G,1);
start = 1;
dist = ones(1,n)*INF;
visited = zeros(1,n);
dist(start) = 0;for i = 1:n[~, u] = min(dist + visited*INF);visited(u) = 1;for v = 1:nif ~visited(v) && dist(u)+G(u,v) < dist(v)dist(v) = dist(u)+G(u,v);endend
enddisp('Dijkstra: 起點到各點的最短距離：');
disp(dist);

2. Bellman-Ford 算法

INF = 1e9;
edges = [1 2 4;1 3 2;2 3 1;2 4 5;3 2 1;3 4 8;3 5 10;4 5 2];n = 5;   % 節點數
m = size(edges,1);
start = 1;
dist = ones(1,n)*INF;
dist(start) = 0;% 松弛操作 n-1 次
for k = 1:n-1for i = 1:mu = edges(i,1);v = edges(i,2);w = edges(i,3);if dist(u) + w < dist(v)dist(v) = dist(u) + w;endend
end% 檢測負環
hasNegativeCycle = false;
for i = 1:mu = edges(i,1);v = edges(i,2);w = edges(i,3);if dist(u) + w < dist(v)hasNegativeCycle = true;end
enddisp('Bellman-Ford: 起點到各點的最短距離：');
disp(dist);
if hasNegativeCycledisp('圖中存在負權回路！');
end

3. Floyd-Warshall 算法

INF = 1e9;
G = [0 4 2 INF INF;4 0 1 5 INF;2 1 0 8 10;INF 5 8 0 2;INF INF 10 2 0];n = size(G,1);for k = 1:nfor i = 1:nfor j = 1:nif G(i,k)+G(k,j) < G(i,j)G(i,j) = G(i,k)+G(k,j);endendend
enddisp('Floyd-Warshall: 所有點對最短路徑矩陣：');
disp(G);

五、總結

• 建模方法：用圖表示系統，用邊權表示代價

• 最短路問題目標：找到權和最小路徑

• 算法選擇：

  • 單源非負權：Dijkstra
  • 單源含負權：Bellman-Ford
  • 全源最短路：Floyd-Warshall