Multiple-Weighted Graph Elimination

I have a multiple weighted graph. Each between nodes are showing the paths from a city to another city and each edge have a time, distance and cost. The user should enter a start and an end point and a criteria for the path (time, distance, and cost). Once the program get this,it should traverse and remove redundant nodes between a current node and the next while traversing from Starting Node to the Ending Node based on the criteria chosen. Here, a redundant node means that the second or the third connection to the same next node to reach to the final node with worse values. Here, worse means longer time, more costly, or longer distance.
I have tried different methods like converting to a simple one-weighted graph, using Dijkstra and using arrays for storing the edge values but non of them give me the desired output. Can you suggest me the most time and space efficient algorithm to do this task?
this is one of the codes I have written. This code works for path from 1-4 but for the other paths, it shows the wrong result and while debugging I understand that the problem is related to the current and next_vertex value.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 40
enum color { White, Gray, Black };
typedef struct list_node {
int index;
int time;
int distance;
int cost;
struct list_node* next;
} list_node;
typedef struct node {
int data;
enum color color;
list_node* head;
} node;
typedef struct graph {
int nVertices;
node heads[];
} graph;
node* new_node(int data) {
node* z = (node*)malloc(sizeof(node));
z->data = data;
z->head = NULL;
z->color = White;
return z;
}
list_node* new_list_node(int item_index, int time, int distance, int cost) {
list_node* z = (list_node*)malloc(sizeof(list_node));
z->index = item_index;
z->time = time;
z->distance = distance;
z->cost = cost;
z->next = NULL;
return z;
}
graph* new_graph(int nVertices) {
graph* g = (graph*)malloc(sizeof(graph) + (nVertices * sizeof(node)));
g->nVertices = nVertices;
int i;
for (i = 0; i < nVertices; i++) {
node* z = new_node(-1);
g->heads[i] = *z;
}
return g;
}
void add_node_to_graph(graph* g, int data) {
node* z = new_node(data);
int i;
for (i = 0; i < g->nVertices; i++) {
if (g->heads[i].data < 0) {
g->heads[i] = *z;
break;
}
}
}
int in_graph_head_list(graph* g, int data) {
int i;
for (i = 0; i < g->nVertices; i++) {
if (g->heads[i].data == data)
return 1;
}
return 0;
}
void AddEdges(graph* g, int source, int dest, int time, int distance, int cost) {
if (!in_graph_head_list(g, source)) {
add_node_to_graph(g, source);
}
if (!in_graph_head_list(g, dest)) {
add_node_to_graph(g, dest);
}
int i, j;
for (i = 0; i < g->nVertices; i++) {
if (g->heads[i].data == source) {
int indexDest = -1;
for (j = 0; j < g->nVertices; j++) {
if (g->heads[j].data == dest) {
indexDest = j;
break;
}
}
if (indexDest != -1) {
list_node* n = new_list_node(indexDest, time, distance, cost);
if (g->heads[i].head == NULL) {
g->heads[i].head = n;
}
else {
list_node* temp = g->heads[i].head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
}
}
break;
}
}
}
void printgraph(graph* g) {
int i;
for (i = 0; i < g->nVertices; i++) {
node* curr_node = &(g->heads[i]);
printf("Node %d: ", curr_node->data);
list_node* temp = curr_node->head;
if (temp == NULL) {
printf("No adjacent nodes.\n");
}
else {
while (temp != NULL) {
int adjacent_vertex = g->heads[temp->index].data;
printf("%d (T=%d, D=%d, C=%d)", adjacent_vertex, temp->time, temp->distance, temp->cost);
temp = temp->next;
if (temp != NULL) {
printf(" --> ");
}
}
printf("\n");
}
}
}
void print_updated_graph(graph* g) {
printf("Updated Graph:\n");
for (int i = 0; i < g->nVertices; i++) {
node* curr_node = &(g->heads[i]);
printf("Node %d: ", curr_node->data);
list_node* temp = curr_node->head;
if (temp == NULL) {
printf("No adjacent nodes.\n");
} else {
while (temp != NULL) {
int adjacent_vertex = g->heads[temp->index].data;
printf("%d (T=%d, D=%d, C=%d)", adjacent_vertex, temp->time, temp->distance, temp->cost);
temp = temp->next;
if (temp != NULL) {
printf(" --> ");
}
}
printf("\n");
}
}
}
void eliminate_edges(graph* g, int current, int next_vertex, int choice, int* edge_values) {
node* curr_node = &(g->heads[current - 1]); // Adjusted for 0-based indexing
list_node* temp = curr_node->head;
list_node* prev = NULL;
while (temp != NULL) {
int adjacent_vertex = temp->index + 1; // Adjusted for 1-based indexing
// Check if the adjacent vertex is not the next_vertex
if (adjacent_vertex != next_vertex + 1) {
// Check the chosen weight for elimination
switch (choice) {
case 1: // Time
if (temp->time >= edge_values[0]) {
if (prev == NULL) {
curr_node->head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
} else {
prev = temp;
}
break;
case 2: // Distance
if (temp->distance > edge_values[1]) { // Use > instead of >=
if (prev == NULL) {
curr_node->head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
} else {
prev = temp;
}
break;
case 3: // Cost
if (temp->cost >= edge_values[2]) {
if (prev == NULL) {
curr_node->head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
} else {
prev = temp;
}
break;
}
}
temp = temp->next;
}
}
void find_path(graph* g, int current, int end, int* visited, int* path, int path_length, int choice) {
visited[current] = 1;
path[path_length] = current;
path_length++;
if (current == end) {
// Found a path from start to end
printf("Path: ");
for (int i = 0; i < path_length - 1; i++) {
printf("%d ", path[i]);
}
printf("%d\n", path[path_length - 1]);
// Print edge values
for (int i = 0; i < path_length - 1; i++) {
node* curr_node = &(g->heads[path[i] - 1]);
list_node* temp = curr_node->head;
while (temp != NULL) {
if (temp->index + 1 == path[i + 1]) {
printf("Edge (%d, %d): (T=%d, D=%d, C=%d)\n", path[i], path[i + 1], temp->time, temp->distance, temp->cost);
break;
}
temp = temp->next;
}
}
printf("\n");
} else {
node* curr_node = &(g->heads[current - 1]); // Adjusted for 0-based indexing
list_node* temp = curr_node->head;
int next_vertex = temp->index + 1; // Adjusted for 1-based indexing
int* path_visited = calloc(g->nVertices + 1, sizeof(int)); // Array to track visited vertices within the current path
int multiple_paths = 0; // Variable to track multiple paths
int edge_values[3] = { INT_MAX, INT_MAX, INT_MAX }; // Array to store edge values for comparison
while (temp != NULL) {
int adjacent_vertex = temp->index + 1; // Adjusted for 1-based indexing
if (!visited[adjacent_vertex]) {
if (path_visited[adjacent_vertex]) {
multiple_paths = 1;
break;
}
path_visited[adjacent_vertex] = 1;
next_vertex++;
// Store edge values for comparison
if (temp->time < edge_values[0])
edge_values[0] = temp->time;
if (temp->distance < edge_values[1])
edge_values[1] = temp->distance;
if (temp->cost < edge_values[2])
edge_values[2] = temp->cost;
}
temp = temp->next;
}
// Check if there are multiple paths from the current vertex to the next adjacent vertex
if (multiple_paths) {
eliminate_edges(g, current, next_vertex, choice, edge_values);
}
temp = curr_node->head; // Reset the temp pointer
while (temp != NULL) {
int adjacent_vertex = temp->index + 1; // Adjusted for 1-based indexing
if (!visited[adjacent_vertex]) {
find_path(g, adjacent_vertex, end, visited, path, path_length, choice);
}
temp = temp->next;
}
free(path_visited);
}
visited[current] = 0;
path_length--;
}
int main() {
graph* g = new_graph(4);
printf("Welcome to the trip graph.\n");
printf("The trip roads are as below.\n\n");
AddEdges(g, 1, 2, 1, 1, 1);
AddEdges(g, 1, 3, 1, 1, 1);
AddEdges(g, 2, 4, 1, 4, 5);
AddEdges(g, 2, 3, 3, 2, 1);
AddEdges(g, 2, 1, 2, 1, 3);
AddEdges(g, 3, 1, 7, 1, 4);
AddEdges(g, 3, 1, 1, 3, 2);
AddEdges(g, 3, 4, 4, 3, 1);
AddEdges(g, 3, 4, 1, 7, 6);
AddEdges(g, 4, 4, 5, 3, 2);
AddEdges(g, 4, 3, 1, 1, 1);
AddEdges(g, 4, 2, 1, 4, 5);
printgraph(g);
int start, end;
while (1) {
printf("\nEnter your starting Node for elimination (press -1 to exit): ");
scanf("%d", &start);
if (start == -1) {
break;
}
printf("Enter the ending node: ");
scanf("%d", &end);
int choice;
while (1) {
printf("\nBased on what do you want to do the elimination?\n");
printf("1. Time 2. Distance 3. Cost\n");
scanf("%d", &choice);
printf("\nAll paths from %d to %d:\n", start, end);
if (choice >= 1 && choice <= 3) {
break;
} else {
printf("Invalid choice. Please try again.\n");
}
}
int* visited = calloc(g->nVertices + 1, sizeof(int)); // Array to track visited vertices
int* path = calloc(g->nVertices + 1, sizeof(int)); // Array to store the current path
find_path(g, start, end, visited, path, 0, choice);
free(visited);
free(path);
print_updated_graph(g); 
}
return 0;
}