给定一个带权重的有向图,使用Floyd算法计算所有顶点之间的最短路径。假设图中有4个顶点A、B、C、D,边的权重如下:AB=2,AC=6,AD=7,BC=3,BD=8,CD=2。在Floyd算法的第3次迭代中,顶点D到顶点B的最短路径是?
答案解析
Floyd算法通过迭代更新每个顶点到其他所有顶点的最短路径。第3次迭代意味着已经考虑了所有经过3个或更少顶点的路径。对于顶点D到顶点B的最短路径,选项A直接给出DB,但未考虑可能的中间顶点。选项B考虑了经过顶点A和C的路径,但这不是最短路径。选项C考虑了经过顶点C的路径,但忽略了顶点B。选项D考虑了经过顶点A和C的路径,但实际上最短路径是直接从D到B。因此,正确答案是A。
正确答案:A