下列关于图的最短路径的叙述中，正确的是（　　）。

A. 最短路径一定是简单路径 B. Dijkstra 算法不适合求有回路的带权图的最短路径 C. Dijkstra 算法不适合求任意两个顶点的最短路径 D. Dijkstra 算法可以正确处理含有负权边的图

[tag_link]

正确答案：A

结论

选 A。

推导

在不存在负权回路的通常最短路定义下，若一条路径重复顶点，就含有回路；去掉该回路不会增加长度，因此存在一条同样不长于它的简单最短路径。Dijkstra 可处理有回路图，也可从每个源点重复运行求任意点对最短路，但要求边权非负，故 B、C、D 均错误。

易错点

Dijkstra 的限制是“不能有负权边”，不是“不能有回路”。