dijkstra算法常见问题

Dijkstra算法常见问题包括：
1. Dijkstra算法能否处理负权边？
答：不能。Dijkstra算法是基于贪心策略的，每次选择距离起点最近的节点进行扩展，因此无法处理负权边，因为负权边可能导致距离起点更近的节点反而被放弃。

2. Dijkstra算法的时间复杂度是多少？
答：朴素版的Dijkstra算法的时间复杂度是O(n²)，堆优化版的Dijkstra算法的时间复杂度是O(mlogn)，其中n为节点数，m为边数。因此，朴素版适合于稠密图，堆优化版适合于稀疏图。

3. Dijkstra算法能否处理有向图？
答：可以。Dijkstra算法本身并不依赖于图的方向性，只需要将有向图转化为无向图即可。

4. Dijkstra算法能否处理带有负环的图？
答：不能。负环是指环上所有边的权值之和为负数的环，如果存在负环，则Dijkstra算法会陷入死循环。