首页 > 试题广场 >

如下有向带权图,若采用迪杰斯特拉(Dijkstra) 算法求

[单选题]

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


  • d,e,f
  • e,d,f
  • f,d,e
  • f,e,d
推荐
参照大佬的解法
选C
【分析】
从a到各顶点的最短路径的求解过程:

后续目标顶点依次为f,d,e,

【排除法】对于A,若下一个顶点为d,路径a,b,d的长度5,而a,b,c,f的长度仅为4,显然错误。同理可以排除B。将f加入集合S后,采用上述的方法也可以排除D。


编辑于 2019-04-10 14:20:51 回复(1)
选C。根据Dijkstra算法原理以及题目中的已知条件:
  • S={Va,Vb,Vc},S集合收录从源点a到其他各顶点的最短路径,题目条件给出:最短路径的目标顶点是b,第二条最短路径的目标顶点是c
  • 对于其余未收录的顶点(d,e,f)从源点a到其最短路径长度dist[V],必须经过S中已收录的顶点。
  • a->b->f最短路径为2+1+1=4,a->b->d最短路径为2+3=5,a->b->d->e最短路径为2+3+1=6,所以最短路径一次为f,d,e
发表于 2019-04-09 15:18:28 回复(0)
发表于 2019-11-09 16:26:58 回复(2)
S为已确定最短路径的集合,初始状态为{'p_0=0'}
U为其他点集合{'p_i=d_i', ...}, (i = 1~n, d_i = (p_0至p_i之距离) or INF)
while (U不为空) { // 实际循环n次
    取U中d最小的点j,将'p_j=d_j'从U中移除,加入S;
    同时,对于U中所有其他点p_k,检查以d_j + (p_j至p_k之距离) < d_k?是则更新d_k。
}
发表于 2019-09-25 19:27:08 回复(0)
答案是c
发表于 2018-10-17 18:24:34 回复(0)