Dijkstra算法实现中`distance[m]!=INT_MAX`代码行是否多余？

我是C++初学者，拿到一份基础的Dijkstra算法实现代码。在DijkstraAlgo函数的嵌套for循环里，判断条件包含&& distance[m]!=INT_MAX这一段。我分别编译运行了保留和删除这行的代码，结果都正常，但想不通什么时候未访问顶点的最小距离会等于无穷大，所以请教这行代码是不是多余的，以及它被加进来的原因。

完整代码如下：

#include<iostream>
#include<climits>
using namespace std;

int miniDist(int distance[], bool Tset[]) // 寻找未访问节点中的最小距离节点
{
    int minimum=INT_MAX,ind;
              
    for(int k=0;k<6;k++) 
    {
        if(Tset[k]==false && distance[k]<=minimum)      
        {
            minimum=distance[k];
            ind=k;
        }
    }
    return ind;
}

void DijkstraAlgo(int graph[6][6],int src) // 邻接矩阵实现的Dijkstra算法
{
    int distance[6]; // 存储每个节点到源点的最小距离
    bool Tset[6];// 标记节点是否已被访问
    
    for(int k = 0; k<6; k++)
    {
        distance[k] = INT_MAX;
        Tset[k] = false;    
    }
    
    distance[src] = 0;   // 源点到自身的距离设为0               
    
    for(int k = 0; k<6; k++)                            
    {
        int m=miniDist(distance,Tset); 
        Tset[m]=true;
        for(int k = 0; k<6; k++)                   
        {
            // 更新邻接节点的距离
            if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX && distance[m]+graph[m][k]<distance[k])
                distance[k]=distance[m]+graph[m][k];
        }
    }
    cout<<"Vertex\t\tDistance from source vertex"<<endl;
    for(int k = 0; k<6; k++)                       
    { 
        char str=65+k; 
        cout<<str<<"\t\t\t"<<distance[k]<<endl;
    }
}

int main()
{
    int graph[6][6]={
        {0, 1, 2, 0, 0, 0},
        {1, 0, 0, 5, 1, 0},
        {2, 0, 0, 2, 3, 0},
        {0, 5, 2, 0, 2, 2},
        {0, 1, 3, 2, 0, 1},
        {0, 0, 0, 2, 1, 0}};
    DijkstraAlgo(graph,0);
    return 0;                           
}

这行代码并非多余，它是处理非连通图场景的关键 #

你测试用的是连通图，所有节点都能从源点到达，所以不会触发distance[m] == INT_MAX的情况，删了代码也能正常运行，但换成非连通图就会出问题：

1. 触发场景：非连通图
   当图中存在和源点完全没有路径连通的节点时，miniDist函数最终会选中这类节点（因为所有未访问节点的distance都是INT_MAX，函数会按遍历顺序返回其中一个）。此时distance[m]的值就是INT_MAX。

2. 没有这行代码的后果：整数溢出
   Dijkstra算法要求边的权重为非负数，graph[m][k]如果不为0就是正数。当distance[m]是INT_MAX时，执行distance[m] + graph[m][k]会触发整数溢出，结果变成一个负数（多数编译器按补码循环处理有符号整数溢出）。这时候负数 < distance[k]（distance[k]此时也是INT_MAX）的判断会成立，错误地把distance[k]更新为负数，导致最终结果完全错误。

3. 代码的作用
   distance[m]!=INT_MAX这个判断会跳过对不可达节点的后续距离更新，既避免了整数溢出的风险，也减少了无效的计算操作。

所以这行代码是为了增强算法的鲁棒性，处理非连通图的边界场景，并不是多余的。

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