单行线交通网中寻找最优旅行路线

例6-10　已知图6-19 所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从 v1出发，通过这个交通网到 v8去，求使总费用最小的旅行路线。

图6-19

可见，从 v1到 v8的旅行路线是很多的。例如，可以从 v1出发，依次经过 v2，v5，然后到 v8；也可以从 v1出发，依次经过 v3，v4，v6，v7，然后到 v8，等等。不同的路线，所需总费用是不同的。比如，按前一条路线，总费用是6+1+6=13 单位；而按后一条路线，总费用是3+2+10+2+4=21 单位。不难看到，用图的语言来描述，从 v1到 v8的旅行路线与有向图中从 v1到v8的路是一一对应的。一条旅行路线的总费用就是相应的从 v1到 v8的路中所有弧旁数字之和。当然，这里说的路可以不是初等路线。例如，某人从 v1到 v8的旅行路线可以是从 v1出发，依次经 v3，v4，v6，v5，v4，v6，v7，最后到达 v8。这条路线相应的路是（v1，v3，v4，v6，v5，v4，v6，v7，v8），总费用是47 单位。(www.xing528.com)

从这个例子可以引出一般的最短路问题：给定一个赋权有向图，即给了一个有向图D=（V，A），对每一条弧a=（vi，vj），相应地有权 w（a）=wij。又给定D中的两个顶点 vs，vt，设P 是D中从 vs到 vt的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从 vs到 vt的路中，求一条权最小的路，即求一条从 vs到 vt的路 P0，使

式中对D中所有从 vs到 vt的路P 取最小，称 P0是从 vs到 vt的最短路。路 P0的权称为从vs到vt的距离，记为d（vs，vt）。显然，d（vs，vt）与 d（vt，vs）不一定相等。

最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且经常作为一个基本工具，用于解决其他优化问题。