在[tex=4.357x1.214]a2fgr/W+/4noIbkIIGsltA==[/tex]算法中，增加一个记忆系统，使得此算法不仅能给出从 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 到[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex] 的最短路的路长，而且可以给出一条最短路径。
举一反三
- 利用 [tex=3.929x1.214]LwEtGvTGj1URnOeaanEEJQ==[/tex]算法，求出下面图中从[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 到 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]的所有最短路径及路径长度。[img=303x185]1785e4b18b46567.png[/img]（1）
- 在赋权下图中，利用[tex=3.929x1.214]LwEtGvTGj1URnOeaanEEJQ==[/tex]算法求出从[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]到[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]的所有最短路径及其权。[img=465x297]17871c4ac9eed8e.png[/img]
- 以下算法是计算两个正整数[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]和[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]最大公因数的递归函数,给出其递归模型。[img=246x187]17a38102a090077.png[/img]
- 假设图采用邻接矩阵存储。自由树(即无环连通图)[tex=1.429x1.0]t3EWRtipWRbM0wEI5sxtIA==[/tex][tex=2.571x1.286]9rh3ju5etdkssGyY6ZufVA==[/tex]的直径是树中所有点对点间最短路径长度蛇最大值,即 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex]的直径定义为 [tex=9.214x1.357]qQlvYuFXER0XPD83YiK1r3AqvRZAhqWqzocBdRWgPFvWevwJxi6XPXZLYmR7oDAZ[/tex] 这里 [tex=2.857x1.357]ryAcSEdCmoYPGTNXQFHomQ==[/tex] 表示顶点[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 到顶点[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex] 的最短路径长度(路径长度火路径中包含的边数)。编写一 算法求 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 的言径,以图 [tex=1.786x1.0]6vJ4kr1+zLa1rBkdL8N+Jw==[/tex]为例给出解。并分析算法的时间复杂度。[img=198x189]179ec5e27f0171c.png[/img]
- 有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是单连的，是指对于任意两个顶点 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 和 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex], 或者 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex] 是从 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]出发可到达的,或者 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 是从 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex] 出发可到达的. 证明: [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是单连的当且仅当 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 有一条生成有向途径.