1 例:如下图所示的单行线交通网，每个弧旁边的 数字表示这条单行线的长度。现在有一个人要从v 1 出 发，经过这个交 通网到达v 6 ， 要寻求总路 程最短的线 路。 v 6 v 5 v 3 v 1 v 4 v 2 3 6 5 1 1 2 4 3 6 最短路径问题 最短路径问题 2 从v 1 到v 6 的路线是很多的。比如从v 1 出发， 经过v 2 ,v 4 到达v 6 或者从v 1 出发，经过v 2 ，v 3 ，v 5 到达v 6 等等。但不同的路线，经过的总 长度是不同的。例如，按照第一个线路，总 长度是3+6+3=12单位，按照第二个路线，总 长度是3+1+1+6=11单位。3 一、问题的提法及应用背景 一、问题的提法及应用背景 （ （ 1 1 ）问题的提法 ）问题的提法寻求网络中两点间的最 短路就是寻求连接这两个点的边的总权数为 最小的通路。 （ （ 2 2 ）应用背景 ）应用背景管道铺设、交通网络、线 路安排、厂区布局、设备更新等。4 在图的点或边上表明某种信息的数称为权。 含有权的图称为赋权图。 二、赋权图的定义 如图5 如果图中各点表示各个城市，边表示城市间的公 路，这
