时间和空间复杂度

时间复杂度：

• 按这里的写法，时间复杂度为 O(V² + V*E)（每一轮都会扫描顶点以找到最小值，并扫描边以进行松弛）。使用二叉堆和邻接表后，时间复杂度可优化为 O((V + E) log V)。

空间复杂度：

• 距离数组和已访问数组需要 O(V) 空间（输入的边除外）。

总结：

• Dijkstra 通过贪心地确定距离最近的顶点，并松弛其边，来计算从单个源点出发到其他顶点的最短距离，适用于非负权重。
• 它无法处理负权边；遇到负权边时，请使用 Bellman-Ford。