Skip to content

Latest commit

 

History

History
270 lines (239 loc) · 9.6 KB

习题_24_27.md

File metadata and controls

270 lines (239 loc) · 9.6 KB

P24 观察图 4-27，列举从 y 到 u 不包含任何环路的路径。

  • 第一跳是 x

    • y - x - u
    • y - x - v - u
    • y - x - w - u
    • y - x - v - w - u

  • 第一跳是 w

    • y - w - u
    • y - w - v - u
    • y - w - x - u
    • y - w - x - v - u

  • 第一跳是 z

    • y - z - w - u
    • y - z - w - v - u
    • y - z - w - x - u
    • y - z - w - x - v - u

P25 重复习题 P24，列举从 x 到 z, z 到 u 以及 z 到 w 的不包含任何环路的路径。

  • x 到 z

    • 第一跳是 u
      • x - u - w - z
      • x - u - w - y - z
      • x - u - w - x - y - z
      • x - u - w - v - x - y - z
      • x - u - v - w - z
      • x - u - v - w - y - z
    • 第一跳是 v
      • x - v - u - w - z
      • x - v - u - w - y - z
      • x - v - u - w - x - y - z
      • x - v - w - z
      • x - v - w - y - z
    • 第一跳是 w
      • x - w - z
      • x - w - y - z
    • 第一跳是 y
      • x - y - z
      • x - y - w - z

  • z 到 u

    • 第一跳是 w
      • z - w - u
      • z - w - v - u
      • z - w - v - x - u
      • z - w - y - x - u
      • z - w - y - x - v - u
      • z - w - x - u
      • z - w - x - v - u
    • 第一跳是 y
      • z - y - w - u
      • z - y - w - v - u
      • z - y - w - v - x - u
      • z - y - w - x - u
      • z - y - w - x - v - u
      • z - y - x - u
      • z - y - x - v - u
      • z - y - x - v - w - u
      • z - y - x - w - u
      • z - y - x - w - v - u

  • z 到 w

    • z - w
    • 第一跳是 y
      • z - y - w
      • z - y - x - w
      • z - y - x - v - w
      • z - y - x - v - u - w
      • z - y - x - u - w
      • z - y - x - u - v - w

P26 考虑下面的网络。对于标明的链路费用，用 Dijkstra 的最短路径算法计算出从 x 到所有网络结点的最短路径。通过计算一个类似于表 4-3 的表，说明该算法是如何工作的。

  • Dijkstra 算法实现 程序运行验证如下所示 :

    ➜  progs git:(master) ✗ ./run.sh p26.c
   **************** print structure of graph ***************
   V = 7
   E = 12
   0 : { z x 8 } { z y 12 }
   1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
   2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
   3 : { u t 2 } { v t 4 } { y t 7 }
   4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
   5 : { u w 3 } { x w 6 } { v w 4 }
   6 : { u t 2 } { u w 3 } { v u 3 }
   *********************************************************
   shortest path from x to z : [distance = 8] { z x 8 } 
   shortest path from x to y : [distance = 6] { y x 6 } 
   shortest path from x to v : [distance = 3] { v x 3 } 
   shortest path from x to t : [distance = 7] { v x 3 }  { v t 4 } 
   shortest path from x to x : [distance = 0]
   shortest path from x to w : [distance = 6] { x w 6 } 
   shortest path from x to u : [distance = 6] { v x 3 }  { v u 3 }

P27 考虑习题 P26 中所示的网络。使用 Dijkstra 算法和一个类似于表 4-3 的表来说明你做的工作:

a. 计算出从 t 到所有网络结点的最短路径。

b. 计算出从 u 到所有网络结点的最短路径。

c. 计算出从 v 到所有网络结点的最短路径。

d. 计算出从 w 到所有网络结点的最短路径。

e. 计算出从 y 到所有网络结点的最短路径。

f. 计算出从 z 到所有网络结点的最短路径。

  • Dijkstra 算法实现 程序运行结果如下所示 :

    • a.

      ➜  progs git:(master) ✗ ./p26.c.exe t
   [22:37:15:13556] src = t 3
   **************** print structure of graph ***************
   V = 7
   E = 12
   0 : { z x 8 } { z y 12 }
   1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
   2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
   3 : { u t 2 } { v t 4 } { y t 7 }
   4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
   5 : { u w 3 } { x w 6 } { v w 4 }
   6 : { u t 2 } { u w 3 } { v u 3 }
   *********************************************************
   shortest path from t to z : [distance = 15] { v t 4 }  { v x 3 }  { z x 8 } 
   shortest path from t to y : [distance = 7] { y t 7 } 
   shortest path from t to v : [distance = 4] { v t 4 } 
   shortest path from t to t : [distance = 0]
   shortest path from t to x : [distance = 7] { v t 4 }  { v x 3 } 
   shortest path from t to w : [distance = 5] { u t 2 }  { u w 3 } 
   shortest path from t to u : [distance = 2] { u t 2 }

    • b.

       ➜  progs git:(master) ✗ ./p26.c.exe u
  [22:38:43:827442] src = u 6
  **************** print structure of graph ***************
  V = 7
  E = 12
  0 : { z x 8 } { z y 12 }
  1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
  2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
  3 : { u t 2 } { v t 4 } { y t 7 }
  4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
  5 : { u w 3 } { x w 6 } { v w 4 }
  6 : { u t 2 } { u w 3 } { v u 3 }
  *********************************************************
  shortest path from u to z : [distance = 14] { v u 3 }  { v x 3 }  { z x 8 } 
  shortest path from u to y : [distance = 9] { u t 2 }  { y t 7 } 
  shortest path from u to v : [distance = 3] { v u 3 } 
  shortest path from u to t : [distance = 2] { u t 2 } 
  shortest path from u to x : [distance = 6] { v u 3 }  { v x 3 } 
  shortest path from u to w : [distance = 3] { u w 3 } 
  shortest path from u to u : [distance = 0]

    • c.

      ➜  progs git:(master) ✗ ./p26.c.exe v
 [22:40:27:606071] src = v 2
 **************** print structure of graph ***************
 V = 7
 E = 12
 0 : { z x 8 } { z y 12 }
 1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
 2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
 3 : { u t 2 } { v t 4 } { y t 7 }
 4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
 5 : { u w 3 } { x w 6 } { v w 4 }
 6 : { u t 2 } { u w 3 } { v u 3 }
 *********************************************************
 shortest path from v to z : [distance = 11] { v x 3 }  { z x 8 } 
 shortest path from v to y : [distance = 8] { y v 8 } 
 shortest path from v to v : [distance = 0]
 shortest path from v to t : [distance = 4] { v t 4 } 
 shortest path from v to x : [distance = 3] { v x 3 } 
 shortest path from v to w : [distance = 4] { v w 4 } 
 shortest path from v to u : [distance = 3] { v u 3 }

    • d.

      ➜  progs git:(master) ✗ ./p26.c.exe w
 [22:41:22:309333] src = w 5
 **************** print structure of graph ***************
 V = 7
 E = 12
 0 : { z x 8 } { z y 12 }
 1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
 2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
 3 : { u t 2 } { v t 4 } { y t 7 }
 4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
 5 : { u w 3 } { x w 6 } { v w 4 }
 6 : { u t 2 } { u w 3 } { v u 3 }
 *********************************************************
 shortest path from w to z : [distance = 14] { x w 6 }  { z x 8 } 
 shortest path from w to y : [distance = 12] { v w 4 }  { y v 8 } 
 shortest path from w to v : [distance = 4] { v w 4 } 
 shortest path from w to t : [distance = 5] { u w 3 }  { u t 2 } 
 shortest path from w to x : [distance = 6] { x w 6 } 
 shortest path from w to w : [distance = 0]
 shortest path from w to u : [distance = 3] { u w 3 }

    • e.

      ➜  progs git:(master) ✗ ./p26.c.exe y
 [22:42:1:378307] src = y 1
 **************** print structure of graph ***************
 V = 7
 E = 12
 0 : { z x 8 } { z y 12 }
 1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
 2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
 3 : { u t 2 } { v t 4 } { y t 7 }
 4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
 5 : { u w 3 } { x w 6 } { v w 4 }
 6 : { u t 2 } { u w 3 } { v u 3 }
 *********************************************************
 shortest path from y to z : [distance = 12] { z y 12 } 
 shortest path from y to y : [distance = 0]
 shortest path from y to v : [distance = 8] { y v 8 } 
 shortest path from y to t : [distance = 7] { y t 7 } 
 shortest path from y to x : [distance = 6] { y x 6 } 
 shortest path from y to w : [distance = 12] { y x 6 }  { x w 6 } 
 shortest path from y to u : [distance = 9] { y t 7 }  { u t 2 }

    • f.

      ➜  progs git:(master) ✗ ./p26.c.exe z
 [22:42:44:217028] src = z 0
 **************** print structure of graph ***************
 V = 7
 E = 12
 0 : { z x 8 } { z y 12 }
 1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
 2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
 3 : { u t 2 } { v t 4 } { y t 7 }
 4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
 5 : { u w 3 } { x w 6 } { v w 4 }
 6 : { u t 2 } { u w 3 } { v u 3 }
 *********************************************************
 shortest path from z to z : [distance = 0]
 shortest path from z to y : [distance = 12] { z y 12 } 
 shortest path from z to v : [distance = 11] { z x 8 }  { v x 3 } 
 shortest path from z to t : [distance = 15] { z x 8 }  { v x 3 }  { v t 4 } 
 shortest path from z to x : [distance = 8] { z x 8 } 
 shortest path from z to w : [distance = 14] { z x 8 }  { x w 6 } 
 shortest path from z to u : [distance = 14] { z x 8 }  { v x 3 }  { v u 3 }