<?php
// Class representing a graph
class Graph {
private $vertices;
private $graph;
public function __construct($vertices) {
$this->vertices = $vertices;
$this->graph = array();
for ($i = 0; $i < $vertices; $i++) {
$this->graph[$i] = array_fill(0, $vertices, 0);
}
}
// Function to add an edge to the graph
public function addEdge($source, $destination, $weight) {
$this->graph[$source][$destination] = $weight;
$this->graph[$destination][$source] = $weight;
}
// Function to find the vertex with the minimum distance value
private function minDistance($distances, $visited) {
$min = PHP_INT_MAX;
$minIndex = -1;
for ($v = 0; $v < $this->vertices; $v++) {
if (!$visited[$v] && $distances[$v] <= $min) {
$min = $distances[$v];
$minIndex = $v;
}
}
return $minIndex;
}
// Function to print the shortest path from source to destination
public function printShortestPath($distances, $parent, $source, $destination) {
$path = array();
$pathIndex = 0;
$path[$pathIndex] = $destination;
$pathIndex++;
$currentVertex = $destination;
while ($parent[$currentVertex] !== -1) {
$path[$pathIndex] = $parent[$currentVertex];
$pathIndex++;
$currentVertex = $parent[$currentVertex];
}
echo "Shortest path from " . $this->getCityName($source) . " to " . $this->getCityName($destination) . ": ";
for ($i = $pathIndex - 1; $i >= 0; $i--) {
echo $this->getCityName($path[$i]);
if ($i > 0) {
echo " -> ";
}
}
echo "\n";
}
// Function to print the shortest route from source to destination
public function printShortestRoute($distances, $parent, $source, $destination) {
$path = array();
$pathIndex = 0;
$path[$pathIndex] = $destination;
$pathIndex++;
$currentVertex = $destination;
while ($parent[$currentVertex] !== -1) {
$path[$pathIndex] = $parent[$currentVertex];
$pathIndex++;
$currentVertex = $parent[$currentVertex];
}
echo "Shortest route from " . $this->getCityName($source) . " to " . $this->getCityName($destination) . ": ";
for ($i = $pathIndex - 1; $i >= 0; $i--) {
echo $this->getCityName($path[$i]);
if ($i > 0) {
echo " -> ";
}
}
echo "\n";
echo "Total distance: " . $distances[$destination] . "km\n";
echo "\n";
}
// Helper function to get city name based on index
private function getCityName($index) {
$cities = array(
"Rajshahi",
"Mymensingh",
"Dhaka",
"Barishal",
"Habiganj",
"Chattagram"
);
return $cities[$index];
}
// Function to find the shortest paths from all sources to all destinations using Dijkstra's algorithm
public function allShortestPaths() {
for ($source = 0; $source < $this->vertices; $source++) {
$distances = array_fill(0, $this->vertices, PHP_INT_MAX);
$distances[$source] = 0;
$visited = array_fill(0, $this->vertices, false);
$parent = array_fill(0, $this->vertices, -1);
for ($count = 0; $count < $this->vertices - 1; $count++) {
$u = $this->minDistance($distances, $visited);
$visited[$u] = true;
for ($v = 0; $v < $this->vertices; $v++) {
if (!$visited[$v] && $this->graph[$u][$v] !== 0 && $distances[$u] !== PHP_INT_MAX && $distances[$u] + $this->graph[$u][$v] < $distances[$v]) {
$distances[$v] = $distances[$u] + $this->graph[$u][$v];
$parent[$v] = $u;
}
}
}
for ($destination = 0; $destination < $this->vertices; $destination++) {
if ($destination !== $source) {
$this->printShortestPath($distances, $parent, $source, $destination);
}
}
}
}
}
// Example usage
$graph = new Graph(6);
$graph->addEdge(0, 1, 240); // Rajshahi to Mymensingh
$graph->addEdge(0, 2, 250); // Rajshahi to Dhaka
$graph->addEdge(0, 3, 360); // Rajshahi to Barishal
$graph->addEdge(1, 0, 240); // Mymensingh to Rajshahi
$graph->addEdge(1, 2, 110); // Mymensingh to Dhaka
$graph->addEdge(1, 4, 310); // Mymensingh to Habiganj
$graph->addEdge(2, 5, 290); // Dhaka to Chattagram
$graph->addEdge(2, 3, 250); // Dhaka to Barishal
$graph->addEdge(2, 4, 170); // Dhaka to Habiganj
$graph->addEdge(3, 1, 110); // Barishal to Mymensingh
$graph->addEdge(3, 5, 340); // Barishal to Chattagram
$graph->addEdge(4, 0, 360); // Habiganj to Rajshahi
$graph->addEdge(4, 3, 230); // Habiganj to Barishal
$graph->addEdge(4, 2, 250); // Habiganj to Dhaka
$graph->addEdge(4, 5, 290); // Habiganj to Chattagram
$graph->addEdge(5, 3, 230); // Chattagram to Barishal
$graph->addEdge(5, 2, 290); // Chattagram to Dhaka
$graph->allShortestPaths();
?>
Write, Run & Share PHP code online using OneCompiler's PHP online compiler for free. It's one of the robust, feature-rich online compilers for PHP language, running on the latest version 7. Getting started with the OneCompiler's PHP compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as PHP and start coding.
OneCompiler's PHP online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample PHP program which takes name as input and prints hello message with your name.
<?php
fscanf(STDIN, "%s\n", $name);
echo "Hello ".$name.".\n";
?>
PHP(Hypertext Preprocessor) is widely used server sripting language by Rasmus Lerdorf in the year 1994.
In PHP, there is no need to explicitly declare variables to reserve memory space. When you assign a value to a variable, declaration happens automatically. Variables are case-sensitive in PHP.
$variable_name = value;
If, If-else, Nested-Ifs are used when you want to perform a certain set of operations based on conditional expressions.
if(conditional-expression){
//code
}
if(conditional-expression){
//code if condition is true
} else {
//code if condition is false
}
if(condition-expression1) {
//code if above condition is true
} elseif(condition-expression2){
//code if above condition is true
}
elseif(condition-expression3) {
//code if above condition is true
}
...
else {
//code if all the conditions are false
}
Switch is used to execute one set of statement from multiple conditions.
switch(conditional-expression) {
case value1:
// code if the above value is matched
break; // optional
case value2:
// code if the above value is matched
break; // optional
...
default:
// code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
// code
}
// you can use any of the below syntax
foreach ($array as $element-value) {
//code
}
foreach ($array as $key => $element-value) {
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while(condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity.
function function_name(parameters) {
//code
}
function_name (parameters)