Dijkstra's Algorithm

Edsger W. Dijkstra was a Dutch computer scientist who made significant contributions to computer science. He is best known for developing Dijkstra's algorithm, which solves the least-cost path problem in a directed or undirected graph with non-negative edges.

But before talking about Dijkstra's algorithm, let's talk about the Breadth-First Search algorithm.

Breadth-First Search

Working with graphs is a common task in computing. One of the most common problems is finding the shortest path between two vertices in a graph. The Breadth-First Search algorithm shows how to find the shortest path in a graph, for example the shortest route between two cities on a map where cities are vertices and roads are edges.

Imagine we need to go from A to G. The Breadth-First Search algorithm helps us find the shortest path. It starts by visiting the source vertex (A) and then explores all neighboring vertices. After that, it explores the vertices two steps away, and so on.

In our case, the shortest path is A -> B -> E -> G.

Here, it takes only 3 steps to reach G.

Dijkstra's Algorithm

But what if the edges have weights? Breadth-First Search no longer works. Dijkstra's algorithm finds the cheapest path in a directed or undirected graph whose edges have weights. It keeps two lists: one of visited vertices and one of unvisited vertices. It selects the unvisited vertex closest to the source, marks it as visited and updates the weights of its neighbors.

Let's adapt the previous example to include weights on the edges.

Now each edge has a weight, and our challenge is to find the path with the lowest total weight.

Let's apply Dijkstra's algorithm to find the cheapest path from A to G.

1. We start at A and look at its neighbors: reaching B costs 10 and reaching C costs 5.

   Vertex	Distance from A	Path
   A	0	A
   B	10	A → B
   C	5	A → C

2. The unvisited vertex closest to A is C (5). We visit C and update its neighbors: D now costs 7 (5 + 2) and F now costs 9 (5 + 4).

   Vertex	Distance from A	Path
   A	0	A
   B	10	A → B
   C	5	A → C
   D	7	A → C → D
   F	9	A → C → F

3. The next closest is D (7). Through D, E costs 8 (7 + 1). F would cost 13 (7 + 6), which is worse than 9, so F stays the same.

   Vertex	Distance from A	Path
   A	0	A
   B	10	A → B
   C	5	A → C
   D	7	A → C → D
   F	9	A → C → F
   E	8	A → C → D → E

4. Next is E (8). Through E, G costs 10 (8 + 2). Visiting F and B afterwards does not improve any distance, so the algorithm stops.

   Vertex	Distance from A	Path
   A	0	A
   B	10	A → B
   C	5	A → C
   D	7	A → C → D
   F	9	A → C → F
   E	8	A → C → D → E
   G	10	A → C → D → E → G

The cheapest path from A to G is A -> C -> D -> E -> G, with a total cost of 10.

Applying it with PHP

Let's build a hands-on example in PHP to apply Dijkstra's algorithm.

$graph = [
    'A' => ['B' => 10, 'C' => 5],
    'B' => ['E' => 8, 'D' => 3],
    'C' => ['D' => 2, 'F' => 4],
    'D' => ['E' => 1, 'F' => 6],
    'E' => ['G' => 2],
    'F' => ['E' => 1],
    'G' => []
];

function dijkstra(array $graph, string $source, string $target): array
{
    $dist = array_fill_keys(array_keys($graph), INF);
    $prev = array_fill_keys(array_keys($graph), null);
    $dist[$source] = 0;

    // SplPriorityQueue returns the highest priority first,
    // so we use the negative distance to get the closest vertex.
    $queue = new SplPriorityQueue();
    $queue->insert($source, 0);

    while (!$queue->isEmpty()) {
        $u = $queue->extract();

        foreach ($graph[$u] as $v => $cost) {
            $alt = $dist[$u] + $cost;
            if ($alt < $dist[$v]) {
                $dist[$v] = $alt;
                $prev[$v] = $u;
                $queue->insert($v, -$alt);
            }
        }
    }

    $path = [];
    for ($u = $target; $u !== null; $u = $prev[$u]) {
        array_unshift($path, $u);
    }

    return $path;
}

$path = dijkstra($graph, 'A', 'G');
echo implode(' -> ', $path); // A -> C -> D -> E -> G

Here is the algorithm, step by step:

1. We initialize the distances and the priority queue.
2. We set the distance of the source vertex to 0.
3. While the priority queue is not empty, we extract the vertex with the smallest distance.
4. For each neighboring vertex, we compute the alternative distance and update it if it is smaller.
5. We build the path by walking back through the previous vertices.
6. We return the path.

Conclusion

With the growing use of AI, Machine Learning and Big Data, graphs have become more and more important. Dijkstra's algorithm is one of the most important algorithms for finding the shortest path in a graph. I hope you now understand how it works and how it can be applied to a real-world scenario. If you liked this article, leave a comment and share it with your friends. See you next time!