非连通图场景下Dijkstra算法是否可行？附实现代码

首先明确一点：标准Dijkstra算法的设计是可以处理非连通图场景的，但你的初始实现没有处理非连通图里的边界情况，才导致了问题。

原实现的核心问题 #

在非连通图中，那些和源节点（比如你测试的C）不在同一连通分量的节点（比如B），它们的ShortestDistanceFromTarget会一直是初始化的int.MaxValue。原循环条件verticesDictionary.Values.ToList().Any(x => x.IsVisited == false)会强制算法去处理这些孤立节点——当你尝试计算currentVertex.ShortestDistanceFromTarget + graph.GetEdgeWeight(...)时，int.MaxValue加上任何正数都会触发整数溢出，导致错误的距离值，进而引发逻辑问题。

你的修改是正确的方向 #

你把循环条件改成verticesDictionary.Values.ToList().Any(x => x.IsVisited == false && x.ShortestDistanceFromTarget != int.MaxValue)，这个调整完美解决了问题：它只让算法处理已经被发现（距离不是无穷大）且未访问的节点，相当于只在源节点所在的连通分量内执行计算，完全避开了对孤立节点的无效操作，也消除了溢出风险。

额外的优化建议 #

1. 路径不存在的判断：在FormShortestPath方法开头，先检查目标节点的ShortestDistanceFromTarget是否还是int.MaxValue，如果是的话，直接返回空栈或者抛出明确的提示（比如“源节点与目标节点不存在连通路径”），这样调用方能清晰知道结果的含义，而不是拿到一个空栈一脸懵。
2. 优先队列优化：你现在每次找最小距离节点的方式是verticesDictionary.Where(x => x.Value.IsVisited == false).ToList().Min()，这是O(n)的操作，多次循环下来时间复杂度是O(n²)。可以改用C#内置的PriorityQueue<(string VertexKey, Vertex Vertex), int>来维护未访问节点，每次取出最小距离的节点只需要O(log n)的时间，整体复杂度会降到O(m log n)，节点越多效率提升越明显。

你的实现代码 #

internal static Stack<string> Dijkstra(string sourcePoint, string targetPoint, Graph graph) 
{ 
    List<string> verticesStringList = graph.GetAllVertices(); 
    Dictionary<string, Vertex> verticesDictionary = new Dictionary<string, Vertex>(); 
    InitializeVerticesDictionary(sourcePoint, verticesStringList, verticesDictionary); 

    while (verticesDictionary.Values.ToList().Any(x => x.IsVisited == false && x.ShortestDistanceFromTarget != int.MaxValue)) 
    { 
        KeyValuePair<string, Vertex> keyValuePair = verticesDictionary.Where(x => x.Value.IsVisited == false).ToList().Min(); 
        string vertexKey = keyValuePair.Key; 
        Vertex currentVertex = keyValuePair.Value; 
        List<string> neighbourVertices = graph.GetNeighbourVerticesSorted(keyValuePair.Key); 

        foreach (string neighbourVertexString in neighbourVertices) 
        { 
            Vertex neighbourVertex = verticesDictionary[neighbourVertexString]; 
            int newDistanceFromStartVertex = currentVertex.ShortestDistanceFromTarget + graph.GetEdgeWeight(keyValuePair.Key, neighbourVertexString); 
            if (newDistanceFromStartVertex < neighbourVertex.ShortestDistanceFromTarget) 
            { 
                verticesDictionary[neighbourVertexString].ShortestDistanceFromTarget = newDistanceFromStartVertex; 
                verticesDictionary[neighbourVertexString].PreviousVertex = keyValuePair.Key; 
            } 
        } 
        verticesDictionary[vertexKey].IsVisited = true; 
    } 
    return FormShortestPath(targetPoint, verticesDictionary); 
} 

private static Stack<string> FormShortestPath(string targetPoint, Dictionary<string, Vertex> verticesDictionary) 
{ 
    Stack<string> traverseStack = new Stack<string>(); 
    KeyValuePair<string, Vertex> vertex = verticesDictionary.Where(x => x.Key == targetPoint).FirstOrDefault(); 
    while (vertex.Value.PreviousVertex != null) 
    { 
        traverseStack.Push(vertex.Value.PreviousVertex + " Goes To " + vertex.Key); //the end edge 
        vertex = verticesDictionary.Where(x => x.Key == vertex.Value.PreviousVertex).FirstOrDefault(); 
    } 
    return traverseStack; 
} 

private static void InitializeVerticesDictionary(string sourcePoint, List<string> verticesStringList, Dictionary<string, Vertex> verticesDictionary) 
{ 
    foreach (string vertexString in verticesStringList) 
    { 
        Vertex vertex = new Vertex { ShortestDistanceFromTarget = int.MaxValue }; 
        if (vertexString == sourcePoint) 
        { 
            vertex.ShortestDistanceFromTarget = 0; 
        } 
        verticesDictionary.Add(vertexString, vertex); 
    } 
}

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