Finding the shortest path in a weighted graph with 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 finding a similar path like Dijkstra’s algorithm.

My implementation allows you 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 data center 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 than 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.

• 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 an O(1) operation. In our case, it is ok since we know that all vertexes have a priority of self::$infinite.

• After the initialization, 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 its adjacent vertexes which are still in our priority queue.

• The variable $alt holds the length of the path from the $origin vertex to the neighbor 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 to BFS:

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

That is it for today.

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