dijkstra.c

// Dijkstra's Pathfinding Algorithm (Matrix Edition)

// Import Libraries
#include <stdio.h>
#include <stdlib.h>

// Define Constants
#define INFINITY 2147483647
#define NEG_INFINITY -2147483647
#define true 1
#define false 0

// Decide on weather to compile main (Used as library or used in standalone)
// !!Comment out if used as library to prevent main redefinition!! 
#define _DEFMAIN


// Printer Function for printing all values in a distance array
void printDistances(int *dist, int size){
    printf("Vertex with Distance from Source\n");
    for(int node = 0; node < size; node++){
        printf("%d -> %d\n", node, dist[node]);
    }
}


// Function to get the shortest valid node
int shortestNode(int *dist, int *checked, int size){
    int min = INFINITY;
    int minIndex;
    // Loop through every node
    for(int i = 0; i < size; i++){
        // Check if its the new smallest node and it has not already been checked off.
        if(dist[i] < min && checked[i] == false){
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}


// The meat of the the algorithm
// Takes In:
// map -> Pointer of 2d matrix of distances between nodes
// cMap -> Pointer of 2d matrix of Connectivity Booleans
// size -> Size of 2d matrix (Number of nodes)
// start -> Starting Node
int * dijkstra(int *map, int *cMap, int size, int start){
    // Distance Array -> Contains Values Of Current Smallest Distances
    int * dist = (int*)malloc(sizeof(int) * size);
    // Set all to infinity
    for(int i = 0; i < size; i++){dist[i] = INFINITY;}

    // Checked Array -> Indicates What Nodes Have Already Been Checked
    // Using calloc to pre-generate with all zeros
    int * checked = (int*)calloc(size, sizeof(int));

    // Set the distance of the starting node to 0
    dist[start] = 0;

    // Loop Through size Times To Go Through All From Nodes
    for(int cout = 0; cout < size; cout++){
        // Get Smallest Node In Distance Array
        int from = shortestNode(dist, checked, size);
        checked[from] = true;
        // Go Through Each Node, Checking Connections
        for(int to = 0; to < size; to++){
            // For navigating 2d arrays, using `(from*size) + to`
            // AKA `(rows*size + column)`

            // Checking If:
            // The Nodes Are Connected (using cMap)
            // The New Node Pair Are The Smallest Value
            // Checked Status Of To Node Is False
            if(cMap[(from*size) + to] == true && dist[to] > dist[from] + map[(from*size) + to] && checked[to] == false){
                // Change Distance To New Shortest Value
                dist[to] = dist[from] + map[(from*size) + to];
            }
        }
    }

    // Free Allocated Memory (Checked Array)
    free(checked);

    // Return Distance Array Pointer
    return dist;
}


#ifdef _DEFMAIN  // Check if main should be compiled
int main(){

    // Demo Values
    int map[9][9] = {
    {0, 4, 0, 0, 0, 0, 0, 8, 0}, 
    {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
    {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
    {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
    {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
    {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
    {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
    {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
    {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    int cMap[9][9] = {
    {0, 1, 0, 0, 0, 0, 0, 1, 0}, 
    {1, 0, 1, 0, 0, 0, 0, 1, 0}, 
    {0, 1, 0, 1, 0, 1, 0, 0, 1}, 
    {0, 0, 1, 0, 1, 1, 0, 0, 0}, 
    {0, 0, 0, 1, 0, 1, 0, 0, 0}, 
    {0, 0, 1, 1, 1, 0, 1, 0, 0}, 
    {0, 0, 0, 0, 0, 1, 0, 1, 1}, 
    {1, 1, 0, 0, 0, 0, 1, 0, 1}, 
    {0, 0, 1, 0, 0, 0, 1, 1, 0}};

    // Run Dijkstras And Get Result
    int * result = dijkstra(
        &map[0][0],  // Distance Map
        &cMap[0][0],  // Connectivity Map
        9,  // Size of Maps / Matrix
        0  // Starting Node
    );
    
    // Printing Final Values
    printDistances(result, 9);

    // Free result
    free(result);

    // Expected Output:
    /*
    Vertex with Distance from Source
    0 -> 0
    1 -> 5
    2 -> -2147483647
    3 -> -2147483647
    4 -> -2147483647
    5 -> 35
    6 -> 40
    7 -> -10
    8 -> -20
    9 -> -2147483647
    */
}	
#endif  // _DEFMAIN