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 ]; } function calculateMemoryUsage(int $numNodes, int $numEdges): array { $memoryUsageNxN = ($numNodes * $numNodes) * 4; $memoryUsage5xN = (5 * $numEdges) * 4; return [ 'D' => $memoryUsageNxN/1024, '5N' => $memoryUsage5xN/1024, ]; } $numNodes = 20; $numEdges = 100; $source = '1'; $target = $numNodes; $graphData = generateRandomGraph($numNodes, $numEdges); $dijkstra = new Dijkstra(); $graph5xN = new Graph(); foreach ($graphData['nodes'] as $node) { $dijkstra->addNode($node); } foreach ($graphData['edges'] as $edge) { $dijkstra->addEdge($edge['node1'], $edge['node2'], $edge['weight']); } // foreach ($graphData['nodes'] as $node) { // $graph5xN->addNode($node); // } foreach ($graphData['edges'] as $edge) { $graph5xN->addEdge($edge['node1'], $edge['node2'], $edge['weight']); } $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); $memoryUsage = calculateMemoryUsage($numNodes, $numEdges); $memory5xn=$memoryUsage['5N']; $memoryD=$memoryUsage['D']; echo "Dijkstra: time: " . ($endDijkstra - $startDijkstra) . " sec, memory: " . ($memoryD) . " KB\n"; echo "5xN: time: " . ($end5xN - $start5xN) . " sec, memory: " . ($memory5xn) . " KB\n"; class Graph { private array $matrix = []; public function addEdge(int $from, int $to, int $weight): void { $this->matrix[] = [$from, $to, $weight, INF, 0, []]; } public function findShortestPath(int $start, int $end): array { // Инициализация матрицы foreach ($this->matrix as &$row) { if ($row[0] === $start) { $row[3] = $row[2]; // Установка начальной суммы пути $row[4] = 1; // Установка состояния в 1 (посещено) $row[5] = [$start]; // Установка начального пути } } $found = false; while (!$found) { $found = true; foreach ($this->matrix as &$row) { if ($row[4] === 1) { // Если текущее состояние равно 1 (посещено) foreach ($this->matrix as &$nextRow) { if ($nextRow[0] === $row[1]) { $newDistance = $row[3] + $nextRow[2]; // Вычисление нового расстояния if ($newDistance < $nextRow[3]) { $nextRow[3] = $newDistance; $nextRow[4] = 1; // Установка состояния в 1 (посещено) $nextRow[5] = array_merge($row[5], [$row[1]]); // Обновление пути } } } $row[4] = 2; // Установка состояния в 2 (обработано) } elseif ($row[4] === 0) { // Если текущее состояние равно 0 (не посещено) $found = false; } } } $shortestPathWeight = INF; $shortestPath = []; foreach ($this->matrix as $row) { if ($row[1] === $end && $row[3] < $shortestPathWeight) { $shortestPathWeight = $row[3]; $shortestPath = $row[5]; } } // Добавляем конечный узел к пути $shortestPath[] = $end; return [ 'path' => $shortestPath, 'totalWeight' => $shortestPathWeight, ]; } } 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], ]; } } ?>