图论中的网络

加权边

带有距离、时间或成本等值的边。

如何使用

在道路网络中，从城镇 A 到城镇 B 的边标为 12，表示这条路长 12 km。若一条路线为 A–B–C，权值为 12 和 9，则总距离为 12 + 9 = 21 km。

出现在图论中的网络这一章（中五）。加权边在第二卷最为重要：你沿路线把权值相加、比较两条路线找出较短者，或把所有权值加总，例如网络中电缆的总长度。

顶点的度数权值是一条边所带的数值（距离或成本），而度数是数一个顶点处相交的边数；度数高并不意味着权值大。

路线中的边数边数较少的路线不一定更短；你必须把权值相加，因为三条短边的总和可能小于两条长边。

权值可以代表什么？

权值可代表边上任何可测量的量：以 km 计的距离、以分钟计的行程时间、以令吉计的成本，或电缆长度。务必读题弄清数字的含义，并在最终答案中保持相同单位。

怎样用加权边求最短路线？

列出两个顶点之间的可能路线，把每条路线上的权值相加，然后选出总和最小的路线。例如，若路线 1 合计 21 km、路线 2 合计 19 km，则路线 2 是较短的路径。