数据结构与算法（周测5-最短路径）

判断题

1.在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。

2.P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。

3.对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。

4.Let P be the shortest path from S to T. If the weight of every edge in the graph is incremented by 1, P will still be the shortest path from S to T.

5.Let M be the minimum spanning tree of a weighted graph G. Then the path in M between V1 and V2 must be the shortest path between them in G.

选择题

1.在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？

1. c与a的最短路径长度就是13
2. c与a的最短路径长度就是7
3. c与a的最短路径长度不超过13
4. c与a的最短路径不小于7

2.若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：

3.我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？

4.In a weighted graph, if the length of the shortest path from b to a is 10, and there exists an edge of weight 3 between c and b, then how many of the following statements is/are TRUE?

1. The length of the shortest path from c to a must be 13.
2. The length of the shortest path from c to a must be 7.
3. The length of the shortest path from c to a must be no greater than 13.
4. The length of the shortest path from c to a must be no less than 7.

5.数据结构中Dijkstra算法用来解决哪个问题？

6.使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：

7.若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：

8.下面的哪个算法可以求图的最短路径____。

9.If an undirected graph G = (V, E) contains 7 vertices. Then to guarantee that G is connected in any cases, there has to be at least __ edges.

10.使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：

原文：https://www.cnblogs.com/nonlinearthink/p/11854784.html