|
1
|
|
|
<?php |
|
2
|
|
|
namespace Algorithms; |
|
3
|
|
|
|
|
4
|
|
|
class Dijkstra |
|
5
|
|
|
{ |
|
6
|
|
|
protected $points; |
|
7
|
|
|
protected $relations; |
|
8
|
|
|
|
|
9
|
|
|
public function __construct($relations = null) |
|
10
|
|
|
{ |
|
11
|
|
|
if (!empty($relations)) { |
|
12
|
|
|
$this->setRelations($relations); |
|
13
|
|
|
} |
|
14
|
|
|
} |
|
15
|
|
|
|
|
16
|
|
|
public function setRelations($relations) |
|
17
|
|
|
{ |
|
18
|
|
|
if (self::validate($relations)) { |
|
19
|
|
|
$this->relations = $relations; |
|
20
|
|
|
} else { |
|
21
|
|
|
if (is_callable($relations) && ($relations instanceof \Closure)) { |
|
22
|
|
|
$creator = new GraphTools\Creator; |
|
23
|
|
|
call_user_func($relations, $creator); |
|
24
|
|
|
|
|
25
|
|
|
$this->relations = $creator->createConnections(); |
|
26
|
|
|
} |
|
27
|
|
|
} |
|
28
|
|
|
} |
|
29
|
|
|
|
|
30
|
|
|
public function generate() |
|
31
|
|
|
{ |
|
32
|
|
|
$results = []; # Prepare results array |
|
33
|
|
|
|
|
34
|
|
|
# Analyze all relations |
|
35
|
|
|
foreach ($this->relations as $point => $relation) { |
|
36
|
|
|
# Prepare $points array by isset source point |
|
37
|
|
|
$this->points = [ |
|
38
|
|
|
$point => [ |
|
39
|
|
|
0, |
|
40
|
|
|
'', |
|
41
|
|
|
], |
|
42
|
|
|
]; |
|
43
|
|
|
|
|
44
|
|
|
$this->dist($point, $point); |
|
45
|
|
|
$results[$point] = $this->points; # Copy $points content to results array |
|
46
|
|
|
} |
|
47
|
|
|
|
|
48
|
|
|
return $results; |
|
49
|
|
|
} |
|
50
|
|
|
|
|
51
|
|
|
private function dist($source, $pointId, &$visited = []) |
|
52
|
|
|
{ |
|
53
|
|
|
$visited[$pointId] = true; # Set current point as visited |
|
54
|
|
|
|
|
55
|
|
|
# Prepare help variables |
|
56
|
|
|
$min_ptr = -1; |
|
57
|
|
|
$min = 0; |
|
58
|
|
|
|
|
59
|
|
|
# Analyzes point neighborhood |
|
60
|
|
|
foreach ($this->relations[$pointId] as $relation) { |
|
61
|
|
|
if ($relation[0] != $source) { # If current point is different than source |
|
62
|
|
|
list($min_ptr, $min) = $this->setMinPtr($relation, $visited, $min_ptr, $min); |
|
63
|
|
|
|
|
64
|
|
|
# Change the shortest way to current point |
|
65
|
|
|
$distance = $this->getShortestDistance($pointId); |
|
66
|
|
|
|
|
67
|
|
|
$this->updatePoint($pointId, $relation, $distance); |
|
68
|
|
|
} |
|
69
|
|
|
} |
|
70
|
|
|
|
|
71
|
|
|
# If isset unvisited point with minimal way go for it |
|
72
|
|
|
if ($min_ptr != -1) { |
|
73
|
|
|
$this->dist($source, $min_ptr, $visited); |
|
74
|
|
|
} |
|
75
|
|
|
} |
|
76
|
|
|
|
|
77
|
|
|
private function getShortestDistance($pointId) |
|
78
|
|
|
{ |
|
79
|
|
|
return isset($this->points[$pointId][0]) ? $this->points[$pointId][0] : 0; |
|
80
|
|
|
} |
|
81
|
|
|
|
|
82
|
|
|
private function setMinPtr($relation, $visited, $min_ptr, $min) |
|
83
|
|
|
{ |
|
84
|
|
|
if (empty($visited[$relation[0]])) { # If current point is not visited |
|
85
|
|
|
if ($min_ptr == -1) { # When minimal point is not finded |
|
86
|
|
|
$min_ptr = $relation[0]; |
|
87
|
|
|
$min = $relation[1]; |
|
88
|
|
|
} elseif ($min > $relation[1]) { |
|
89
|
|
|
$min_ptr = $relation[0]; |
|
90
|
|
|
$min = $relation[1]; |
|
91
|
|
|
} |
|
92
|
|
|
} |
|
93
|
|
|
|
|
94
|
|
|
return array($min_ptr, $min); |
|
95
|
|
|
} |
|
96
|
|
|
|
|
97
|
|
|
private function updatePoint($pointId, $relation, $distance) |
|
98
|
|
|
{ |
|
99
|
|
|
if (empty($this->points[$relation[0]])) { |
|
100
|
|
|
$this->points[$relation[0]] = [ |
|
101
|
|
|
$distance + $relation[1], |
|
102
|
|
|
((empty($this->points[$pointId][1])) ? $pointId : $this->points[$pointId][1]) . ':' . $relation[0], |
|
103
|
|
|
]; |
|
104
|
|
|
} else { |
|
105
|
|
|
if ($this->points[$relation[0]][0] > ($this->points[$pointId][0] + $relation[1])) { |
|
106
|
|
|
$this->points[$relation[0]] = [ |
|
107
|
|
|
(isset($this->points[$pointId][0]) ? $this->points[$pointId][0] : 0) + $relation[1], |
|
108
|
|
|
(empty($this->points[$pointId][1]) ? null : $this->points[$pointId][1] . ':') . $relation[0], |
|
109
|
|
|
]; |
|
110
|
|
|
} |
|
111
|
|
|
} |
|
112
|
|
|
} |
|
113
|
|
|
|
|
114
|
|
|
public function distances($point) |
|
115
|
|
|
{ |
|
116
|
|
|
$this->dist($point, $point); |
|
117
|
|
|
return $this->points; |
|
118
|
|
|
} |
|
119
|
|
|
|
|
120
|
|
View Code Duplication |
private static function validate($relations_array) |
|
|
|
|
|
|
121
|
|
|
{ |
|
122
|
|
|
if (is_array($relations_array)) { |
|
123
|
|
|
$return = true; |
|
124
|
|
|
foreach ($relations_array as $relations) { |
|
125
|
|
|
$return = self::checkPointRelations($relations); |
|
126
|
|
|
} |
|
127
|
|
|
|
|
128
|
|
|
return $return; |
|
129
|
|
|
} else { |
|
130
|
|
|
return false; |
|
131
|
|
|
} |
|
132
|
|
|
} |
|
133
|
|
|
|
|
134
|
|
View Code Duplication |
private static function checkPointRelations($relations) |
|
|
|
|
|
|
135
|
|
|
{ |
|
136
|
|
|
if (is_array($relations)) { |
|
137
|
|
|
$return = true; |
|
138
|
|
|
|
|
139
|
|
|
foreach ($relations as $relation) { |
|
140
|
|
|
$return = self::checkSingleRelation($relation); |
|
141
|
|
|
} |
|
142
|
|
|
|
|
143
|
|
|
return $return; |
|
144
|
|
|
} else { |
|
145
|
|
|
return false; |
|
146
|
|
|
} |
|
147
|
|
|
} |
|
148
|
|
|
|
|
149
|
|
|
private static function checkSingleRelation($relation) |
|
150
|
|
|
{ |
|
151
|
|
|
return (is_array($relation) && (count($relation) == 2) && isset($relation[0]) && isset($relation[1])); |
|
152
|
|
|
} |
|
153
|
|
|
} |
|
154
|
|
|
|
PHPAlgorithms /
Dijkstra-s-algorithm
Loading history...
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.