C#实现Dijkstra算法输出错误，无法正确计算源节点最短路径

核心问题分析 #

• 已处理节点标记逻辑混乱：你在更新距离时才将nearvertex加入vertex列表，这会导致同一个节点被重复添加，且无法正确标记哪些节点已经完成最短路径计算。正确的时机应该是在选中当前最短路径节点后，立即将其标记为已处理。
• 距离更新的边界条件缺失：
  • 未判断graph[nearvertex][i]是否为0（0表示节点间无直接边），会错误地用0来计算路径长度。
  • 当distance[nearvertex]为int.MaxValue时，distance[nearvertex] + graph[nearvertex][i]会触发整数溢出，导致错误的比较结果。
• 输出逻辑错误：当前代码输出的是每次选中的最短边长度，而非源节点到各节点的最终最短路径值，不符合需求。
• 节点选中条件有漏洞：判断0 < distance[j]会排除源节点到自身的距离（0），但源节点本身一开始就应该标记为已处理，不需要参与后续的节点选择。

修复后的代码 #

namespace Dijkstra
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[][] graph = {
                new int []{ 0, 1, 7, 0, 0 },
                new int [] { 0, 0, 4, 4, 1},
                new int []{ 0, 0, 0, 3, 2 },
                new int []{ 0, 0, 0, 0, 5 },
                new int []{ 0, 0, 0, 0, 0 } };
            ShortestPath(graph, 0);
        }

        static void ShortestPath(int[][] graph, int source)
        {
            int totalNodes = graph.Length;
            int[] distance = new int[totalNodes];
            bool[] processed = new bool[totalNodes]; // 用布尔数组标记已处理节点，比List.Contains更高效

            // 初始化距离数组：源节点到自身为0，其他为无穷大
            for (int i = 0; i < totalNodes; i++)
            {
                distance[i] = i == source ? 0 : int.MaxValue;
                processed[i] = false;
            }

            // Dijkstra算法需要处理n-1次，因为每次确定一个节点的最短路径
            for (int count = 0; count < totalNodes - 1; count++)
            {
                // 找到未处理节点中距离源节点最近的节点
                int minDistance = int.MaxValue;
                int nearestNode = -1;
                for (int j = 0; j < totalNodes; j++)
                {
                    if (!processed[j] && distance[j] <= minDistance)
                    {
                        minDistance = distance[j];
                        nearestNode = j;
                    }
                }

                // 如果没有可达节点，提前退出
                if (nearestNode == -1) break;

                // 标记当前节点为已处理
                processed[nearestNode] = true;

                // 更新所有未处理节点的距离
                for (int i = 0; i < totalNodes; i++)
                {
                    // 条件：未处理、有直接边、当前节点距离不是无穷大、新路径更短
                    if (!processed[i] 
                        && graph[nearestNode][i] != 0 
                        && distance[nearestNode] != int.MaxValue 
                        && distance[nearestNode] + graph[nearestNode][i] < distance[i])
                    {
                        distance[i] = distance[nearestNode] + graph[nearestNode][i];
                    }
                }
            }

            // 输出源节点到各节点的最短路径
            Console.WriteLine("源节点到各节点的最短路径：");
            for (int i = 0; i < totalNodes; i++)
            {
                Console.WriteLine($"节点 {i}: {distance[i] == int.MaxValue ? "不可达" : distance[i].ToString()}");
            }
        }
    }
}

关键修复说明 #

• 用布尔数组替代List标记已处理节点：processed数组比List.Contains的时间复杂度更低（O(1) vs O(n)），彻底避免重复添加节点的问题。
• 调整节点选中逻辑：去掉多余的0 < distance[j]判断，逻辑只关注未处理且距离最小的节点，源节点会在第一次循环中被选中并标记为已处理。
• 完善距离更新条件：
  • 增加graph[nearestNode][i] != 0判断，排除无直接边的节点，避免无效计算。
  • 增加distance[nearestNode] != int.MaxValue判断，防止整数溢出导致的错误比较。
• 修正输出逻辑：直接输出distance数组，清晰展示源节点到每个节点的最短路径值，还处理了不可达节点的显示。
• 初始化逻辑简化：用三元运算符初始化距离数组，代码更简洁易读。

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