Dijkstra's Algorithm in PHP

dijkstra.php

<?php
function dijkstra($graph, $start, $end) {
    // Set the distance from the start node to all other nodes to infinity
    $distances = array_fill(0, count($graph), INF);
    // Set the distance from the start node to itself to 0
    $distances[$start] = 0;
    // Set all nodes as unvisited
    $visited = array_fill(0, count($graph), false);
    // Set the previous node for each node to null
    $previous = array_fill(0, count($graph), null);

    // Loop through all the nodes
    while (array_search(false, $visited, true) !== false) {
        // Find the node with the shortest distance from the start node that hasn't been visited
        $current = null;
        $shortest_distance = INF;
        for ($i = 0; $i < count($graph); $i++) {
            if (!$visited[$i] && $distances[$i] < $shortest_distance) {
                $current = $i;
                $shortest_distance = $distances[$i];
            }
        }

        // Mark the current node as visited
        $visited[$current] = true;

        // Check all the neighboring nodes of the current node
        foreach ($graph[$current] as $neighbor => $weight) {
            // Calculate the distance to the neighbor through the current node
            $distance = $distances[$current] + $weight;
            // If the distance is shorter than the current distance to the neighbor, update the distance
            if ($distance < $distances[$neighbor]) {
                $distances[$neighbor] = $distance;
                $previous[$neighbor] = $current;
            }
        }
    }

    // Backtrack from the end node to the start node to find the shortest path
    $path = array();
    $current = $end;
    while ($current !== null) {
        array_unshift($path, $current);
        $current = $previous[$current];
    }

    // Return the shortest distance and the shortest path
    return array($distances[$end], $path);
}

// Define the graph
$graph = array(
    0 => array(1 => 4, 7 => 8),
    1 => array(0 => 4, 7 => 11, 2 => 8),
    2 => array(1 => 8, 3 => 7, 5 => 4, 8 => 2),
    3 => array(2 => 7, 4 => 9, 5 => 14),
    4 => array(3 => 9, 5 => 10),
    5 => array(2 => 4, 3 => 14, 4 => 10, 6 => 2),
    6 => array(5 => 2, 7 => 1, 8 => 6),
    7 => array(0 => 8, 1 => 11, 6 => 1, 8 => 7),
    8 => array(2 => 2, 6 => 6, 7 => 7),
);

// Call the dijkstra function with the graph, starting node, and ending node
list($distance, $path) = dijkstra($graph, 0, 4);

// Print the shortest distance and the shortest path
echo "Shortest distance: " . $distance . "\n";
echo "Shortest path: " . implode(" -> ", $path) . "\n";