最短路问题

第三节　最短路问题

引例 在某省的8个城市v0，v1，…，v7之间有一个公路网，如图9-9所示，每条公路为图中的边，边上的数字（一般我们称之为权数）表示通过该公路所需的时间，设你在城市v0，那么从v0到其他各城市，应选择什么路径使所需时间最少？

要解决这类问题，最关键的是要在图中找出从起点到终点之间总权数之和最小的路线，也就是在指定的两点间找一条路（或链），使数字和最小，因此我们统称这类问题为最短路问题.

第三步 类似地，找出与集合S={v1，v2}中每一个顶点与中有直接相连边的顶点，并计算出v1到它们的距离，找出最小值及对应顶点.与v1相连边有1条（v1，v3）；与v2相连边有4条（v2，v3），（v2，v4），（v2，v5），（v2，v6），分别计算v1到相关各点的距离得

问题得以最终解决，用逆向法可以写出最短路的路线图