fibonacci_dijkstra.cpp

#include "fibonacciheap.h"
#include "binaryheap.h"

// Dijkstra's algorithm using Fibonacci heap
void dijkstra_fibonacci(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 Fibonacci heap and node pointer array
    FibonacciHeap* heap = create_fib_heap();
    FibNode** node_ptrs = (FibNode**)malloc(num_nodes * sizeof(FibNode*));

    // Initialize node pointer array
    for (int i = 0; i < num_nodes; i++) {
        node_ptrs[i] = NULL;
    }

    // Insert source node
    node_ptrs[src] = create_fib_node(src, 0);
    fib_heap_insert(heap, node_ptrs[src]);

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

    while (!is_fib_heap_empty(heap)) {
        // Extract node with minimum distance
        FibNode* min_node = fib_heap_extract_min(heap);
        int u = min_node->vertex;

        // Skip processed nodes or invalid distances
        if (visited[u] || min_node->distance == INF) {
            free(min_node);
            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;

                    if (node_ptrs[v] == NULL) {
                        // First visit to this node, insert into heap
                        node_ptrs[v] = create_fib_node(v, new_dist);
                        fib_heap_insert(heap, node_ptrs[v]);
                    }
                    else {
                        // Update node distance in heap
                        fib_heap_decrease_key(heap, node_ptrs[v], new_dist);
                    }
                }
            }
            neighbor = neighbor->next;
        }

        // Free processed node
        free(min_node);
        node_ptrs[u] = NULL;
    }

    // Clean up memory
    free(visited);
    free(node_ptrs);
    free_fib_heap(heap);
}

// Compute shortest path to a specific target using Fibonacci heap
int shortest_path_length_fibonacci(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_fibonacci(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;
}