<?
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],
];
}
}
?>