Dijkstra算法是否要求图为连通图？需满足非负权重外的连通性吗？

Dijkstra算法不要求图具备连通性，它仅对边的权重有非负的要求。

在处理不连通的图时，算法会正常完成计算：

• 若起点位于某一连通分量内，算法会准确算出该起点到同一连通分量中所有顶点的最短路径。
• 对于不属于该连通分量的顶点，算法会将它们的最短路径距离标记为无穷大（或实现中约定的“不可达”值），不会出现运行错误或逻辑崩溃。

拿你提到的例子来说：假设图包含两个独立的连通分量，一个有3个顶点，另一个有2个顶点。如果起点选在3个顶点的分量里，算法会输出起点到这3个顶点的最短路径，另外2个顶点会被标记为不可达；反之，若起点在2个顶点的分量中，算法只会处理该分量内的路径计算，另一分量的顶点同样显示不可达。

简言之，只要边的权重非负，无论图是否连通，Dijkstra算法都能按预期工作，只是对跨连通分量的顶点返回“无可达路径”的结果。

内容的提问来源于stack exchange，提问作者Zen12345