最短路问题
2026年01月14日
第三节 最短路问题
引例 在某省的8个城市v0，v1，…，v7之间有一个公路网，如图9-9所示，每条公路为图中的边，边上的数字（一般我们称之为权数）表示通过该公路所需的时间，设你在城市v0，那么从v0到其他各城市，应选择什么路径使所需时间最少？
图9-9
要解决这类问题，最关键的是要在图中找出从起点到终点之间总权数之和最小的路线，也就是在指定的两点间找一条路（或链），使数字和最小，因此我们统称这类问题为最短路问题.
图9-10
图9-11
图9-12
图9-13
图9-14
图9-15
图9-16
问题得以最终解决，用逆向法可以写出最短路的路线图
