Springen naar inhoud

Navigatiesysteem dmv dijkstra algoritme


  • Log in om te kunnen reageren

#1

BasvEsch

    BasvEsch


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 28 februari 2011 - 13:57

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Overdruk

    Overdruk


  • >100 berichten
  • 214 berichten
  • Ervaren gebruiker

Geplaatst op 28 februari 2011 - 23:21

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 ?
Cogito ergo sum.

#3

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 01 maart 2011 - 09:19

Heb je hier soms iets aan: http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP ?


Dat is waar hij de code in de eerste plaats al van gekopieerd heeft lol ;)

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.

#4

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 01 maart 2011 - 13:41

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?
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#5

Puntje

    Puntje


  • >250 berichten
  • 316 berichten
  • Ervaren gebruiker

Geplaatst op 01 maart 2011 - 16:07

Wat in het script moet je precies invullen? Met die gegevens kan ik je wel helpen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures