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);.
- How to iterate through an array of pointer in c
- Populating dropdown with strings in GTK4
- loop 2 taking input automatically
- Why is GNU GLIBC strsignal() considered thread unsafe on modern operating systems?
- How to find first two digits in C
- Expose only required functions in C
- gcc Console output newline
- How to create file as another user via C/C++ in Linux?
- Problem: Peg Solitaire Solution with Backtracking in C
- How to use double pointers (pointer to pointer) for an array of structures properly in standard C?
- How to retrieve function pointer from inside function in C?
- Multi-line DEFINE directives?
- Different compilers... Will I need to install redistributable libraries for all?
- Linker and Memory map for shared memory in autosar embedded environment
- Can not use sched_setaffinity() on macOS
- Comparison between a pointer and an integer in C
- Why do the 32-bit and 64-bit Compiled Versions of this Program Populate Memory in this Way?
- How can the Linux kernel compile itself?
- How do I compile the asm generated by GCC?
- strcmp with pointers not working in C
- Compiler Error when using a struct
- How to enforce the struct bit order with the GCC compiler?
- In C, extract mantissa of a double as a long long in portable way
- Why is sizeof(HEADER_SIZE) = 4 when it was initialized as 44?
- "Palindrome recursive function" detects palindromes right but doesn't behave as expected
- what is the reason for explicitly declaring L or UL for long values
- TCP/IP Programming in C
- Is this unstable behavior of execve after vfork a gcc bug?
- Is a char array more efficient than a char pointer in C?
- "incompatible pointer type" compiling in C