Simple Dijkstra in C

README.md

make && ./dijkstra

main.c

#include <stdio.h> // use printf
#include <limits.h> // use UINT_MAX
#include <string.h> // use strcmp
#include <stdbool.h> // use bool
#include <assert.h> // use assert

struct Node {
    const char* name;
    // UINT_MAX for maxcimum distance
    unsigned int distance;
    bool visited;
    // To reverse the path
    struct Node* nearestNode;
};

struct Edge {
    const char* a;
    const char* b;
    int weight;
};

void printNodes(struct Node* nodes, unsigned int NODES_LENGTH) {
    printf("Nodes: ");
    for (unsigned int i = 0; i < NODES_LENGTH; i++) {
        printf("(%s|%u|%c|%s)",
            nodes[i].name,
            nodes[i].distance,
            nodes[i].visited ? 'X' : ' ',
            nodes[i].nearestNode != NULL ? nodes[i].nearestNode->name : ""
        );
        if (i != NODES_LENGTH - 1) {
            printf(", ");
        }
    }
    printf("\n");
}

void printEdges(struct Edge* edges, unsigned int EDGES_LENGTH) {
    printf("Edges: ");
    for (unsigned int i = 0; i < EDGES_LENGTH; i++) {
        printf("(%s->%s|%u)", edges[i].a, edges[i].b, edges[i].weight);
        if (i != EDGES_LENGTH - 1) {
            printf(", ");
        }
    }
    printf("\n");
}

struct Node* getNearestNode(struct Node* nodes, unsigned int NODES_LENGTH) {
    struct Node* nearestNode = NULL;
    for (unsigned int i = 0; i < NODES_LENGTH; i++) {
        // If node was visited skip
        if (nodes[i].visited) continue;
        // If node has a longer distance skip
        if (nearestNode != NULL && nodes[i].distance >= nearestNode->distance) continue;
        // Otherwise make this the nearest node
        nearestNode = &nodes[i];
    }
    return nearestNode;
}

struct Node* getNodeByName(struct Node* nodes, unsigned int NODES_LENGTH, const char* name) {
    for (unsigned int i = 0; i < NODES_LENGTH; i++) {
        if (strcmp(nodes[i].name, name) == 0) return &nodes[i];
    }
    return NULL;
}

void dijkstra(struct Node* nodes, unsigned int NODES_LENGTH, struct Edge* edges, unsigned int EDGES_LENGTH, bool undirected) {
    struct Node* nearestNode = NULL;
    while (true) {
        printNodes(nodes, NODES_LENGTH);

        nearestNode = getNearestNode(nodes, NODES_LENGTH);
        // Stop if all nodes are explored/visited
        if (nearestNode == NULL || nearestNode->distance == UINT_MAX) {
            printf("Stop: No nearest node\n");
            break;
        }
        printf("Nearest node: %s\n", nearestNode->name);
        for (unsigned int i = 0; i < EDGES_LENGTH; i++) {
            struct Node* a = getNodeByName(nodes, NODES_LENGTH, edges[i].a);
            struct Node* b = getNodeByName(nodes, NODES_LENGTH, edges[i].b);
            if (undirected) {
                if (a != nearestNode && b != nearestNode) continue;
                if (a == nearestNode && b->visited) continue;
                if (b == nearestNode && a->visited) continue;
            } else {
                if (a != nearestNode) continue;
                if (b->visited) continue;
            }
            printf("Check edge %s -|%u|-> %s\n", a->name, edges[i].weight, b->name);
            if (a == nearestNode && b->distance > (nearestNode->distance + edges[i].weight)) {
                printf("> Found shorter distance: %u > %u\n", b->distance, nearestNode->distance + edges[i].weight);
                b->distance = nearestNode->distance + edges[i].weight;
                b->nearestNode = nearestNode;
            }

            if (undirected && b == nearestNode && a->distance > (nearestNode->distance + edges[i].weight)) {
                printf("> Found shorter distance: %u > %u\n", a->distance, nearestNode->distance + edges[i].weight);
                a->distance = nearestNode->distance + edges[i].weight;
                a->nearestNode = nearestNode;
            }
            continue;
        }
        // Mark node as explored/visited
        nearestNode->visited = true;
    }
    printNodes(nodes, NODES_LENGTH);
}

int main() {

    // DIJKSTRA ALGORITHM
    // > get the shortest distance of all nodes to a node
    // Requires:
    // - only positive edges
    // 1. Initalize
    //    > set root node distance to 0
    //    > set other nodes distances to 'Infinity'
    //    > mark all nodes as not visited
    // 2. Repeat:
    //    2.1 select node with the shortest distance that was not yet visited
    //    2.2 mark it as visited and update the shortest distances to all direct connected nodes

    // 1) Setup nodes and edges
    const unsigned int NODES_LENGTH = 6;
    struct Node nodes[] = {
        {"x0", 0,        false, NULL},
        {"x1", UINT_MAX, false, NULL},
        {"x2", UINT_MAX, false, NULL},
        {"x3", UINT_MAX, false, NULL},
        {"x4", UINT_MAX, false, NULL},
        {"x5", UINT_MAX, false, NULL},
    };
    const unsigned int EDGES_LENGTH = 8;
    struct Edge edges[] = {
        {"x0", "x1", 1},
        {"x0", "x5", 7},
        {"x1", "x2", 3},
        {"x2", "x3", 4},
        {"x2", "x4", 6},
        {"x2", "x5", 2},
        {"x3", "x4", 3},
        {"x4", "x5", 1},
    };
    // 2)
    dijkstra(nodes, NODES_LENGTH, edges, EDGES_LENGTH, true);

    printf("------------------------------------------------\n");
    {
        const unsigned int NODES_LENGTH = 9;
        struct Node nodes[] = {
            {"x1", 0,        false, NULL},
            {"x2", UINT_MAX, false, NULL},
            {"x3", UINT_MAX, false, NULL},
            {"x4", UINT_MAX, false, NULL},
            {"x5", UINT_MAX, false, NULL},
            {"x6", UINT_MAX, false, NULL},
            {"x7", UINT_MAX, false, NULL},
            {"x8", UINT_MAX, false, NULL},
            {"x9", UINT_MAX, false, NULL},
        };
        const unsigned int EDGES_LENGTH = 17;
        struct Edge edges[] = {
            {"x1", "x2", 2},
            {"x1", "x7", 6},
            {"x1", "x8", 5},

            {"x2", "x3", 3},
            {"x2", "x8", 2},
            {"x2", "x9", 5},

            {"x3", "x4", 4},
            {"x3", "x9", 7},

            {"x4", "x5", 5},
            {"x4", "x6", 1},
            {"x4", "x9", 2},

            {"x5", "x6", 3},
            {"x5", "x7", 7},

            {"x6", "x7", 4},
            {"x6", "x9", 4},

            {"x7", "x8", 3},

            {"x8", "x9", 2},
        };
        // 2)
        dijkstra(nodes, NODES_LENGTH, edges, EDGES_LENGTH, true);
    }

    printf("------------------------------------------------\n");
    {
        // A --4-- B
        // |      / \
        // 2     1   5
        // |    /     \
        // C --8-------D
        const unsigned int NODES_LEN = 4;
        struct Node nodes[] = {
            {"A", 0,        false, NULL},
            {"B", UINT_MAX, false, NULL},
            {"C", UINT_MAX, false, NULL},
            {"D", UINT_MAX, false, NULL},
        };
        const unsigned int EDGES_LEN = 6;
        struct Edge edges[] = {
            {"A","B",4},
            {"A","C",2},
            {"B","C",1},
            {"B","D",5},
            {"C","D",8},
            {"C","D",10}, // duplicate edge (just for testing)
        };
        dijkstra(nodes, NODES_LEN, edges, EDGES_LEN, true);
        assert(nodes[0].distance == 0); // A = 0
        assert(nodes[1].distance == 3); // B = 3
        assert(nodes[2].distance == 2); // C = 2
        assert(nodes[3].distance == 8); // D = 8
    }
    
    printf("------------------------------------------------\n");
    {
        // A -1-+ B
        // |     /|
        // |    2 |
        // 4   /  5
        // |  /   |
        // + +    +
        // C -1-+ D
        const unsigned int NODES_LEN = 4;
        struct Node nodes[] = {
            {"A", 0,        false, NULL},
            {"B", UINT_MAX, false, NULL},
            {"C", UINT_MAX, false, NULL},
            {"D", UINT_MAX, false, NULL},
        };
        const unsigned int EDGES_LEN = 5;
        struct Edge edges[] = {
            {"A","B",1},
            {"A","C",4},
            {"B","C",2},
            {"B","D",5},
            {"C","D",1},
        };
        dijkstra(nodes, NODES_LEN, edges, EDGES_LEN, false);
        assert(nodes[0].distance == 0); // A = 0
        assert(nodes[1].distance == 1); // B = 1
        assert(nodes[2].distance == 3); // C = 3
        assert(nodes[3].distance == 4); // D = 4
    }
    
    printf("------------------------------------------------\n");
    {
        // A -1-> B
        // |      ^
        // |      |
        // |      1
        // |      |
        // +----> C
        const unsigned int NODES_LEN = 3;
        struct Node nodes[] = {
            {"A", 0,        false, NULL},
            {"B", UINT_MAX, false, NULL},
            {"C", UINT_MAX, false, NULL},
        };
        const unsigned int EDGES_LEN = 3;
        struct Edge edges[] = {
            {"A","B",1},
            {"C","B",1},
            {"A","C",10},
        };
        dijkstra(nodes, NODES_LEN, edges, EDGES_LEN, false);
        assert(nodes[0].distance == 0);  // A = 0
        assert(nodes[1].distance == 1);  // B = 1
        assert(nodes[2].distance == 10); // C = 10
    }
    
    printf("------------------------------------------------\n");
    {
        // A --0-- B --0-- C
        // |               |
        // +--------5------+
        const unsigned int NODES_LEN = 3;
        struct Node nodes[] = {
            {"A", 0,        false, NULL},
            {"B", UINT_MAX, false, NULL},
            {"C", UINT_MAX, false, NULL},
        };
        const unsigned int EDGES_LEN = 3;
        struct Edge edges[] = {
            {"A","B",0},
            {"B","C",0},
            {"A","C",5},
        };
        dijkstra(nodes, NODES_LEN, edges, EDGES_LEN, true);
        assert(nodes[0].distance == 0); // A = 0
        assert(nodes[1].distance == 0); // B = 0
        assert(nodes[2].distance == 0); // C = 0
    }
}

Makefile

CC = gcc
CFLAGS = -Wall -Wextra -O2

TARGET = dikstra
SRCS = main.c
OBJS = $(SRCS:.c=.o)

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) -o $@ $^

%.o: %.c
	$(CC) $(CFLAGS) -c $<

clean:
	rm -f $(OBJS) $(TARGET)

.PHONY: all clean