Variation Dijkstra considering 0 as a weight

Question

I'm trying to implement Dijkstra on adjacency matrix where 0 has the meaning of weight instead of "no connection". I'm quite struggling on how to modify the original algorithm, Is there any clue that could help me to find out the way? implementation:

#define V 3
int minDistance(int dist[], bool sptSet[]){
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
 
    return min_index;
}
 
void dijkstra(int graph[V][V], int src){
    int dist[V]; 
 
    bool sptSet[V]; 
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
 
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
 
        sptSet[u] = true;
 
        
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
 
}

for example if I give in input:

0, 0, 0
1, 2, 1
2, 9, 3

the minimum path should be 0 lenght, instead I get 2147483647 which is the INT_MAX.

Source is node 0, and destinations are all the other nodes.

Answer 1

In the implementation you provided, the condition for updating the distance to a node is:

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])

The second part is the one that is causing your code to skip when finding an edge with a cost equal to zero:

graph[u][v]

I assume that your code is written in C++. Thus, this check means true if the value is non-zero, and false otherwise. You need to update the condition to remove this part:

if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])

In this case, the algorithm should work fine.

If you use this update and still need to indicate the case of no edge, then you can set its value to INT_MAX rather than zero.