Wetenschapsforum

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

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 ?

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.

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?

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