A-level 數學/MEI/D1/網路

網路是加權圖，它們的邊與它們關聯的權重。網路對於對地理問題進行建模很有用（儘管它們還有許多其他用途）。

網路

網路有一個稱為最小生成樹的路徑，它是連線網路中每個節點的 via 邊的最短路徑。有兩種生成最小生成樹的演算法：克魯斯卡爾演算法和普里姆演算法，在本頁末尾，您應該能夠以圖形形式使用兩種演算法，並以表格形式使用普里姆演算法。

最後，您還應該能夠使用迪傑斯特拉演算法來查詢兩點之間的最短路線。

演算法

最小生成樹

克魯斯卡爾演算法

---

1. 選擇網路中最短的邊。
2. 選擇網路中未連線已經建立路徑的節點之間的下一個最短邊。
3. 重複步驟 2，直到選擇了 n-1 條邊（其中 n 是網路中節點的數量）。

以下是在維基百科上的一個示例：克魯斯卡爾演算法示例。

普里姆演算法

---

圖形方法

1. 選擇一個任意節點。
2. 透過一條邊將該節點連線到其最近的節點。
3. 現在連線尚未連線到您正在形成的路徑的最近節點。
4. 重複步驟 3，直到所有節點都已連線。

示例：普里姆演算法的圖形執行。

表格方法

網路可以用表格形式表示，其中記錄節點之間的距離。

1. 選擇一個任意節點 X。
2. 刪除行 X。
3. 在列 X 中查詢最小值，讀取它所屬的節點，這就是您的新節點 Y。
4. 刪除行 Y。
5. 在列 X 和 Y 中查詢最小值，然後轉到步驟 3，重複此過程，直到網路連線起來。

示例：普里姆演算法的表格執行。

最短路徑

迪傑斯特拉演算法

---

永久標籤 (P-標籤) 由方框中的值表示。

臨時標籤 (T-標籤) 由沒有方框的值表示。

1. 步驟 1
   1. 用 0 的 P-標籤標記開始節點 S。
   2. 對於所有可以從 S 到達的節點，分配等於它們從 S 到達的直接距離的 T-標籤。
   3. 選擇 T-標籤值最小的節點，將其設為 P-標籤，該標籤標記從 S 到該節點的最短距離。
2. 步驟 2
   1. 在所有可以從剛用 P-標籤標記的節點直接到達的節點上放一個 T-標籤。T-標籤應等於 P-標籤和從該節點到達的直接距離的總和。如果節點上存在 T-標籤，則如果新的總和更小，則應替換它。
   2. 選擇最小 T-標籤並將其設為永久標籤。
   3. 如果這將目標節點設為標籤，則繼續，否則重複步驟 2。
3. 步驟 3
   1. 從當前節點（目標節點）回溯到起始節點，包括任何邊 MN，其中（M 的 P-標籤） - （N 的 P-標籤）= 弧 MN 的長度。

示例

使用迪傑斯特拉演算法查詢 S 和 T 之間的最短路線。

影像	描述
	這是初始圖形。
	首先用 0 的 P-標籤標記起始節點。
	用它們到起始節點距離的 T-標籤標記直接連線的節點。
	將最低 T-標籤設為 P-標籤，然後用它們自己的 T-標籤標記其直接連線的節點。 注意：Q 的 T-標籤已被裁剪，它為 7
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點，這裡 X 的 T-標籤已被重新標記為 4，因為找到了更短的路線。
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。 注意：V 的 T-標籤已被裁剪，它為 6
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。
	將最低 T-標籤設為 P-標籤，用它們自己的 T-標籤標記其直接連線的節點。
	最後，從當前節點（目標節點）回溯到起始節點，包括任何邊 MN，其中（M 的 P-標籤） - （N 的 P-標籤）= 弧 MN 的長度。 路線，SUVWT 是最短路徑，SPQRT 也是最短路徑（但本次演示中沒有選擇它）。