<?
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 = 5;
$numEdges = 20;
$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']);
}
print_r($graphData['edges']);
$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 $nodes = [];
private $edges = [];
public function addEdge($node1, $node2, $weight) {
$this->edges[] = ['node1' => $node1, 'node2' => $node2, 'weight' => $weight];
$this->nodes[$node1] = ['minWeight' => INF, 'flag' => 0];
$this->nodes[$node2] = ['minWeight' => INF, 'flag' => 0];
}
public function findShortestPath($startNode, $endNode) {
$this->nodes[$startNode]['minWeight'] = 0;
while (true) {
$minWeightNode = null;
foreach ($this->nodes as $node => $nodeData) {
if (in_array($nodeData['flag'], [0, 2]) && ($minWeightNode === null || $nodeData['minWeight'] < $this->nodes[$minWeightNode]['minWeight'])) {
$minWeightNode = $node;
}
}
if ($minWeightNode === null) {
break;
}
if ($minWeightNode == $endNode) {
$this->nodes[$minWeightNode]['flag'] = 4;
break;
}
$this->nodes[$minWeightNode]['flag'] = 3;
foreach ($this->edges as $edge) {
if ($edge['node1'] == $minWeightNode || $edge['node2'] == $minWeightNode) {
$neighborNode = $edge['node1'] == $minWeightNode ? $edge['node2'] : $edge['node1'];
if (in_array($this->nodes[$neighborNode]['flag'], [0, 2])) {
$newWeight = $this->nodes[$minWeightNode]['minWeight'] + $edge['weight'];
if ($newWeight < $this->nodes[$neighborNode]['minWeight']) {
$this->nodes[$neighborNode]['minWeight'] = $newWeight;
$this->nodes[$neighborNode]['flag'] = 1;
}
}
}
}
}
if ($this->nodes[$endNode]['flag'] == 4) {
$path = [];
$currentNode = $endNode;
while ($currentNode != $startNode) {
$path[] = $currentNode;
$prevNode = null;
$minWeightDifference = INF;
foreach ($this->edges as $edge) {
if ($edge['node1'] == $currentNode || $edge['node2'] == $currentNode) {
$neighborNode = $edge['node1'] == $currentNode ? $edge['node2'] : $edge['node1'];
if ($this->nodes[$neighborNode]['flag'] == 3) {
$weightDifference = $this->nodes[$currentNode]['minWeight'] - $this->nodes[$neighborNode]['minWeight'] - $edge['weight'];
if ($weightDifference < $minWeightDifference) {
$minWeightDifference = $weightDifference;
$prevNode = $neighborNode;
}
}
}
}
$currentNode = $prevNode;
}
$path[] = $startNode;
$path = array_reverse($path);
return ['path' => $path, 'totalWeight' => $this->nodes[$endNode]['minWeight']];
} else {
return ['path' => [], 'totalWeight' => INF];
}
}
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],
];
}
}
?>