Dijkstra’s Algorithm to find the shortest path using PHP & SQL

This code includes all the following functionalities you need to create a single page for find the route:

• It connects to the MySQL database and retrieves node and edge data.
• It calculates the shortest path between a specified start and end node using Dijkstra’s algorithm.
• It prints the shortest distance and the nodes in the shortest path.

Yo need to replace ‘your_host’, ‘your_username’, ‘your_password’, ‘your_database’, ‘Start Node’, and ‘End Node’ with your actual database and node names.

<?php

// Database connection details
$host = 'your_host';
$username = 'your_username';
$password = 'your_password';
$database = 'your_database';

// Create a database connection
$conn = new mysqli($host, $username, $password, $database);

// Check the connection
if ($conn->connect_error) {
    die("Connection failed: " . $conn->connect_error);
}

// Define the graph array
$graph = array();

// Fetch nodes from the 'nodes' table
$nodesQuery = "SELECT * FROM nodes";
$nodesResult = $conn->query($nodesQuery);

if (!$nodesResult) {
    die("Node query failed: " . $conn->error);
}

while ($row = $nodesResult->fetch_assoc()) {
    $node_id = $row['node_id'];
    $node_name = $row['node_name'];

    // Initialize the node in the graph array
    $graph[$node_name] = array();
}

// Fetch edges from the 'edges' table
$edgesQuery = "SELECT * FROM edges";
$edgesResult = $conn->query($edgesQuery);

if (!$edgesResult) {
    die("Edge query failed: " . $conn->error);
}

while ($row1 = $edgesResult->fetch_assoc()) {
    $from_node = $row1['from_node'];
    $to_node = $row1['to_node'];
    $distance = $row1['distance'];

    // Add the edge to the graph array
    $graph[$from_node][$to_node] = $distance;
}

// Close the database connection
$conn->close();

function dijkstra($graph, $startNode, $endNode) {
    $infinity = PHP_INT_MAX;
    $distances = array();
    $unvisitedNodes = $graph;
    $path = array();

    foreach ($unvisitedNodes as $node => $value) {
        $distances[$node] = $infinity;
    }

    $distances[$startNode] = 0;

    while (count($unvisitedNodes) > 0) {
        $minNode = null;

        foreach ($unvisitedNodes as $node => $value) {
            if ($minNode === null || $distances[$node] < $distances[$minNode]) {
                $minNode = $node;
            }
        }

        foreach ($graph[$minNode] as $neighbor => $value) {
            $alt = $distances[$minNode] + $graph[$minNode][$neighbor];
            if ($alt < $distances[$neighbor]) {
                $distances[$neighbor] = $alt;
                $path[$neighbor] = $minNode;
            }
        }

        unset($unvisitedNodes[$minNode]);
    }

    // Trace the path from startNode to endNode
    $shortestPath = array();
    $currentNode = $endNode;

    while (isset($path[$currentNode])) {
        array_unshift($shortestPath, $currentNode);
        $currentNode = $path[$currentNode];
    }

    array_unshift($shortestPath, $startNode);

    return array(
        'distances' => $distances,
        'path' => $path,
        'shortest_path' => $shortestPath,
    );
}

// Define the start and end nodes
$startNode = 'Start Node'; // Replace with the actual start node name
$endNode = 'End Node';     // Replace with the actual end node name

// Calculate the shortest path
$result = dijkstra($graph, $startNode, $endNode);

// Print the shortest path
echo "Shortest distance from $startNode to $endNode: " . $result['distances'][$endNode] . "<br>";
echo "Shortest path: " . implode(" -> ", $result['shortest_path']);

?>