Creating dijkstras algorithm and having issues in C language

Question

In my program, I'm tasked to take the first input, node names, then depending on the count of the node names we enter x amount of lines of graphs for the matrix used to display the possible paths for each node, then lastly the last line we should enter source node, then destination node, however there is an issue with the function where it simply skips checking the possible paths before finding the shortest path, as seen when giving the following example:

A,B,C,D,E,F
,4,5,,,
4,,11,9,7,
5,11,,,3,
,9,,,13,2
,7,3,13,,6
,,,2,6,
A,F

my function goes through a graph like this in the following fashion:

   A  B  C  D  E  F
A  0  4  5  0  0  0 (means that A can only go to B or C)
B  4  0  11 0  7  0 (B can only go to A, C, and E)
C  5  11 0  0  3  0 (C can only go to A, B, and E)
D  0  9  0  0  13 2
E  0  7  3  13 0  6
F  0  0  0  2  6  0

and the numbers inside represents the distance (only the 0's or integer distances are being fed). Now my code just takes the input, if there is nothing between the commas, then it defaults to 0, and continues, and then feeds this to the function which finds the shortest path but takes illegal paths. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <ctype.h>
#define MAX_NODES 10
#define INFINIX INT_MAX




void dijkstra_with_path(int graph[MAX_NODES][MAX_NODES], int num_nodes, int start, int destination, int distances[MAX_NODES], int predecessors[MAX_NODES]) {
    int unvisited_nodes[MAX_NODES];
    int i, current_node, neighbor, distance;

    for (i = 0; i < num_nodes; i++) {
        distances[i] = INFINIX;
        predecessors[i] = -1;
        unvisited_nodes[i] = 1;
    }

    distances[start] = 0;

    while (1) {
        int min_distance = INFINIX;
        for (i = 0; i < num_nodes; i++) {
            if (unvisited_nodes[i] && distances[i] < min_distance) {
                min_distance = distances[i];
                current_node = i;
            }
        }

        if (min_distance == INFINIX) {
            break;
        }

        unvisited_nodes[current_node] = 0;

        for (neighbor = 0; neighbor < num_nodes; neighbor++) {
            if (graph[current_node][neighbor] > 0) {
                distance = distances[current_node] + graph[current_node][neighbor];
                if (distance < distances[neighbor]) {
                    distances[neighbor] = distance;
                    predecessors[neighbor] = current_node;
                }
            }
        }
    }
}


int is_digit(char ch) {
    return (ch >= '0' && ch <= '9');
}

int main() {
    char station_names[100];
    char nodes[100][20];
    fgets(station_names, sizeof(station_names), stdin);

    int node_index = 0;
    int node_length = 0;
    int invalids[5] = {0,0,0,0,0};

    for (int i = 0; station_names[i] != '\n'; i++) {
        if (station_names[i] == ',') {
            nodes[node_index][node_length] = '\0';
            node_index++;
            node_length = 0;
        } else if (station_names[i] != ' ') {
            nodes[node_index][node_length] = station_names[i];
            node_length++;
        }
    }

    if (node_length > 0) {
        nodes[node_index][node_length] = '\0';
        node_index++;
    }

    char usergraphin[100];
    int graph[node_index][node_index];





    for (int i = 0; i < node_index; i++) {
        fgets(usergraphin, sizeof(usergraphin), stdin);

        int y = 0;
        int length = 0;
        int comnum = 0;
        for (int z = 0; usergraphin[z] != '\0'; z++) {
            if (usergraphin[z] == ',' || usergraphin[z] == '\n') {
                if (length > 0) {
                    char *endptr;
                    graph[i][y] = strtol(usergraphin + z - length, &endptr, 10);
                    if (*endptr != '\0' && *endptr != ',' && *endptr != '\n') {

                        invalids[4] = 1;

                    }
                } else {
                    graph[i][y] = 0;
                }
                y++;
                length = 0;
                if (usergraphin[z] == ',') {
                    comnum++;
                }
            } else if (isdigit(usergraphin[z])) {
                length++;
            } else if (usergraphin[z] != ' ') {

                invalids[4] = 1;

            }
        }
        if (comnum != node_index - 1) {

            invalids[4] = 1;

        }
    }

    char start_node_name[20];
    char destination_node_name[20];


    fgets(usergraphin, sizeof(usergraphin), stdin);

    if (sscanf(usergraphin, "%19[^,],%19s", start_node_name, destination_node_name) != 2) {

        invalids[3] = 1;

    }

    int start_index = -1;
    int destination_index = -1;
    for (int i = 0; i < node_index; i++) {
        if (strcmp(start_node_name, nodes[i]) == 0) {
            start_index = i;
        }
        if (strcmp(destination_node_name, nodes[i]) == 0) {
            destination_index = i;
        }
    }


    if (start_index == -1) {

        invalids[3] = 1;

    }


    if (destination_index == -1) {

        invalids[2] = 1;

    }


    if (start_index == destination_index) {

        invalids[1] = 1;

    }

    int start_node = start_index;
    int destination_node = destination_index;
    int distances[node_index];
    int predecessors[node_index];

    dijkstra_with_path(graph, node_index, start_node, destination_node, distances, predecessors);

    if (distances[destination_node] == INFINIX) {

        invalids[0] = 1;
    }


    if (invalids[4]) {
        printf("Invalid distance matrix.\n");
        return 5;
    } else if (invalids[3]) {
        printf("Invalid source station.\n");
        return 4;
    } else if (invalids[2]) {
        printf("Invalid destination station.\n");
        return 3;
    } else if (invalids[1]) {
        printf("No journey, same source and destination station.\n");
        return 2;
    } else if (invalids[0]) {
        printf("No possible journey.\n");
        return 1;
    }



    printf("%d,", distances[destination_node]);

    int num_intermediate_stations = 0;
    int current = destination_node;
    while (current != start_node) {
        current = predecessors[current];
        if (current != start_node) {
            num_intermediate_stations++;
        }
    }

    int cost = (int)ceil(1.2 * distances[destination_node] + 25 * num_intermediate_stations);

    printf("%d\n", cost);

    int path[node_index];
    int count = 0;
    current = destination_node;
    while (current != -1) {
        path[count++] = current;
        current = predecessors[current];
    }

    for (int i = count - 1; i > 0; i--) {
        printf("%s,", nodes[path[i]]);
    }
    printf("%s\n", nodes[path[0]]);

    return 0;
}

The proper output should be A,C,E,F, but my code outputs A,C,F (with distance as integer, and the second integer is cost/task requirment you can ignore) Now I tried to fix this using an external function to check possible paths then feed it to the dijkstra_with_path function as seen with the following code, but the output is still incorrect, its trying to go from C to F directly...

void find_possible_paths(int graph[MAX_NODES][MAX_NODES], int num_nodes, int possible_paths[MAX_NODES][MAX_NODES]) {
    // Initialize all paths as not possible
    for (int i = 0; i < num_nodes; i++) {
        for (int j = 0; j < num_nodes; j++) {
            // If there is a non-zero weight between the nodes, mark the path as possible
            if (graph[i][j] != 0) {
                possible_paths[i][j] = 1;
            }
            // If there is no weight (i.e., the weight is zero), mark the path as not possible
            else {
                possible_paths[i][j] = 0;
            }
        }
    }
}

void dijkstra_with_path(int graph[MAX_NODES][MAX_NODES], int num_nodes, int start, int destination, int distances[MAX_NODES], int predecessors[MAX_NODES], int possible_paths[MAX_NODES][MAX_NODES]) {
    int unvisited_nodes[MAX_NODES];
    int i, current_node, neighbor, distance;

    for (i = 0; i < num_nodes; i++) {
        distances[i] = INFINIX;
        predecessors[i] = -1;
        unvisited_nodes[i] = 1;
    }

    distances[start] = 0;

    while (1) {
        int min_distance = INFINIX;
        for (i = 0; i < num_nodes; i++) {
            if (unvisited_nodes[i] && distances[i] < min_distance) {
                min_distance = distances[i];
                current_node = i;
            }
        }

        if (min_distance == INFINIX) {
            break;
        }

        unvisited_nodes[current_node] = 0;

        for (neighbor = 0; neighbor < num_nodes; neighbor++) {
            if (possible_paths[current_node][neighbor]) {
                distance = distances[current_node] + graph[current_node][neighbor];
                if (distance < distances[neighbor]) {
                    distances[neighbor] = distance;
                    predecessors[neighbor] = current_node;
                }
            }
        }
    }
}

Here is the output I'm getting:

12,40
A,C,F

and the correct one should be A,C,E,F. I'd appreciate it if you can help me correct this issue as my understanding in C is very low, as I first tried to attempt this in python then convert it to C lmao (I know how beginner this sounds right now).

Here is my python implementation that works:

import heapq


def dijkstra_with_path(graph, start, destination):
    distances = {node: float('infinity') for node in graph}
    predecessors = {node: None for node in graph}

    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        if current_node == destination:
            break

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    path = []
    current = destination
    while current is not None:
        path.insert(0, current)
        current = predecessors[current]

    return distances[destination], path


graph = {
    "A": {"B": 4, "C": 5},
    "B": {"A": 4, "C": 11, "E": 7},
    "C": {"B": 11, "E": 3},
    "D": {"B": 9, "E": 13, "F": 2},
    "E": {"B": 7, "C": 3, "D":13, "F":6},
    "F": {"D": 2, "E": 6},
}

start_node = "A"
destination_node = "F"

shortest_distance, path = dijkstra_with_path(graph, start_node, destination_node)

print(f"Shortest distance from {start_node} to {destination_node}: {shortest_distance}")
print(f"Shortest path: {' -> '.join(path)}")

Answer 1

The main problem is mismatched array dimensions. In dijkstra_with_path, the graph parameter is declared as int graph[MAX_NODES][MAX_NODES] (it will be automatically adjusted to int (*graph)[MAX_NODES]), but the argument of the function call from main is graph that is declared as int graph[node_index][node_index] (the argument will be converted to type int (*)[node_index]). The array indexing operations on the graph parameter inside the dijkstra_with_path function will be incorrect when node_index does not equal MAX_NODES. For example, when MAX_NODES is 10 and node_index is 6, graph[2][2] inside the dijkstra_with_path function will be at the same location as graph[3][4] inside the main function. This is because 2×10+2 equals 3×6+4. In general, for a 2-D array with dimensions [numrows][numcolumns], the element [row][column] in the 2-D array is at the same offset from the start of the array as the element [row × numcolumns + column] is from the start of a 1-D array of the same base type.

One way to fix it would be to change int graph[node_index][node_index]; in main to int graph[node_index][MAX_NODES]; or int graph[MAX_NODES][MAX_NODES]; so that the number of columns matches that expected by the dijkstra_with_path function.

Another (more flexible) way to fix it is to keep int graph[node_index][node_index]; in main as-is, and change the dijkstra_with_path function to use a variably modified type for the graph parameter. This will require some rearrangement of the dijkstra_with_path function parameters as follows:

void dijkstra_with_path(int num_nodes, int graph[num_nodes][num_nodes], int start, int destination, int distances[num_nodes], int predecessors[num_nodes])

Also change int unvisited_nodes[MAX_NODES]; to int unvisited_nodes[num_nodes]; for consistency (but it doesn't matter as long as num_nodes is not greater than MAX_NODES).

Then in main, since graph has been declared as int graph[node_index][node_index];, change the function call to dijkstra_with_path(node_index, graph, start_node, destination_node, distances, predecessors);.