Finding the shortest path in a weighted graph with PHP

A simple implementation of Dijkstra’s algorithm in PHP

In my last article I shared my code for searching a path in a graph using breath first search.

BFS works well if the graph is not weighted. By the way if the weight is 1 (or any other constant) for each edge then BFS is basically finding the same path like Dijkstra’s algorithm.

My implementation allows to select a method that calculates the edge weight so anybody can check the above statement … :-)

What if our graph has weights for each edge that needs to be taken into consideration?

Let’s just imagine the road network with the cities as vertexes and the roads as edges.

If we have to find the shortest path between two cities then obviously the weight of the edge (e.g. the distance between the cities) does matter.

In my use-case (a datacenter with network devices and cables connecting them) a weight can be also specified. Just think about the OSPF protocol that is also using Dijkstra’s algorithm.

I have selected a minimum priority queue based approach since it is somewhat quicker that a regular set based solution. I will compare the performance of these algorithms in my next article.

Unfortunately, neither PHP nor the Ds\PriorityQueue or SplPriorityQueue packages come equipped with a minimum priority queue data structure that meets the stated requirements (as outlined below).

So I wrote my own PriorityQueue class that implements the 3 methods needed:

• add_with_priority(): adds an item (in our case a vertex) to the priority queue with a priority,

• decrease_priority(): decrease the priority of an item,

• extract_min(): returns the item with the smallest priority from the queue.

My solution is array based but I do not need anything fancier than that.

The code is pretty straightforward:

public function dijkstraWithPriorityQueue(int $origin, int $destination) {

    $this->origin = $origin;
    $this->destination = $destination;

    $dist = [];
    $dist[$origin] = 0;

    $q = new MyPriorityQueue();

    foreach(array_keys($this->graph) as $vertex) {
        if ($vertex !== $origin) {
            $dist[$vertex] = self::$infinite;
            $this->setParent($vertex, null);
            $q->append($vertex, self::$infinite);
        }
    }

    $q->add_with_priority($origin, 0);

    while($q->count()) {
        $u = $q->extract_min();
        if ($u === $destination || $u === 0)
            break; // if we found our destination or there is no such route ...
        foreach($this->getAdjacentEdgesInSet($u, $q) as $v) {
            $alt = $dist[$u] + $this->graphEdges($u, $v, $this->getDistance(...));
            if ($alt < $dist[$v]) {
                $dist[$v] = $alt;
                $this->setParent($v, $u);
                $q->decrease_priority($v, $alt);
            }
        }
    }

    $this->setRoute($this->extractRoute());

    return $this;

}

Let us go through the code line-by-line:

• We set our origin and destination vertexes.

• Then we initiate a destination matrix holding the current distance between the given node and our origin vertex ($origin).

• We create a new instance of my priority queue implementation and set the distance and the parent node for each vertex and append them to the queue. The append() method simply adds the vertexes to the end of the queue without checking their priority, so it is basically an O(1) operation. In our case it is absolutely ok since we know that all vertexes have a priority of self::$infinite.

• After the initialisation we add our origin vertex to the priority queue with the smallest priority.

• Then we cycle through our queue extracting the smallest priority item with extract_min().

• If we found one and it is not our destination vertex then we check it’s adjacent vertexes which are still in our priority queue.

• The variable $alt holds the length of the path from the $origin vertex to the neighbour vertex $v if it were to go through $u. If this path is shorter than the current shortest path recorded for $v, that current path is replaced with this $alt path, the parent for $v is set to the current vertex $u and the priority of $v is decreased to $alt in our priority queue. These steps are the most important parts of Dijkstra’s algorithm.

• At the end of the method we extract and set the route if any was found.

An interesting part of the code is the way we calculate the weigth of an edge between vertexes $u and $v.

For this we call:

$this->graphEdges($u, $v, $this->getDistance(...));

The graphEdges method takes the vertexes and a callable. The callable is then used to calculate the weight.

private function getDistance(int $u, int $v): int {
    return $this->graph[$u][$v] ?? self::$infinite;
}

With this approach we can easily swap-in a new method to calculate the actual weight and use for example the below one to turn our Dijkstra method into something that resembles a close variant to BFS:

private static function alwaysReturnOne(int $u, int $v): int {
    return 1;
}

That's all folks. I hope you enjoyed this article.

In my next post I will compare the execution time of my BFS, simple queue based Dijkstra and the priority queue based Dijkstra algorithms.