-
Notifications
You must be signed in to change notification settings - Fork 0
/
FloydWarshall.php
110 lines (97 loc) · 2.96 KB
/
FloydWarshall.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
<?php
define('INFINITE', pow(2, (20 * 8 - 2)-1));
/**
* The Floyd-Warshall algorithm is a shortest path algorithm for graphs.
* Copyright 2021 Janne Mikkonen <[email protected]>
* License: https://opensource.org/licenses/MIT
*/
class FloydWarshall {
/**
* Distances array
* @var array
*/
private array $__distances = array();
/**
* Predecessor array
* @var array
*/
private array $__predecessor = array();
/**
* Weights array
* @var array
*/
private array $__weights = array();
/**
* Number of nodes
* @var int
*/
private int $__nodes = 0;
/**
* Node names array
* @var array
*/
private array $__nodenames = array();
/**
* Temporary data array
* @var array
*/
private array $__temp = array();
public function __construct(array $graphmatrice, array $nodenames) {
$this->__weights = $graphmatrice;
$this->__nodes = count($this->__weights);
if (!empty($nodenames) && $this->__nodes === count($nodenames)) {
$this->__nodenames = $nodenames;
}
$this->__floydwarshall();
}
/**
* PHP implementation of FloydWarshall algorithm
*/
private function __floydwarshall ():void {
for ($i = 0; $i < $this->__nodes; $i++) {
for ($j = 0; $j < $this->__nodes; $j++) {
if ($i == $j) {
$this->__distances[$i][$j] = 0;
} else if ($this->__weights[$i][$j] > 0) {
$this->__distances[$i][$j] = $this->__weights[$i][$j];
} else {
$this->__distances[$i][$j] = INFINITE;
}
$this->__predecessor[$i][$j] = $i;
}
}
for ($k = 0; $k < $this->__nodes; $k++) {
for ($i = 0; $i < $this->__nodes; $i++) {
for ($j = 0; $j < $this->__nodes; $j++) {
if ($this->__distances[$i][$j] > ($this->__distances[$i][$k] + $this->__distances[$k][$j])) {
$this->__distances[$i][$j] = $this->__distances[$i][$k] + $this->__distances[$k][$j];
$this->__predecessor[$i][$j] = $this->__predecessor[$k][$j];
}
}
}
}
}
private function __getPath(int $i, int $j):void {
if ( $i != $j ) {
$this->__getPath($i, $this->__predecessor[$i][$j]);
}
array_push($this->__temp, $j);
}
public function getPath($i, $j):array {
$this->__temp = array();
$this->__getPath($i, $j);
return $this->__temp;
}
public function getNodeNames():array {
return $this->__nodenames;
}
public function getNodes():int {
return $this->__nodes;
}
public function getDistances():array {
return $this->__distances;
}
public function getPredecessors():array {
return $this->__predecessor;
}
}