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 portable is code with #pragma optimize?
- Make warn_unused_result applied to all function with GCC
- Multiple threads and CPU cache
- Linking error vs. compilation error
- how to compile multiple instances of a source file linking to it different files.o
- Background compile in VS2010 and C/C++
- What Turing complete macro languages are available for C/C++
- How to use Cython to compile Python 3 into C
- Are forward declarations needed when the typedef declaration is done?
- How to assign real and imaginary parts of complex variables in C
- Strict aliasing between Complex numbers and real numbers in C
- How to CORRECTLY install gsl library in Linux?
- Using = operator on atomic variable?
- Unknown conversion types in this program I'm meant to compile
- Iterator in C language
- Treating __func__ as a string literal instead of a predefined identifier
- c - strcpy with struct string returning error
- Segmentation fault when executing a Python script in a C program?
- Questions about C Function Prototypes and Compilation
- What is the purpose of "-Wa,option" in GCC?
- Do we have c99 subflags
- netcat gcc compile option so that IDA pro can show function name
- What is the correct way to free output buffer after call to openssl::i2d_X509?
- How can I link C++ files to a C program?
- Why doesn't this program in C compile? Error: undefined reference to `i2c_smbus_read_byte_data'
- integer promotion isn't taken into account
- Why do I get a SEGFAULT when I try to sort an array of integers using K & R code examples?
- Are C preprocessor statements a part of the C language?
- FFMPEG Api conversion from YUV420P to RGB produces strange output
- Why is the tree constructed this way incorrect?