用Dijkstra标号法求图15.7所示的带权图中从顶点a到其余各点的最短路径与距离。

已知一个图如图8-42（b)所示，依据Dijkstra算法求从顶点l到其余各顶点的最短路径的顺序应是（)。A、

已知一个图如图8-42(b)所示，依据Dijkstra算法求从顶点l到其余各顶点的最短路径的顺序应是()。

A、2，5，4，6，3

B、2 , 5，3，4，6

C、2，3，5，4，6

D、5，4，6，3，2

在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（①).对于如

图8-42(a)所示的带权有向图，从顶点1到顶点5的最短路径为(②).

A、非零

B、非整

C、非负

D、非正

所谓单目标最短路径（single-destinationshortestpath)问题是指在一个带权有向图G中求从各个顶

点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.

关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).

编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。

Dijkstra算法从源点到其余各顶点的最短路径的路径长度按（①)次序依次产生，该算法在边上的权出现（②)情况时，不能正确产生最短路径。

标顶点的最短路径时所用的计算时间约为10ms，那么当图中有40个顶点时计算时间约为()ms。

带权图（权值非空，表示边连接的两个顶点间的距离)的最短路径问题是找出从初始顶点到国标顶点之

间的一条最短路径，假设从初始顶点到目标顶点之间存在路径。现有一种解决该问题的方法：

(1)设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;

(2)选择离u最近且尚未在最短路径中的一个顶点v，加人到最短路径中，并修改当前结点u=v;

(3)重复步骤(2)，直到u是目标顶点时为止。

请问上述方法能否求解最短路径？若该方法可行，请证明之;否则请举例说明。