Creating dijkstras algorithm and having issues in C language
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)}")
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);.
- Why is the '&' operator needed for an int variable but not for an array in C?
- The `write` syscall in C writes to an unexpected position
- populating an array at compile time in C
- Why does carg(-0) return -pi?
- Why is the initialization of this structure global variable wrong?
- Efficient linked list design for a C file manager
- Function with a malloc on a pointer declared in main()
- structure padding on 64bit machine
- Malloc and memcpy struct plus array
- PInvoke has unbalanced the stack
- fast check if the difference between two int32_t is 1 or 0
- Is there any difference between stating the "alignas" keyword in struct definition VS array of struct definition?
- Is it possible to read a file in parallel by extending this function?
- How to organize the receive msg and user current input in C network such that it's clean
- How to use regular expressions in C
- Is there a cross-platform way to determine if a device is powered via PSU or external battery in C?
- jmp to address in inline AVR C
- How to compile x64 code with Visual Studio in command line?
- Difference between target and target data? How to do teams/threads configurations without teams directive?
- cast without * operator
- Are different translation units allowed to define structures with the same name?
- Not a constant initializer element?
- 2 Functions in 1 main program(Visual Studio 2013)
- Using free with pointer to middle of allocation
- How does C/CPP know how to point to "next" struct node when the struct node is not yet defined?
- why does linker have a tougher task in C++ compared to C?
- Is a 32 bit integer on a 16 bit machine possible?
- g-wan not updating dependencies of servlets
- Compiler circular reference
- Compiling Options in Code Blocks