Advanced Graph Algorithms: Implementing Dijkstra's Algorithm in PHP | CodeSignal Learn

Advanced Graph Algorithms: Implementing Dijkstra's Algorithm in PHP | CodeSignal Learn

One of the exciting algorithms we'll be examining is Dijkstra’s Algorithm. It is a cornerstone for finding the shortest path in a graph with non-negative weights. The algorithm centers on a priority queue represented as a binary heap, which ensures that at any given point, the unvisited node with the lowest distance is chosen. The algorithm keeps track of the shortest distance from the start node to all other nodes in the graph, progressively updating the shortest distance for only the unvisited nodes. In PHP, we utilize SplPriorityQueue to implement this efficiently.

Here is the implementation of the algorithm:

PHP

class Node {
    public $id;
    public $distance;

    public function __construct($id, $distance) {
        $this->id = $id;
        $this->distance = $distance;
    }
}

class Dijkstra {
    public static function dijkstra($graph, $start) {
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        $minHeap->insert(new Node($start, 0), 0);
        $dist = [$start => 0];

        while (!$minHeap->isEmpty()) {
            $current = $minHeap->extract();
            $currentNode = $current['data'];
            $current_dist = $currentNode->distance;

            if ($current_dist > ($dist[$currentNode->id] ?? PHP_INT_MAX)) {
                continue;
            }

            foreach ($graph[$currentNode->id] ?? [] as $neighbor => $weight) {
                $distance = $current_dist + $weight;
                if ($distance < ($dist[$neighbor] ?? PHP_INT_MAX)) {
                    $dist[$neighbor] = $distance;
                    $minHeap->insert(new Node($neighbor, $distance), -$distance);
                }
            }
        }

        return $dist;
    }
}

// Example usage
$graph = [
    "A" => ["B" => 1, "C" => 4],
    "B" => ["A" => 1, "C" => 2, "D" => 5],
    "C" => ["A" => 4, "B" => 2, "D" => 1],
    "D" => ["B" => 5, "C" => 1],
];

print_r(Dijkstra::dijkstra($graph, "A")); // Output: Array ( [A] => 0 [B] => 1 [C] => 3 [D] => 4 )

The implementation leverages Dijkstra's algorithm to find the shortest path from a starting node to all other nodes in a weighted graph with non-negative weights. The SplPriorityQueue is used to maintain a priority queue of nodes, prioritizing those with the shortest estimated distance. The algorithm iteratively extracts the node with the lowest distance from the queue, updates the shortest distance for its neighboring nodes if a shorter path is found through the current node, and inserts the updated nodes back into the priority queue with their new priorities. This process continues until all reachable nodes have been visited, resulting in an array of the shortest distances from the start node to each node in the graph.