[Ex5.9-3]
在一个城市交通系统中取出一段如下图所示, 其入口为顶点 $v_1$, 出口为顶点 $v_8$. 每条弧段旁的数字表示通过该路段所需的时间. 每次转弯需要附加时间为 3 秒.
求 $v_1$ 到 $v_8$ 的最短时间路径.
在一个城市交通系统中取出一段如下图所示, 其入口为顶点 $v_1$, 出口为顶点 $v_8$. 每条弧段旁的数字表示通过该路段所需的时间. 每次转弯需要附加时间为 3 秒.
求 $v_1$ 到 $v_8$ 的最短时间路径.
1
根据题意, 我们假设图中线段的方向即意味着真实道路的方向. 虽然 $v_2$ 至 $v_5$ 所需时间为 3+1=4 秒, 而图中相同距离的 $v_4$ 至 $v_7$ 所需 2 秒. 对于这种情况, 我们认为由各种环境或约束导致行驶的速度不同.
首先写出带权邻接矩阵
\[
W=\begin{pmatrix}
0 & 1 & \infty & \infty & \infty & \infty & \infty & \infty\\
1 & 0 & 3 & 2 & \infty & \infty & \infty & \infty\\
\infty & 3 & 0 & \infty & 1 & \infty & \infty & \infty\\
\infty & 2 & \infty & 0 & \infty & \infty & 2 & \infty\\
\infty & \infty & 1 & \infty & 0 & 6 & 2 & \infty\\
\infty & \infty & \infty & \infty & 6 & 0 & \infty & 3\\
\infty & \infty & \infty & 2 & 2 & \infty & 0 & 4\\
\infty & \infty & \infty & \infty & \infty & 3 & 4 & 0\\
\end{pmatrix}
\]