问题 单项选择题

对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是()

A.d.e.f

B.e,d,f

C.f,d,e

D.f,e,d

答案

参考答案:C

解析:

根据迪杰斯特拉(Dijkstra)算法,可以得到以下过程: 从a出发,与其直接相邻的是b(2)、c(5),因此可以得到第一条最短路径的目标顶点是b。 从{a,b}出发,与其相邻的是c(3)、d(5)、e(6),因此可以得到第二条最短路径的目标顶点是c。 从{a,b,c}出发,与其相邻的是d(5)、e(6)、f(4),因此可以得到第三条最短路径的目标顶点是f。 从{a,b,c,f}出发,与其相邻的是d(5)、e(6),因此可以得到第四、五条最短路径的目标顶点是d、e。因此结点的顺序为f、d、e,即C选项。

选择题
选择题