Minor performance bug found in Dijkstra.php

[mart-molle]

trafficstars

I found a minor performance bug in Dijkstra.php which can increase execution time but DOES NOT affect correctness. The issue occurs in the loop on lines 126-128:

while (!empty($this->queue)) { $this->processNextNodeInQueue($exclude); }

Since the only loop exit condition is an empty work queue, the code keeps running until it has found the shortest path from $source to EVERY node in the entire graph. If $source and $target are close together in a large graph, this can take a lot of extra time, long after the shortest path to $target has already be found.

I know that the code is trying to fine ALL shortest paths from $source to $target, and not just one of them. However, even in this case we can still use an early exit from this loop.

Recall that in Dijkstra's algorithm nodes are pulled from the work queue in order of increasing distance from $source, and once a node is pulled from the queue for processing, we know its final distance from $source.

Thus, we only need to remain in the loop as long as (distance[$closest] <= distance[$target])

Unfortunately, node $closest from the work queue is not identified until line 58 INSIDE the function processNextNodeInQueue. Modifying this program structure leads to further changes to the above loop, like this:

$closest = $source;	// initialize before first iteration
    while ((!empty($this->queue)) and (distance[$closest] <= distance[$target]){ // BUG FIX
        $this->processNextNodeInQueue($closest, $exclude);
    $closest = array_search(min($this->queue), $this->queue); // MOVED FROM INSIDE FUNCTION
    }

To balance these changes we must pass $closest the function processNextNodeInQueue as a parameter, i.e., OLD CODE:

protected function processNextNodeInQueue(array $exclude)
{
    // Process the closest vertex
    $closest = array_search(min($this->queue), $this->queue);

NEW CODE: protected function processNextNodeInQueue($closest, array $exclude) { // Process the closest vertex /* $closest = array_search(min($this->queue), $this->queue); <<< REMOVE FROM FUNCTION */

The fix should be very simple but I am NOT familiar with PHP programming and I have not been able to test it. Below is the output of DIFF command showing all my changes. Sorry I can't seem to attach a program to this message. Regards, Mart Molle.

diff Dijkstra.php Tweak_Dijkstra.php 50a51

 * @param string $closest Node in the queue with MIN distance from $source

55c56 < protected function processNextNodeInQueue(array $exclude)

protected function processNextNodeInQueue($closest, array $exclude)

58c59 < $closest = array_search(min($this->queue), $this->queue);

/* $closest = array_search(min($this->queue), $this->queue); <<< REMOVE FROM FUNCTION */ 126,127c127,130 < while (!empty($this->queue)) { < $this->processNextNodeInQueue($exclude);

---

$closest = $source; // initialize before first iteration while ((!empty($this->queue)) and (distance[$closest] <= distance[$target]){ // BUG FIX $this->processNextNodeInQueue($closest, $exclude); $closest = array_search(min($this->queue), $this->queue); // MOVED FROM INSIDE FUNCTION