算法设计与分析-习题9.3

目录1.请解释为了解决下面的问题 Dijkstra算法和所操作的图是否要做调整?要做怎样的调整?a.对于加权有向图求解单起点最短路径问题。b.求一个加权图或者有向图中两个顶点之间的最短路径[这个变化形式被称为单对最短路径问题(single-pair shortest-path problem)]。c.求一个加权图或有向图中所有其他顶点到一个给定顶点之间的最短路径[这个变化形式被称为单终点最短路径问题(single-destination shortest-paths problem)]。d.如果对图中的每个顶点都赋予一个非负的数字求解这种图的单起点最短路径问题(路径的长度定义为组成路径的顶点数字之和)。2.解下面这个单起点最短路径问题的实例以顶点a作为起点。3.给出一个反例说明对于包含负权重的加权连通图 Dijkstra 算法可能会无效。4.有一个加权连通图G在对它求解单起点最短路径问题的过程中构造了一棵树T。下列说法是对还是错?a. T是G的生成树。b. T是G的最小生成树。5.为Dijkstra 算法的简化版本写一段伪代码对于用权重矩阵表示的图只求出从一个给定顶点到其他所有顶点的距离(也就是最短路径的长度而不是最短路径本身)。6.对于权重全部大于0的图证明 Dijkstra算法的正确性。7.对于用邻接链表表示的有向无环图设计一个解单起点最短路径问题的线性算法。8.解释如何利用 Dijkstra算法求解最小总和问题(习题8.1第8题)。9.最短路径建模 假设有一个加权连通图的模型是由球(代表顶点)和连接球的相应长度的绳子(代表边)构成的。a.描述如何用这个模型解单对最短路径问题。b.描述如何用这个模型解单起点最短路径问题。1.请解释为了解决下面的问题 Dijkstra算法和所操作的图是否要做调整?要做怎样的调整?a.对于加权有向图求解单起点最短路径问题。Dijkstra本来就支持有向图。b.求一个加权图或者有向图中两个顶点之间的最短路径[这个变化形式被称为单对最短路径问题(single-pair shortest-path problem)]。提前中止算法正常运行 Dijkstra一旦终点被弹出优先队列确定最短路径立刻停止不需要跑完所有点c.求一个加权图或有向图中所有其他顶点到一个给定顶点之间的最短路径[这个变化形式被称为单终点最短路径问题(single-destination shortest-paths problem)]。原图所有边反转方向以原来的终点作为新起点运行普通 Dijkstra得到的路径就是原图中所有点 → 终点的最短路d.如果对图中的每个顶点都赋予一个非负的数字求解这种图的单起点最短路径问题(路径的长度定义为组成路径的顶点数字之和)。把顶点的值转换到边权值上面每条边u → v新边权 v 的顶点权值起点的权值要单独加到最终距离里比如路径s → a → b → t顶点和w (s) w (a) w (b) w (t)等价于w (s) (边 s→a 权 a) (边 a→b 权 b) (边 b→t 权 t)2.解下面这个单起点最短路径问题的实例以顶点a作为起点。a.b.3.给出一个反例说明对于包含负权重的加权连通图 Dijkstra 算法可能会无效。此时Dijkstra 因提前确定顶点距离无法处理负权边4.有一个加权连通图G在对它求解单起点最短路径问题的过程中构造了一棵树T。下列说法是对还是错?a. T是G的生成树。对T 包含图中所有顶点有n−1 条边、无环。且连通→ 满足生成树定义。b. T是G的最小生成树。错因为最短路径树是保证从起点到各点路径最短而最小生成树 MST保证总边权最小。两者目的不同结构一般不一样。5.为Dijkstra 算法的简化版本写一段伪代码对于用权重矩阵表示的图只求出从一个给定顶点到其他所有顶点的距离(也就是最短路径的长度而不是最短路径本身)。算法 DIJKSTRA(weight, n, v): 输入: 权重矩阵 weight[0..n-1][0..n-1], 顶点数 n, 起点 v 输出: 最短距离数组 dist[0..n-1] // 初始化 for i 0 to n-1: dist[i] weight[v][i] // 起点到各点初始距离 visited[i] false // 都未确定 visited[v] true // 起点已确定 dist[v] 0 // 自己到自己距离为0 // 执行 n-1 次找到剩下所有点的最短路 for count 1 to n-1: // 第一步选 未访问 且 dist最小 的顶点 u min ∞ u -1 for i 0 to n-1: if not visited[i] and dist[i] min: min dist[i] u i visited[u] true // 确定 u 的最短路径 // 第二步用 u 松弛 所有未访问点 for w 0 to n-1: if not visited[w] and weight[u][w] ≠ ∞: if dist[w] dist[u] weight[u][w]: dist[w] dist[u] weight[u][w] return dist6.对于权重全部大于0的图证明 Dijkstra算法的正确性。即证明当算法把顶点 u 标记为 “已确定” 时dist [u] 已经是 s 到 u 的真正最短路径长度。反证假设当算法把u标记为已确定时dist [u] 不是 s 到 u 的最短路径长度。那么一定存在一条更短的真实最短路径s-u(真实最短路径)把这条真实路径拆开,设这条真实最短路径是s-.....-x-y-....-u此时x 是路径上最后一个已经被算法确定的点y 是路径上紧接着 x、还没被确定的点比较 dist [y] 和 dist [u]因为所有边权 0路径是递增的dist[x]w(x,y)真实最短距离到 y而算法此时已经处理过x所以dist[y]dist[x]w(x,y)又因为y在s→u 的最短路径上dist[y]剩下路径长度真实最短距离到 u因为所有边权 0所以dist[y]真实最短距离到 u但我们假设真实最短距离到 udist[u]所以推出dist[y]dist[u]。而算法每一步都会选距离最短的点由推理的情况这一轮应该选 y而不是 u。因此矛盾假设不成立。7.对于用邻接链表表示的有向无环图设计一个解单起点最短路径问题的线性算法。有向无环图就意味着每个点只会处理一次不会回头对 DAG 进行拓扑排序初始化距离数组起点 dist0其余 ∞按拓扑序依次遍历每个顶点 u对 u 的每一条出边 u→v 做松弛dist[v] min(dist[v], dist[u] weight(u→v))算法 DAG_SHORTEST_PATH(adj, n, s): 输入: 邻接表 adj, 顶点数 n, 起点 s 输出: 最短距离数组 dist[] // 1. 拓扑排序 top_order 拓扑排序(adj) // 2. 初始化距离 for 每个顶点 v: dist[v] ∞ dist[s] 0 // 3. 按拓扑序处理每个点 for u in top_order: // 遍历 u 的所有邻接边 u→v for 每条边 (u, v, w) ∈ adj[u]: if dist[v] dist[u] w: dist[v] dist[u] w return dist效率为O(V E)8.解释如何利用 Dijkstra算法求解最小总和问题(习题8.1第8题)。把矩阵看成一张图每个格子是顶点向右 / 向下走是边格子里的数值是边权然后用 Dijkstra 求从左上角到右下角的最短路径。运行dijkstra优先队列每次取出当前 dist 最小的格子用它松弛右边、下边的格子dist[nei]min(dist[nei], dist[i][j]grid[nei])到达终点时dist[终点]就是最小路径和9.最短路径建模 假设有一个加权连通图的模型是由球(代表顶点)和连接球的相应长度的绳子(代表边)构成的。a.描述如何用这个模型解单对最短路径问题。找到起点小球 s和终点小球 t。用手捏住 s 和 t向两边用力拉直。整张模型会被拉紧贴紧的那一串绳子就是 s 到 t 的最短路径。没被拉紧、松松垮垮的绳子都不是最短路径。b.描述如何用这个模型解单起点最短路径问题。把起点小球 s 固定在桌面上。拿起所有其他小球让它们自然下垂。整个模型会被重力自然拉紧。此时每个小球到起点 s 的绳子总长度就是最短路径长度。连接它们的拉紧绳子就是最短路径。