Does this line of code do anything in this Dijkstra algorithm implementation?

Question

here's a simple implementation of Dijskstra. I'm aware its very basic, just learning C++. I got it from another source, and can't understand why they have included this line of code:

&& distance[m]!=INT_MAX

which appears in the nested for loop in the Dijsktra function definition. I've compiled it with and without this line of code and it seems to work just fine both ways. I can't see any scenario where the minimum distance of an unvisited vertex would equal infinity. Any ideas why it might have been included? Is it superflous? Full code below.

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

int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
    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) // adjacency matrix 
{
    int distance[6]; // // array to calculate the minimum distance for each node                             
    bool Tset[6];// boolean array to mark visited and unvisited for each node
    
     
    for(int k = 0; k<6; k++)
    {
        distance[k] = INT_MAX;
        Tset[k] = false;    
    }
    
    distance[src] = 0;   // Source vertex distance is set 0               
    
    for(int k = 0; k<6; k++)                           
    {
        int m=miniDist(distance,Tset); 
        Tset[m]=true;
        for(int k = 0; k<6; k++)                  
        {
            // updating the distance of neighbouring vertex
            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;                           
}

Looks like `miniDist()` could return `INT_MAX` if the if-statement inside the for-loop never succeeds. — Jeremy Friesner, Aug 15 '22 at 22:46

lorro · Answer 1 · 2022-08-15T22:52:28.740

1

In older C++ standards, signed integer overflow is UB. When it's not (c++20), it's due to 2's complement arithmetics, which means that if you add to INT_MAX, you'll end up having negative numbers. Thus, distance[m]+graph[m][k]<distance[k] could actually succeed (be true) even if distance[m] == INT_MAX. The code is right to defend against this.

edited Aug 15 '22 at 22:52

answered Aug 15 '22 at 22:49

lorro

10,687
23
36

1

UB or not, it definitely won't do what's expected in case of overflow... – nickie Aug 15 '22 at 22:50
@nickie exactly – lorro Aug 15 '22 at 22:52
I think signed overflow **by computation** is still UB even in C++20, see [this question](https://stackoverflow.com/questions/70801443/why-is-signed-overflow-due-to-computation-still-undefined-behavior-in-c20). – heap underrun Aug 16 '22 at 00:00

Does this line of code do anything in this Dijkstra algorithm implementation?

1 Answers1