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 = 10000; $numEdges = 100000; $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']); } $endMemoryDijkstra = memory_get_usage(); $usedMemoryDijkstra = $endMemoryDijkstra - $startMemoryDijkstra; $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); $startMemory5xN = memory_get_usage(); $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) private array $matrix = []; // Array to store the matrix representation of the graph // 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 { $visited = []; // Array to store the visited status of each node $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); // Initialize the arrays with default values foreach ($nodes as $node) { $visited[$node] = false; $previousNodes[$node] = null; $distances[$node] = INF; } $distances[$start] = 0; $currentNode = $start; // Main loop to process each node while ($currentNode !== null) { $neighbors = $this->nodes[$currentNode]; $currentDistance = $distances[$currentNode]; // Process the neighbors of the current node foreach ($neighbors as $neighbor => $weight) { $newDistance = $currentDistance + $weight; // Update the distance to the neighbor if a shorter path is found if ($newDistance < $distances[$neighbor]) { $distances[$neighbor] = $newDistance; $previousNodes[$neighbor] = $currentNode; } } // Mark the current node as visited $visited[$currentNode] = true; // Find the next unvisited node with the shortest distance $currentNode = null; $minDistance = INF; foreach ($nodes as $node) { if (!$visited[$node] && $distances[$node] < $minDistance) { $currentNode = $node; $minDistance = $distances[$node]; } } } // 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 $nodes; private $edges; public function __construct() { $this->nodes = []; $this->edges = []; } /** * Добавляет узел в граф. * * @param string $node */ public function addNode($node) { $this->nodes[$node] = true; } /** * Добавляет ребро между двумя узлами с заданным весом. * * @param string $node1 * @param string $node2 * @param float $weight */ public function addEdge($node1, $node2, $weight) { if (!isset($this->edges[$node1])) { $this->edges[$node1] = []; } if (!isset($this->edges[$node2])) { $this->edges[$node2] = []; } $this->edges[$node1][$node2] = $weight; $this->edges[$node2][$node1] = $weight; } /** * Находит кратчайший путь между двумя узлами с помощью оптимизированного алгоритма Дейкстры. * * @param string $source * @param string $target * @return array */ public function findShortestPath($source, $target) { $distances = []; $previous = []; $visited = []; $unvisitedNodes = $this->nodes; foreach ($this->nodes as $node => $_) { $distances[$node] = INF; $previous[$node] = null; } $distances[$source] = 0; while (!empty($unvisitedNodes)) { $minNode = null; $minDistance = INF; foreach ($unvisitedNodes as $node => $_) { if ($distances[$node] < $minDistance) { $minDistance = $distances[$node]; $minNode = $node; } } if ($minNode === null) { break; } foreach ($this->edges[$minNode] as $neighbor => $weight) { $newDistance = $distances[$minNode] + $weight; if ($newDistance < $distances[$neighbor]) { $distances[$neighbor] = $newDistance; $previous[$neighbor] = $minNode; } } $visited[$minNode] = true; unset($unvisitedNodes[$minNode]); } $path = []; $current = $target; while ($current !== null) { array_unshift($path, $current); $current = $previous[$current]; } return [ 'path' => $path, 'totalWeight' => $distances[$target], ]; } } ?>