Answer

问题及解答

[Ex5.9-3]

Posted by haifeng on 2019-04-26 16:38:34 last update 2019-04-26 16:38:34 | Edit | Answers (1)

在一个城市交通系统中取出一段如下图所示, 其入口为顶点 $v_1$, 出口为顶点 $v_8$. 每条弧段旁的数字表示通过该路段所需的时间. 每次转弯需要附加时间为 3 秒.

求 $v_1$ 到 $v_8$ 的最短时间路径.

 

 

 


 

1

Posted by haifeng on 2019-04-26 17:20:58

根据题意, 我们假设图中线段的方向即意味着真实道路的方向. 虽然 $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}
\]