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 也是最短路径（但本次演示中没有选择它）。