binaryheap.cpp

#include "binaryheap.h"

// Create graph
Graph* create_graph(int num_nodes) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->num_nodes = num_nodes;
    graph->adj_list = (AdjNode**)malloc(num_nodes * sizeof(AdjNode*));

    for (int i = 0; i < num_nodes; i++)
        graph->adj_list[i] = NULL;

    return graph;
}

// Add edge
void add_edge(Graph* graph, int u, int v, int weight) {
    // Edge from u to v
    AdjNode* new_node = (AdjNode*)malloc(sizeof(AdjNode));
    new_node->vertex = v;
    new_node->weight = weight;
    new_node->next = graph->adj_list[u];
    graph->adj_list[u] = new_node;
}

// Free graph memory
void free_graph(Graph* graph) {
    for (int i = 0; i < graph->num_nodes; i++) {
        AdjNode* current = graph->adj_list[i];
        while (current != NULL) {
            AdjNode* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(graph->adj_list);
    free(graph);
}

// Create min heap
MinHeap* create_min_heap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->array = (HeapNode*)malloc(capacity * sizeof(HeapNode));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// Swap heap nodes
void swap_heap_nodes(HeapNode* a, HeapNode* b) {
    HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

// Min heapify
void min_heapify(MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left].distance < heap->array[smallest].distance)
        smallest = left;

    if (right < heap->size && heap->array[right].distance < heap->array[smallest].distance)
        smallest = right;

    if (smallest != idx) {
        swap_heap_nodes(&heap->array[idx], &heap->array[smallest]);
        min_heapify(heap, smallest);
    }
}

// Check if heap is empty
int is_empty(MinHeap* heap) {
    return heap->size == 0;
}

// Extract minimum element
HeapNode extract_min(MinHeap* heap) {
    if (heap->size <= 0) {
        HeapNode empty = { INF, -1 };
        return empty;
    }

    HeapNode root = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    min_heapify(heap, 0);

    return root;
}

// Decrease key 
void decrease_key(MinHeap* heap, int vertex, int distance) {
    // directly insert new node, let old node expire naturally
    if (heap->size >= heap->capacity) {
        // Expand heap capacity
        heap->capacity *= 2;
        heap->array = (HeapNode*)realloc(heap->array, heap->capacity * sizeof(HeapNode));
    }

    heap->array[heap->size].distance = distance;
    heap->array[heap->size].vertex = vertex;
    heap->size++;

    // Bubble up the newly inserted node
    int i = heap->size - 1;
    while (i != 0 && heap->array[(i - 1) / 2].distance > heap->array[i].distance) {
        swap_heap_nodes(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Dijkstra algorithm implementation
void dijkstra(Graph* graph, int src, int* dist, int* prev) {
    int num_nodes = graph->num_nodes;

    // Initialize distance and predecessor arrays
    for (int i = 0; i < num_nodes; i++) {
        dist[i] = INF;
        prev[i] = -1;
    }
    dist[src] = 0;

    // Create min heap
    MinHeap* heap = create_min_heap(num_nodes);

    // Insert source node
    decrease_key(heap, src, 0);

    // Record whether node has been processed
    int* visited = (int*)calloc(num_nodes, sizeof(int));

    while (!is_empty(heap)) {
        // Extract node with minimum distance
        HeapNode min_node = extract_min(heap);
        int u = min_node.vertex;

        // Skip if node has been processed or distance is invalid
        if (visited[u] || min_node.distance == INF)
            continue;

        visited[u] = 1;

        // Traverse all neighbors
        AdjNode* neighbor = graph->adj_list[u];
        while (neighbor != NULL) {
            int v = neighbor->vertex;
            int weight = neighbor->weight;

            if (!visited[v]) {
                int new_dist = dist[u] + weight;

                // If a shorter path is found
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    prev[v] = u;
                    decrease_key(heap, v, new_dist);
                }
            }
            neighbor = neighbor->next;
        }
    }

    free(visited);
    free(heap->array);
    free(heap);
}

// Print path
void print_path(int* prev, int target) {
    if (prev[target] == -1) {
        printf("%d", target);
        return;
    }
    print_path(prev, prev[target]);
    printf(" -> %d", target);
}

// Reconstruct path
void reconstruct_path(int* prev, int target, int* path, int* path_length) {
    *path_length = 0;
    int current = target;

    // Trace path backwards
    while (current != -1) {
        path[(*path_length)++] = current;
        current = prev[current];
    }

    // Reverse path
    for (int i = 0; i < *path_length / 2; i++) {
        int temp = path[i];
        path[i] = path[*path_length - i - 1];
        path[*path_length - i - 1] = temp;
    }
}

// Compute shortest path to a specific target
int shortest_path_length(Graph* graph, int src, int target, int* path, int* path_length) {
    int num_nodes = graph->num_nodes;
    int* dist = (int*)malloc(num_nodes * sizeof(int));
    int* prev = (int*)malloc(num_nodes * sizeof(int));

    dijkstra(graph, src, dist, prev);

    int distance = dist[target];

    if (distance != INF)
        reconstruct_path(prev, target, path, path_length);
    else
        *path_length = 0;

    free(dist);
    free(prev);

    return distance;
}