设P是图G从vs到vt的最短路,则有( )。
举一反三
- 在下列有关最短路问题算法的论述中,哪一个是正确的?? 如果P是有向图D中从vs到vt的最短路,vi是P中的任一个点,那么从vs沿P到vi的路是从vs到vi的最短路;|如果P是有向图D中从vs到vt的最短路,vi是P中的某一个特定的点,那么从vs沿P到vi的路是从vs到vi的最短路;|如果P是有向图D中从vs到vt的最短路,vi是P中的任一个点,那么从vs沿P到vi的路是从vs到vi的唯一最短路;|如果P是有向图D中从vs到vt的最短路,vi是P中的任一个点,那么从vi沿P到vt的路是从vi到vt的唯一最短路。
- 从起点Vs到终点Vt之间各点的距离如图所示。求Vs到Vt的最短路径。[img=919x460]1803a6930517c52.png[/img] A: 180 Vs-2-5-Vt B: 160 Vs-2-5-Vt C: 160 Vs-3-5-Vt D: 180 Vs-3-5-Vt
- 在下列赋权图中,哪一个不能够用Dijkstra方法求解从vs到vt的最短路 ?
- 在下列有关Dijkstra方法的论述中,哪一个是正确的 ?? 对于给定的有向图D,利用标号法至多经过p步,就可以求出从vs到各点的最短路;|对于给定的有向图D,利用标号法至少经过p−1步,才可以求出从vs到各点的最短路;|对于给定的有向图D,利用标号法至多经过p−1步,就可以求出从vs到各点的最短路;|对于给定的有向图D,利用标号法至少经过p步,才可以求出从vs到各点的最短路。
- 假定图D中有p个顶点,在下列有关最短路问题算法的论述中,哪一个是正确的 ? A: 从vs到任一点的最短路必为初等路,图中除Vs外其它的任一点,只可能出现在某一条最短路径上。 B: 如果图D为有向图,弧的权值无论正负,都可利用dijkstra算法求得最短路径。 C: 如果赋权有向图D中不含负回路,那么从Vs到任一点的最短路最多包含p-2个中间点,图中除Vs外其它的任一点,可能出现在多条最短路上; D: 如果赋权有向图D中不含负回路,那么从vs到任一点的最短路最多包含p-1个中间点。