如下有向带权图,若采用迪杰斯特拉(Dijkstra) 算法求源点a到其他各顶点的最短路径,得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是( ).
d,e,f
e,d,f
f,d,e
f,e,d
后续目标顶点依次为f,d,e,
【排除法】对于A,若下一个顶点为d,路径a,b,d的长度5,而a,b,c,f的长度仅为4,显然错误。同理可以排除B。将f加入集合S后,采用上述的方法也可以排除D。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
后续目标顶点依次为f,d,e,
【排除法】对于A,若下一个顶点为d,路径a,b,d的长度5,而a,b,c,f的长度仅为4,显然错误。同理可以排除B。将f加入集合S后,采用上述的方法也可以排除D。