Weighted Graphs

Question

I was wondering what is the problem in the code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_ROOMS 100 // Maximum number of rooms in the map
#define INF INT_MAX   // Infinity value for distances

// Structure to represent an edge in the graph
typedef struct {
    int source;
    int destination;
    int weight;
} Edge;

// Structure to represent a graph
typedef struct {
    int numRooms;
    int numEdges;
    Edge edges[MAX_ROOMS * MAX_ROOMS]; // Assuming each room can be connected to all other rooms
} Graph;

// Structure to represent a queue node for BFS
typedef struct {
    int vertex;
    int distance;
} QueueNode;

// Structure to represent a queue
typedef struct {
    int front, rear;
    int capacity;
    QueueNode* array;
} Queue;

// Function to create a new queue
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->rear = -1;
    queue->array = (QueueNode*)malloc(queue->capacity * sizeof(QueueNode));
    return queue;
}

// Function to check if the queue is empty
bool isEmpty(Queue* queue) {
    return queue->front == -1;
}

// Function to add an element to the queue
void enqueue(Queue* queue, int vertex, int distance) {
    QueueNode newNode;
    newNode.vertex = vertex;
    newNode.distance = distance;
    queue->array[++queue->rear] = newNode;
    if (queue->front == -1) {
        queue->front = 0;
    }
}

// Function to remove an element from the queue
QueueNode dequeue(Queue* queue) {
    QueueNode node = queue->array[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    }
    else {
        queue->front++;
    }
    return node;
}

// Function to read the map from a text file and construct the graph
Graph readMapFromFile(const char* filename) {
    FILE* file;
    errno_t err = fopen_s(&file, filename, "r");
    if (err != 0) {
        printf("Error opening file.\n");
        exit(EXIT_FAILURE);
    }

    Graph graph;
    fscanf_s(file, "%d %d", &graph.numRooms, &graph.numEdges);
    for (int i = 0; i < graph.numEdges; i++) {
        fscanf_s(file, "%d %d %d", &graph.edges[i].source, &graph.edges[i].destination, &graph.edges[i].weight);
    }
    fclose(file);

    return graph;
}

// Function to perform BFS and find the center of Harry's friends' component
int bfsFindCenterOfFriendsComponent(Graph graph, int mainSourceRoom, int* numFriends) {
    // Initialize distances array
    int distances[MAX_ROOMS];
    for (int i = 0; i < graph.numRooms; i++) {
        distances[i] = INF;
    }

    // Initialize visited array
    bool visited[MAX_ROOMS] = { false };

    // Perform BFS
    Queue* queue = createQueue(graph.numRooms);
    enqueue(queue, mainSourceRoom, 0);
    visited[mainSourceRoom] = true;
    distances[mainSourceRoom] = 0;

    while (!isEmpty(queue)) {
        QueueNode current = dequeue(queue);
        int currentRoom = current.vertex;
        int currentDistance = current.distance;

        for (int i = 0; i < graph.numEdges; i++) {
            if (graph.edges[i].source == currentRoom) {
                int neighbor = graph.edges[i].destination;
                int weight = graph.edges[i].weight;

                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distances[neighbor] = currentDistance + weight;
                    enqueue(queue, neighbor, distances[neighbor]);
                }
            }
        }
    }

    // Find the farthest room from the main source room
    int farthestRoom = mainSourceRoom;
    int maxDistance = 0;
    for (int i = 0; i < graph.numRooms; i++) {
        if (distances[i] > maxDistance && distances[i] != INF) {
            maxDistance = distances[i];
            farthestRoom = i;
        }
    }

    // Now, we perform BFS again starting from the farthest room to find the center
    // This time, we use the farthest room as the source
    // We calculate distances from the farthest room to all other rooms
    // The room with the minimum maximum distance to other rooms will be the center

    // Reset distances array
    for (int i = 0; i < graph.numRooms; i++) {
        distances[i] = INF;
    }

    // Reset visited array
    for (int i = 0; i < graph.numRooms; i++) {
        visited[i] = false;
    }

    // Perform BFS from the farthest room
    enqueue(queue, farthestRoom, 0);
    visited[farthestRoom] = true;
    distances[farthestRoom] = 0;

    while (!isEmpty(queue)) {
        QueueNode current = dequeue(queue);
        int currentRoom = current.vertex;
        int currentDistance = current.distance;

        for (int i = 0; i < graph.numEdges; i++) {
            if (graph.edges[i].source == currentRoom) {
                int neighbor = graph.edges[i].destination;
                int weight = graph.edges[i].weight;

                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distances[neighbor] = currentDistance + weight;
                    enqueue(queue, neighbor, distances[neighbor]);
                }
            }
        }
    }

    // Find the room with the minimum maximum distance to other rooms
    int centerRoom = farthestRoom;
    int minMaxDistance = INF;
    for (int i = 0; i < graph.numRooms; i++) {
        if (distances[i] != INF && distances[i] < minMaxDistance) {
            minMaxDistance = distances[i];
            centerRoom = i;
        }
    }

    *numFriends = 0;
    // Count the number of friends (rooms with non-INF distances to the center)
    for (int i = 0; i < graph.numRooms; i++) {
        if (distances[i] != INF && i != centerRoom) {
            (*numFriends)++;
        }
    }

    // Return the center room of Harry's friends' component
    return centerRoom;
}
// Function to find the shortest path from source to destination using Dijkstra's algorithm
void dijkstraShortestPath(int source, int destination, Graph graph) {
    int distances[MAX_ROOMS];
    bool visited[MAX_ROOMS]; // Added

    // Initialize distances and visited arrays
    for (int i = 0; i < graph.numRooms; i++) {
        distances[i] = INF;
        visited[i] = false;
    }

    // Set distance of source to 0
    distances[source] = 0;

    // Dijkstra's algorithm
    for (int count = 0; count < graph.numRooms - 1; count++) {
        int minDistance = INF;
        int minIndex = -1;

        // Find vertex with minimum distance
        for (int v = 0; v < graph.numEdges; v++) { // Iterate over the number of edges
            if (!visited[v] && distances[v] <= minDistance) {
                minDistance = distances[v];
                minIndex = v;
            }
        }

        // Mark the picked vertex as visited
        visited[minIndex] = true;

        // Update distance value of the adjacent vertices
        for (int v = 0; v < graph.numEdges; v++) { // Iterate over the number of edges
            if (!visited[v] && graph.edges[v].weight && distances[minIndex] != INF && distances[minIndex] + graph.edges[minIndex].weight < distances[v]) {
                distances[v] = distances[minIndex] + graph.edges[minIndex].weight;
            }
        }
    }

    // Print the shortest distance from source to destination
    printf("Shortest distance from %d to %d: %d\n", source, destination, distances[destination]);
}


int main() {
    const char* filename = "g1-8.txt"; // Change this to the name of your map file

    // Step 1: Read the map from the file and construct the graph
    Graph graph = readMapFromFile(filename);

    // Step 2: Identify the main source room
    int mainSourceRoom = 0; // Assume the first room as the main source room

    // Step 3: Find the center of Harry's friends' component
    int numFriends = 0; // Number of Harry's friends
    int friendsComponentCenter = bfsFindCenterOfFriendsComponent(graph,             mainSourceRoom, &numFriends); // Implement this function

    // Step 4: Find the shortest path from the main source to Harry's room
    int harrysRoom = friendsComponentCenter; // Placeholder
    dijkstraShortestPath(mainSourceRoom, harrysRoom, graph);

    // Step 5: Print out the questions and their answers
    printf("2.1. In which room does Harry find himself lost, in the beginning? Room %d\n", mainSourceRoom);
    printf("2.2. How many friends does Harry have on this map? %d\n", numFriends);
    printf("2.3. What vertex is Harry's dorm room? Room %d\n", harrysRoom);
    printf("2.4. What is a path with the least energy spending to safely reach his room? [Main Source Room -> Harry's Room]\n");
    printf("2.5. How much energy does the path consume (or gain)? 0 \n(Since the distance from the main source room to Harry's room is 0)\n");

    return 0;
}

The graph I used is :

0 3 0 5 0 2 0 0
0 0 -4 0 0 0 0 0
0 0 0 0 0 0 0 4
0 0 0 0 6 0 0 0
0 0 0 -3 0 0 0 8
0 0 0 0 0 0 3 0
0 0 0 0 0 -6 0 7
0 0 0 0 0 0 0 0

But there is also another graph which is:

0 2 0 0 1 0 0 0 0 0 0 0 2
0 0 0 0 0 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 -2 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 -2 0 0 0 0
0 -2 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 -2 0 0 0 0 0 0 0 0
2 4 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0
0 0 -1 0 0 0 7 0 0 0 0 0 0
0 0 0 3 0 0 0 0 0 0 3 0 3
0 0 2 0 0 0 0 0 0 3 0 0 0

The result is:

Shortest distance from 0 to 0: 0

1. In which room does Harry find himself lost, in the beginning? Room 0
2. How many friends does Harry have on this map? 0
3. What vertex is Harry's dorm room? Room 0
4. What is a path with the least energy spending to safely reach his room? [Main Source Room -> Harry's Room]
5. How much energy does the path consume (or gain)? 0 (Since the distance from the main source room to Harry's room is 0)

But its not quite right so anyone capable for helping me here?