Navigatiesysteem dmv dijkstra algoritme
Moderators: ArcherBarry, Fuzzwood
- Berichten: 2
Navigatiesysteem dmv dijkstra algoritme
Hallo, ik heb een vraag over het dijkstra algoritme waar ik nu met mijn projectgroep mee bezig ben. We hebben een code gevonden om de kortste route te berekenen, maar we kunnen niet in het php( zeg maar de webpagina) , het benodigde knooppunt invullen, dit kan alleen in het php script zelf. We komen er niet uit hoe we dit voor elkaar kunnen krijgen, heeft er misschien iemand een oplossing.
<?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 [%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
?>
<?php
$pt=$_POST['pt'];
echo "$pt<br>";
// I is the infinite distance.
define('I',1000);
// Size of the matrix
$matrixWidth = 20;
// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
array(11,1,3),
array(1,7,20.4),
array(7,12,5.5),
array(7,8,14.2),
array(8,9,19.5),
array(12,0,7.2),
array(11,2,2.5),
array(2,3,19.2),
array(3,4,9.5),
array(6,5,2.2),
array(5,4,0.7),
array(4,10,1.6),
array(10,9,1.9),
array(10,12,8.1),
array(12,0,7.2),
array(9,0,2.3),
array(3,13,0.8),
array(13,12,3.1),
array(12,10,8.1),
array(13,3,0.8),
array(8,7,14.2),
);
$ourMap = array();
// Read in the points and push them into the map
foreach ($points as $point) {
$x = $point[0];
$y = $point[1];
$c = $point[2];
$ourMap[$x][$y] = $c;
$ourMap[$y][$x] = $c;
}
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
for ($i=0; $i < $matrixWidth; $i++) {
$ourMap[$i][$i] = 0;
}
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
$dijkstra->findShortestPath(0);
// Display the results
$pt=$_POST['pt'];
echo $dijkstra->getResults(6);
/*
echo '<pre>';
echo "the map looks like:\n\n";
echo $dijkstra -> printMap($ourMap);
echo "\n\nthe shortest paths from point 0:\n";
echo $dijkstra -> getResults();
echo '</pre>';
*/
?>
Groeten
<?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 [%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
?>
<?php
$pt=$_POST['pt'];
echo "$pt<br>";
// I is the infinite distance.
define('I',1000);
// Size of the matrix
$matrixWidth = 20;
// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
array(11,1,3),
array(1,7,20.4),
array(7,12,5.5),
array(7,8,14.2),
array(8,9,19.5),
array(12,0,7.2),
array(11,2,2.5),
array(2,3,19.2),
array(3,4,9.5),
array(6,5,2.2),
array(5,4,0.7),
array(4,10,1.6),
array(10,9,1.9),
array(10,12,8.1),
array(12,0,7.2),
array(9,0,2.3),
array(3,13,0.8),
array(13,12,3.1),
array(12,10,8.1),
array(13,3,0.8),
array(8,7,14.2),
);
$ourMap = array();
// Read in the points and push them into the map
foreach ($points as $point) {
$x = $point[0];
$y = $point[1];
$c = $point[2];
$ourMap[$x][$y] = $c;
$ourMap[$y][$x] = $c;
}
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
for ($i=0; $i < $matrixWidth; $i++) {
$ourMap[$i][$i] = 0;
}
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
$dijkstra->findShortestPath(0);
// Display the results
$pt=$_POST['pt'];
echo $dijkstra->getResults(6);
/*
echo '<pre>';
echo "the map looks like:\n\n";
echo $dijkstra -> printMap($ourMap);
echo "\n\nthe shortest paths from point 0:\n";
echo $dijkstra -> getResults();
echo '</pre>';
*/
?>
Groeten
- Berichten: 214
Re: Navigatiesysteem dmv dijkstra algoritme
Zelf gebruik ik altijd java en ken ik ook niet de precieze syntax van PHP... Ook al zal dat misschien niet moeilijk zijn.
Heb je hier soms iets aan: http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP ?
Heb je hier soms iets aan: http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP ?
Cogito ergo sum.
- Berichten: 2.609
Re: Navigatiesysteem dmv dijkstra algoritme
Dat is waar hij de code in de eerste plaats al van gekopieerd heeft lolHeb je hier soms iets aan: http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP ?
Ik ken je precieze opdracht niet, maar voor mij zou je elke regel code die je gebruikt ook moeten begrijpen. Je moet begrijpen wat je programma doet en hoe je het moet gebruiken.
Je vraag is hoe je de gebruiker laat kiezen tussen welke punten hij een pad zoekt? Dan moet je op een of andere manier (een form of een graaf ofzo) de gebruiker een keuze geven en die dien je dan als parameters mee te geven aan het algoritme ipv de constantes die er nu in staan.
- Berichten: 7.390
Re: Navigatiesysteem dmv dijkstra algoritme
Kan je niet gebruik maken van een html-form, waar je die invult, en deze dan versturen (GET/POST) en op die manier implementeren?
Of begrijp ik de vraag verkeerd?
Of begrijp ik de vraag verkeerd?
"C++ : Where friends have access to your private members." Gavin Russell Baker.
-
- Berichten: 316
Re: Navigatiesysteem dmv dijkstra algoritme
Wat in het script moet je precies invullen? Met die gegevens kan ik je wel helpen.