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:
- 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
- If the distance to the current vertex + the distance to the neighbour < that the stored distance to the neighbour:
- Remove the current vertex from the unvisited list
- Find the nearest unvisited vertex (i.e., the one with the lowest distance in the distances table)
- Make it the new current vertex
- For each neighbour of the 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