|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace PHPAlgorithms; |
|
4
|
|
|
|
|
5
|
|
|
use Closure; |
|
6
|
|
|
use PHPAlgorithms\Dijkstra\Creator; |
|
7
|
|
|
use PHPAlgorithms\Dijkstra\Exceptions\Exception; |
|
8
|
|
|
use PHPAlgorithms\Dijkstra\Path; |
|
9
|
|
|
use PHPAlgorithms\Dijkstra\Point; |
|
10
|
|
|
|
|
11
|
|
|
class Dijkstra { |
|
12
|
|
|
private $points = array(); |
|
13
|
|
|
|
|
14
|
|
|
public function __construct($function = null) |
|
15
|
|
|
{ |
|
16
|
|
|
if (!is_null($function)) { |
|
17
|
|
|
$this->add($function); |
|
18
|
|
|
} |
|
19
|
|
|
} |
|
20
|
|
|
|
|
21
|
|
|
public function add($function) |
|
22
|
|
|
{ |
|
23
|
|
|
if (!($function instanceof Closure)) { |
|
24
|
|
|
throw new Exception('Sent argument is not instance of Closure'); |
|
25
|
|
|
} |
|
26
|
|
|
|
|
27
|
|
|
$creator = new Creator(); |
|
28
|
|
|
$function($creator); |
|
29
|
|
|
|
|
30
|
|
|
if (empty($this->points)) { |
|
31
|
|
|
$this->points = $creator->dumpPoints(); |
|
32
|
|
|
} else { |
|
33
|
|
|
$index = count($this->points); |
|
34
|
|
|
|
|
35
|
|
|
foreach ($creator->dumpPoints() as $point) { |
|
36
|
|
|
$this->points[$index] = $point; |
|
37
|
|
|
$point->id = $index; |
|
38
|
|
|
|
|
39
|
|
|
$index++; |
|
40
|
|
|
} |
|
41
|
|
|
} |
|
42
|
|
|
|
|
43
|
|
|
return $this; |
|
44
|
|
|
} |
|
45
|
|
|
|
|
46
|
|
|
private function existsUnvisitedInNeighborhood($visited, $point) |
|
47
|
|
|
{ |
|
48
|
|
|
foreach ($this->points[$point]->relations as $relation) { |
|
49
|
|
|
if (!isset($visited[$relation->to->id])) { |
|
50
|
|
|
return true; |
|
51
|
|
|
} |
|
52
|
|
|
} |
|
53
|
|
|
|
|
54
|
|
|
return false; |
|
55
|
|
|
} |
|
56
|
|
|
|
|
57
|
|
|
public function generate($point) |
|
58
|
|
|
{ |
|
59
|
|
|
if ($point instanceof Point) { |
|
60
|
|
|
$point = $point->id; |
|
|
|
|
|
|
61
|
|
|
} |
|
62
|
|
|
|
|
63
|
|
|
if (!isset($this->points[$point])) { |
|
64
|
|
|
throw new Exception("Point with id {$point} not exists"); |
|
65
|
|
|
} |
|
66
|
|
|
|
|
67
|
|
|
$visited = array(); |
|
68
|
|
|
$unvisited = array_keys($this->points); |
|
69
|
|
|
$paths = array(); |
|
70
|
|
|
$previous = null; |
|
71
|
|
|
$relation = null; |
|
72
|
|
|
|
|
73
|
|
|
while (!empty($unvisited) && !is_null($point)) { |
|
74
|
|
|
unset($unvisited[$point]); |
|
75
|
|
|
$visited[$point] = $point; |
|
76
|
|
|
|
|
77
|
|
|
if (!isset($paths[$point])) { |
|
78
|
|
|
$paths[$point] = (new Path())->addNode($point); |
|
79
|
|
|
} |
|
80
|
|
|
|
|
81
|
|
|
if (!is_null($previous)) { |
|
82
|
|
|
if (!isset($paths[$point])) { |
|
83
|
|
|
$paths[$point]->copy($paths[$previous]); |
|
84
|
|
|
$paths[$point]->addNode($point, $relation->distance); |
|
85
|
|
|
} |
|
86
|
|
|
} |
|
87
|
|
|
|
|
88
|
|
|
$relation = $this->getMinimalRelation($unvisited, $paths, $point); |
|
89
|
|
|
|
|
90
|
|
|
$this->updatePaths($paths, $point); |
|
91
|
|
|
|
|
92
|
|
|
$previous = $point; |
|
93
|
|
|
|
|
94
|
|
|
if (!is_null($relation)) { |
|
95
|
|
|
$point = $relation->to |
|
96
|
|
|
->id; |
|
97
|
|
|
} else { |
|
98
|
|
|
$point = $paths[$point]->nodes[0]; |
|
99
|
|
|
|
|
100
|
|
|
if (!$this->existsUnvisitedInNeighborhood($visited, $point)) { |
|
101
|
|
|
$point = null; |
|
102
|
|
|
} |
|
103
|
|
|
} |
|
104
|
|
|
}; |
|
105
|
|
|
|
|
106
|
|
|
return $paths; |
|
107
|
|
|
} |
|
108
|
|
|
|
|
109
|
|
|
public function generateAll() |
|
110
|
|
|
{ |
|
111
|
|
|
$generated = array(); |
|
112
|
|
|
|
|
113
|
|
|
foreach ($this->points as $index => $point) { |
|
114
|
|
|
$generated[$index] = $this->generate($point); |
|
115
|
|
|
} |
|
116
|
|
|
|
|
117
|
|
|
return $generated; |
|
118
|
|
|
} |
|
119
|
|
|
|
|
120
|
|
|
private function getMinimalRelation($unvisited, $paths, $point) |
|
121
|
|
|
{ |
|
122
|
|
|
$minimalValue = INF; |
|
123
|
|
|
$minimalIndex = -1; |
|
124
|
|
|
|
|
125
|
|
|
foreach ($this->points[$point]->relations as $index => $relation) { |
|
126
|
|
|
if (($minimalValue > ($relation->distance + $paths[$point]->distance)) && isset($unvisited[$relation->to->id])) { |
|
127
|
|
|
$minimalIndex = $index; |
|
128
|
|
|
$minimalValue = $relation->distance + $paths[$point]->distance; |
|
129
|
|
|
} |
|
130
|
|
|
} |
|
131
|
|
|
|
|
132
|
|
|
if ($minimalIndex != -1) { |
|
133
|
|
|
return $this->points[$point] |
|
134
|
|
|
->relations[$minimalIndex]; |
|
135
|
|
|
} else { |
|
136
|
|
|
return null; |
|
137
|
|
|
} |
|
138
|
|
|
} |
|
139
|
|
|
|
|
140
|
|
|
public function updatePaths(&$paths, $point) |
|
141
|
|
|
{ |
|
142
|
|
|
foreach ($this->points[$point]->relations as $relation) { |
|
143
|
|
|
if (isset($paths[$relation->to->id])) { |
|
144
|
|
|
if ($paths[$relation->to->id]->distance > ($paths[$point]->distance + $relation->distance)) { |
|
145
|
|
|
$paths[$relation->to->id]->copy($paths[$point]) |
|
146
|
|
|
->addNode($relation->to->id, $relation->distance); |
|
147
|
|
|
} |
|
148
|
|
|
} else { |
|
149
|
|
|
$paths[$relation->to->id] = (new Path())->copy($paths[$point]) |
|
150
|
|
|
->addNode($relation->to->id, $relation->distance); |
|
151
|
|
|
} |
|
152
|
|
|
} |
|
153
|
|
|
} |
|
154
|
|
|
} |
|
155
|
|
|
|
PHPAlgorithms /
Dijkstra-s-algorithm
An attempt at access to an undefined property has been detected. This may either be a typographical error or the property has been renamed but there are still references to its old name.
If you really want to allow access to undefined properties, you can define magic methods to allow access. See the php core documentation on Overloading.