考虑使用Dijkstra算法求解从顶点a到顶点b的最短路径,已知路径(a,c,f,d,g,b)的总权值为14,路径(a,c,e,d,g,b)的总权值为15。如果在算法执行过程中,顶点e的当前最短路径估计值被错误地更新为9,这会导致什么后果?
答案解析
Dijkstra算法在每一步都选择当前最短路径估计值最小的顶点进行松弛操作。如果顶点e的当前最短路径估计值被错误地更新为9,这比实际的最短路径估计值要小,算法可能会错误地认为通过顶点e的路径更短,从而错误地选择路径(a,c,e,d,g,b)作为最短路径(选项A)。这不会导致算法无法找到路径(选项B)或提前终止(选项D),因为算法仍然能够找到一条路径,只是这条路径可能不是实际最短的。选项C描述的情况不会发生,因为算法的错误选择会导致结果不准确。
正确答案:A