Tijden veranderen
Dijkstra algoritme
Dit script geeft een uitkomst, en hierin worden plaatsnamen genoemd.
Code (php)
1
$foo .= sprintf('%d => %d = %d minuten [%d]: (%s).'."\n"
Dit gedeelte is eigenlijk wat eruit komt. Ik wil met de uitkomst nog graag doorgaan, maar ik kan er niet achterkomen waar die uitkomst in 'opgeslagen' word. Als dit wel gebeurt.
Ik dacht eerst in $ourshortestpath, maar dat was het niet.
Code (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
111
112
113
114
115
116
117
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
111
112
113
114
115
116
117
<?PHP
class Dijkstra {
var $visited = array();
var $distance = array();
var $previousNode = array();
var $startnode =null;
var $map = array();
var $infiniteDistance = 0;
var $bestPath = 0;
var $matrixWidth = 0;
function Dijkstra(&$ourMap, $infiniteDistance) {
$this -> infiniteDistance = $infiniteDistance;
$this -> map = &$ourMap;
$this -> bestPath = 0;
}
function findShortestPath($start,$to = null) {
$this -> startnode = $start;
foreach (array_keys($this->map) as $i) {
if ($i == $this -> startnode) {
$this -> visited[$i] = true;
$this -> distance[$i] = 0;
} else {
$this -> visited[$i] = false;
$this -> distance[$i] = isset($this -> map[$this -> startnode][$i])
? $this -> map[$this -> startnode][$i]
: $this -> infiniteDistance;
}
$this -> previousNode[$i] = $this -> startnode;
}
$maxTries = count($this->map);
for ($tries = 0; in_array(false,$this -> visited,true) && $tries <= $maxTries; $tries++) {
$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true));
if($to !== null && $this -> bestPath === $to) {
break;
}
$this -> updateDistanceAndPrevious($this -> bestPath);
$this -> visited[$this -> bestPath] = true;
}
}
function findBestPath($ourDistance, $ourNodesLeft) {
$bestPath = $this -> infiniteDistance;
$bestNode = 0;
foreach ($ourNodesLeft as $node) {
if($ourDistance[$node] < $bestPath) {
$bestPath = $ourDistance[$node];
$bestNode = $node;
}
}
return $bestNode;
}
function updateDistanceAndPrevious($obp) {
foreach (array_keys($this->map) as $i) {
if( isset($this->map[$obp][$i])
&& ($this->map[$obp][$i] != $this->infiniteDistance || $this->map[$obp][$i] == 0 )
&& ($this->distance[$obp] + $this->map[$obp][$i] < $this -> distance[$i])
)
{
$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
$this -> previousNode[$i] = $obp;
}
}
}
function printMap(&$map) {
$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
$foo = '';
for($i=0,$im=count($map);$i<$im;$i++) {
for ($k=0,$m=$im;$k<$m;$k++) {
$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
}
$foo.= "\n";
}
return $foo;
}
function getResults($to = null) {
$ourShortestPath = array();
$foo = '';
foreach (array_keys($this->map) as $i) {
if($to !== null && $to !== $i) {
continue;
}
$ourShortestPath[$i] = array();
$endNode = null;
$currNode = $i;
$ourShortestPath[$i][] = $i;
while ($endNode === null || $endNode != $this -> startnode) {
$ourShortestPath[$i][] = $this -> previousNode[$currNode];
$endNode = $this -> previousNode[$currNode];
$currNode = $this -> previousNode[$currNode];
}
$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
if ($to === null || $to === $i) {
if($this -> distance[$i] >= $this -> infiniteDistance) {
$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
} else {
$foo .= sprintf('%d => %d = %d minuten [%d]: (%s).'."\n" ,
$this -> startnode,$i,$this -> distance[$i],
count($ourShortestPath[$i]),
implode('-',$ourShortestPath[$i]));
}
$foo .= str_repeat('-',20) . "\n";
if ($to === $i) {
break;
}
}
}
return $foo;
}
} // end class
?>
class Dijkstra {
var $visited = array();
var $distance = array();
var $previousNode = array();
var $startnode =null;
var $map = array();
var $infiniteDistance = 0;
var $bestPath = 0;
var $matrixWidth = 0;
function Dijkstra(&$ourMap, $infiniteDistance) {
$this -> infiniteDistance = $infiniteDistance;
$this -> map = &$ourMap;
$this -> bestPath = 0;
}
function findShortestPath($start,$to = null) {
$this -> startnode = $start;
foreach (array_keys($this->map) as $i) {
if ($i == $this -> startnode) {
$this -> visited[$i] = true;
$this -> distance[$i] = 0;
} else {
$this -> visited[$i] = false;
$this -> distance[$i] = isset($this -> map[$this -> startnode][$i])
? $this -> map[$this -> startnode][$i]
: $this -> infiniteDistance;
}
$this -> previousNode[$i] = $this -> startnode;
}
$maxTries = count($this->map);
for ($tries = 0; in_array(false,$this -> visited,true) && $tries <= $maxTries; $tries++) {
$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true));
if($to !== null && $this -> bestPath === $to) {
break;
}
$this -> updateDistanceAndPrevious($this -> bestPath);
$this -> visited[$this -> bestPath] = true;
}
}
function findBestPath($ourDistance, $ourNodesLeft) {
$bestPath = $this -> infiniteDistance;
$bestNode = 0;
foreach ($ourNodesLeft as $node) {
if($ourDistance[$node] < $bestPath) {
$bestPath = $ourDistance[$node];
$bestNode = $node;
}
}
return $bestNode;
}
function updateDistanceAndPrevious($obp) {
foreach (array_keys($this->map) as $i) {
if( isset($this->map[$obp][$i])
&& ($this->map[$obp][$i] != $this->infiniteDistance || $this->map[$obp][$i] == 0 )
&& ($this->distance[$obp] + $this->map[$obp][$i] < $this -> distance[$i])
)
{
$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
$this -> previousNode[$i] = $obp;
}
}
}
function printMap(&$map) {
$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
$foo = '';
for($i=0,$im=count($map);$i<$im;$i++) {
for ($k=0,$m=$im;$k<$m;$k++) {
$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
}
$foo.= "\n";
}
return $foo;
}
function getResults($to = null) {
$ourShortestPath = array();
$foo = '';
foreach (array_keys($this->map) as $i) {
if($to !== null && $to !== $i) {
continue;
}
$ourShortestPath[$i] = array();
$endNode = null;
$currNode = $i;
$ourShortestPath[$i][] = $i;
while ($endNode === null || $endNode != $this -> startnode) {
$ourShortestPath[$i][] = $this -> previousNode[$currNode];
$endNode = $this -> previousNode[$currNode];
$currNode = $this -> previousNode[$currNode];
}
$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
if ($to === null || $to === $i) {
if($this -> distance[$i] >= $this -> infiniteDistance) {
$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
} else {
$foo .= sprintf('%d => %d = %d minuten [%d]: (%s).'."\n" ,
$this -> startnode,$i,$this -> distance[$i],
count($ourShortestPath[$i]),
implode('-',$ourShortestPath[$i]));
}
$foo .= str_repeat('-',20) . "\n";
if ($to === $i) {
break;
}
}
}
return $foo;
}
} // end class
?>
Volgens mij staan hier wel de gegevens in die je nodig hebt.
Gewijzigd op 15/03/2011 17:34:16 door Arjan -
Maar zal is kijken..
Toevoeging op 15/03/2011 18:53:07:
Code (php)
1
$foo .= sprintf('%d => %d = %d minuten [%d]: (%s).'."\n"
Dit is eigenlijk de uitkomst, er komt bijv. te staan:
0 => 0 = 54 minuten [5]: (1-2-3-4-5).
Die getallen '1-2-3-4-5' die wil ik eigenlijk nog gebruiken..