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']);
?>