Dijkstra’s Shortest Paths algorithm in C

Dijksta’s algorithm finds the shortest path in a weighted graph from a single vertex to one or all other vertices. It is a greedy breadth-first search (BFS) algorithm which works as follows:

Create a table of distances to all vertices
Set the distance to 0 for the starting vertex, and infinity for the others
Make a list of unvisited vertices, which starts off containing all vertices
Set the current vertex to be the starting vertex
While the unvisited list is not empty:
1. For each neighbour of the current vertex:
  - If the distance to the current vertex + the distance to the neighbour < that the stored distance to the neighbour:
    - Update the stored distance to the neighbour to be the distance to the current vertex + the distance to the neighbour
2. Remove the current vertex from the unvisited list
3. Find the nearest unvisited vertex (i.e., the one with the lowest distance in the distances table)
4. Make it the new current vertex

Below is an implemention in C. The function dijkstra(), takes an array of edges, the number of edges (size) and the number of vertices (order), and returns an array containing the distance to each vertex. For the unvisited list I used an array of integers which I set to 0 or 1 depending on whether the corresponding vertex was unvisited or visited respectively.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
    unsigned int weight;
} weighted_edge;

unsigned int *dijkstra(const weighted_edge *edges, unsigned int size, unsigned int order,
        unsigned int vertex)
{
    unsigned int i;
    unsigned int *distances = malloc(order * sizeof(unsigned int));
    unsigned int *unvisited = malloc(order * sizeof(unsigned int));
    unsigned int unvisited_count = order;
    unsigned int current = vertex;
    if (distances == NULL || unvisited == NULL) {
        free(distances);
        free(unvisited);
        return NULL;
    }
    /* All distances start infinite and all vertices start unvisited */
    for (i = 0; i < order; i++) {
        distances[i] = UINT_MAX;
        unvisited[i] = 1;
    }
    /* Distance to starting vertex is 0 */
    distances[vertex] = 0;
    while (unvisited_count > 0) {
        /* Update the distances to all neighbours */
        unsigned int e, v;
        unsigned int min_distance;
        for (e = 0; e < size; e++) {
            if (edges[e].first == current || edges[e].second == current) {
                const unsigned int neighbour = edges[e].first == current ?
                    edges[e].second : edges[e].first;
                const unsigned int distance = distances[current] + edges[e].weight;
                if (distance < distances[neighbour]) {
                    distances[neighbour] = distance;
                }
            }
        }
        /* Finished with this vertex */
        unvisited[current] = 0;
        unvisited_count--;
        /* Find the nearest unvisited vertex */
        min_distance = 0;
        for (v = 0; v < order; v++) {
            if (unvisited[v] == 1 && (min_distance == 0 || distances[v] < min_distance)) {
                min_distance = distances[v];
                current = v;
            }
        }
    }
    free(unvisited);
    return distances;
}

Here is an example program that finds all of the distances from vertex 0 in the graph pictured above:

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

int main(void)
{
    const unsigned int size = 9; /* Edges */
    const unsigned int order = 6; /* Vertices */
    weighted_edge *edges = malloc(size * sizeof(weighted_edge));
    unsigned int *distances;
    unsigned int i = 0;

    weighted_edge_connect(edges, 0, 1, 2, &i);
    weighted_edge_connect(edges, 0, 2, 4, &i);
    weighted_edge_connect(edges, 1, 2, 1, &i);
    weighted_edge_connect(edges, 1, 3, 4, &i);
    weighted_edge_connect(edges, 1, 4, 2, &i);
    weighted_edge_connect(edges, 2, 4, 3, &i);
    weighted_edge_connect(edges, 3, 4, 3, &i);
    weighted_edge_connect(edges, 3, 5, 2, &i);
    weighted_edge_connect(edges, 4, 5, 2, &i);

    distances = dijkstra(edges, size, order, 0);

    for (i = 0; i < order; i++) {
        printf("%u: %u\n", i, distances[i]);
    }

    free(distances);
    free(edges);

    return 0;
}

The output:

0: 0
1: 2
2: 3
3: 6
4: 4
5: 6

Martin Broadhurst

Dijkstra’s Shortest Paths algorithm in C

Related