PHPize Online / SQLize Online  /  SQLtest Online

<? function generateRandomGraph($numNodes, $numEdges) { $nodes = []; $edges = []; for ($i = 1; $i <= $numNodes; $i++) { $nodes[] = (string)$i; } for ($i = 0; $i < $numEdges; $i++) { $node1 = $nodes[array_rand($nodes)]; $node2 = $nodes[array_rand($nodes)]; while ($node1 == $node2) { $node2 = $nodes[array_rand($nodes)]; } $edges[] = [ 'node1' => $node1, 'node2' => $node2, 'weight' => rand(1, 100) ]; } return [ 'nodes' => $nodes, 'edges' => $edges ]; } $numNodes = 5000; $numEdges = 100000; $source = '1'; $target = $numNodes; $graphData = generateRandomGraph($numNodes, $numEdges); $dijkstra = new Dijkstra(); $graph5xN = new Graph(); $startMemoryDijkstra = memory_get_usage(); foreach ($graphData['nodes'] as $node) { $dijkstra->addNode($node); } foreach ($graphData['edges'] as $edge) { $dijkstra->addEdge($edge['node1'], $edge['node2'], $edge['weight']); } $endMemoryDijkstra = memory_get_usage(); $usedMemoryDijkstra = $endMemoryDijkstra - $startMemoryDijkstra; $startMemory5xN = memory_get_usage(); foreach ($graphData['nodes'] as $node) { $graph5xN->addNode($node); } foreach ($graphData['edges'] as $edge) { $graph5xN->addEdge($edge['node1'], $edge['node2'], $edge['weight']); } $endMemory5xN = memory_get_usage(); $usedMemory5xN = $endMemory5xN - $startMemory5xN; $startDijkstra = microtime(true); $resultDijkstra = $dijkstra->findShortestPath($source, $target); //print_r($resultDijkstra); $endDijkstra = microtime(true); $start5xN = microtime(true); $result5xN = $graph5xN->findShortestPath($source, $target); //print_r($result5xN); $end5xN = microtime(true); echo "Dijkstra: time: " . ($endDijkstra - $startDijkstra) . " sec, memory: " . ($usedMemoryDijkstra) . " bytes\n"; echo "5xN: time: " . ($end5xN - $start5xN) . " sec, memory: " . ($usedMemory5xN) . " bytes\n"; class Graph { private array $nodes = []; // Array to store the nodes and their connections (edges) // Adds a node to the graph public function addNode(string $node): void { if (!isset($this->nodes[$node])) { $this->nodes[$node] = []; } } // Adds an edge between two nodes with a specified weight public function addEdge(string $from, string $to, int $weight): void { $this->nodes[$from][$to] = $weight; $this->nodes[$to][$from] = $weight; } // Finds the shortest path between the start and end nodes public function findShortestPath(string $start, string $end): array { $distances = []; // Array to store the current shortest distance to each node $previousNodes = []; // Array to store the previous node in the path for each node $nodes = array_keys($this->nodes); // Get the list of node keys // Initialize the arrays with default values foreach ($nodes as $node) { $previousNodes[$node] = null; $distances[$node] = INF; } $distances[$start] = 0; // Set the initial distance for the start node to 0 $queue = new \SplPriorityQueue(); // Create a new priority queue $queue->insert($start, 0); // Insert the start node into the priority queue with a priority of 0 // Main loop to process each node while (!$queue->isEmpty()) { $currentNode = $queue->extract(); // Get the node with the highest priority (lowest distance) if ($currentNode === $end) { // If we've reached the end node, break the loop break; } $neighbors = $this->nodes[$currentNode]; // Get the neighbors of the current node $currentDistance = $distances[$currentNode]; // Get the current shortest distance for the current node // Process the neighbors of the current node foreach ($neighbors as $neighbor => $weight) { $newDistance = $currentDistance + $weight; // Calculate the new distance for the neighbor node // Update the distance to the neighbor if a shorter path is found if ($newDistance < $distances[$neighbor]) { $distances[$neighbor] = $newDistance; $previousNodes[$neighbor] = $currentNode; $queue->insert($neighbor, -$newDistance); // Insert the neighbor into the priority queue with a negative priority (lower distance means higher priority) } } } // Reconstruct the shortest path from the previous nodes array $path = []; $currentNode = $end; while ($currentNode !== null) { $path[] = $currentNode; $currentNode = $previousNodes[$currentNode]; } // Reverse the path and return it along with the total weight $path = array_reverse($path); return [ 'path' => $path, 'totalWeight' => $distances[$end], ]; } } class Dijkstra { private array $nodes = []; // An array to store nodes and their connections (edges) // Adds a node to the graph public function addNode(string $node): void { if (!isset($this->nodes[$node])) { $this->nodes[$node] = []; // Initialize the array for the node's connections } } // Adds an edge between two nodes with a specified weight public function addEdge(string $from, string $to, int $weight): void { $this->nodes[$from][$to] = $weight; // Add the edge from the 'from' node to the 'to' node $this->nodes[$to][$from] = $weight; // Add the edge from the 'to' node to the 'from' node } // Finds the shortest path between the start and end nodes public function findShortestPath(string $start, string $end): array { $distances = []; // An array to store the current shortest distance to each node $previousNodes = []; // An array to store the previous node in the path for each node $nodes = array_keys($this->nodes); // Get an array of all node names // Initialize the arrays with default values foreach ($nodes as $node) { $previousNodes[$node] = null; // Set the previous node for each node to null $distances[$node] = INF; // Set the initial distance for each node to infinity } $distances[$start] = 0; // Set the initial distance for the start node to 0 $queue = new \SplPriorityQueue(); // Create a new priority queue $queue->insert($start, 0); // Insert the start node into the priority queue with a priority of 0 // Main loop to process each node while (!$queue->isEmpty()) { $currentNode = $queue->extract(); // Get the node with the highest priority (lowest distance) if ($currentNode === $end) { // If the current node is the end node, break the loop break; } $neighbors = $this->nodes[$currentNode]; // Get the neighbors of the current node $currentDistance = $distances[$currentNode]; // Get the current distance to the current node // Process the neighbors of the current node foreach ($neighbors as $neighbor => $weight) { $newDistance = $currentDistance + $weight; // Calculate the new distance to the neighbor // Update the distance to the neighbor if a shorter path is found if ($newDistance < $distances[$neighbor]) { $distances[$neighbor] = $newDistance; // Update the distance $previousNodes[$neighbor] = $currentNode; // Set the previous node for the neighbor $queue->insert($neighbor, -$newDistance); // Insert the neighbor with the updated distance } } } // Reconstruct the shortest path from the previous nodes array $path = []; $currentNode = $end; while ($currentNode !== null) { $path[] = $currentNode; // Add the current node to the path $currentNode = $previousNodes[$currentNode]; // Move to the previous node in the path } $path = array_reverse($path);// Reverse the path to get the correct order // Return the shortest path along with the total weight return [ 'path' => $path, 'totalWeight' => $distances[$end], ]; } } ?>