Dijkstra algoritme in php

Overzicht Reageren

Sponsored by: Vacatures door Monsterboard

Henry Wiersma

Henry Wiersma

02/12/2012 16:18:41
Quote Anchor link
Hallo,

Voor school zijn wij bezig om een navigatie app te maken door onze school heen. Zodat nieuwe leerlingen makkelijker alles kunnen vinden.

Om de route te bepalen willen wij gebruik maken van het Dijkstra algoritme. Er zijn PHP codes op het internet te vinden waar dit ritme in verwerkt is, alleen krijg ik die scripts niet werkend.

Bij mij kan de code wel de route bepalen wanneer de punten naast elkaar liggen, maar wanneer hij een route moet berekenen via meerdere knooppunten dan zegt hij dat die route niet mogelijk is.

Ik ben nog geen grote held in het programmeren met PHP, waarschijnlijk zie ik ook iets over het hoofd, maar zelf weet ik niet wat.

Heeft iemand mij helpen?

Met vriendelijke groet,
Henry Wiersma

Code die ik op internet gevonden heb:
Code (php)
PHP script in nieuw venster Selecteer het PHP script
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
118
119
120
121
<?PHP
class Dijkstra {
 
    var
$visited = array();
    var
$distance = array();
    var
$previousNode = array();
    var
$startnode =null;
    var
$map = array();
    var
$infiniteDistance = 0;
    var
$numberOfNodes = 0;
    var
$bestPath = 0;
    var
$matrixWidth = 0;
 
    function
Dijkstra(&$ourMap, $infiniteDistance) {
        $this -> infiniteDistance = $infiniteDistance;
        $this -> map = &$ourMap;
        $this -> numberOfNodes = count($ourMap);
        $this -> bestPath = 0;
    }
 
    function
findShortestPath($start,$to = null) {
        $this -> startnode = $start;
        for ($i=0;$i<$this -> numberOfNodes;$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 = $this -> numberOfNodes;
        $tries = 0;
        while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {            
            $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;
            $tries++;
        }
    }
 
    function
findBestPath($ourDistance, $ourNodesLeft) {
        $bestPath = $this -> infiniteDistance;
        $bestNode = 0;
        for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
            if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
                $bestPath = $ourDistance[$ourNodesLeft[$i]];
                $bestNode = $ourNodesLeft[$i];
            }
        }

        return $bestNode;
    }
 
    function
updateDistanceAndPrevious($obp) {        
        for ($i=0;$i<$this -> numberOfNodes;$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 = '';
        for ($i = 0; $i < $this -> numberOfNodes; $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
?>

Usage Example
Code (php)
PHP script in nieuw venster Selecteer het PHP script
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
<?php
 
// 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(0,1,4),
    array(0,2,I),
    array(1,2,5),
     array(1,3,5),
    array(2,3,5),
    array(3,4,5),
    array(4,5,5),
    array(4,5,5),
    array(2,10,30),
    array(2,11,40),
    array(5,19,20),
    array(10,11,20),
    array(12,13,20),
);

 
$ourMap = array();
 
 
// Read in the points and push them into the map
 
for ($i=0,$m=count($points); $i<$m; $i++) {
    $x = $points[$i][0];
    $y = $points[$i][1];
    $c = $points[$i][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++) {
    for ($k=0; $k < $matrixWidth; $k++) {
        if ($i == $k) $ourMap[$i][$k] = 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
 
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>';
 
?>
 
PHP hulp

PHP hulp

20/06/2024 21:51:51
 
Albert de Wit

Albert de Wit

02/12/2012 18:19:55
Quote Anchor link
Kan/Wil iemand mij helpen?*

Hallo Henry,

Dit is niet zo moeilijk. Het Dijkstra algoritme is namelijk al gemaakt, het enige wat je nog moet doen is het werkend maken.

Probleem is alleen dat je school waarschijnlijk te maken heeft met meerdere verdiepingen. Ik denk niet dat het dijkstra algoritme daarop werkt. Je geeft namelijk een x/y coordinaat in en je krijgt de snelste weg daardoor.
Mooi voorbeeld:
Afbeelding
 
Nick Dijkstra

Nick Dijkstra

02/12/2012 18:37:06
Quote Anchor link
Ik weet niet zeker, maar is dit niks: Linkje
 
Albert de Wit

Albert de Wit

02/12/2012 18:38:40
Quote Anchor link
Dijkstra's algorithme werkt niet met verdiepingen. Het stukje code gepost door Henry tekent dacht ik direct ook de route.
 
Henry Wiersma

Henry Wiersma

03/12/2012 11:35:46
Quote Anchor link
Waarom kun je geen verdiepingen toepassen? Het algoritme werkt toch met knooppunten en paden tussen de knooppunten.

als je trappen ziet als paden die knooppunten op verschillende verdiepingen met elkaar verbind. Dan maakt het volgens mij niet uit hoeveel verdiepingen er zijn.

het script wat ik gepost heb, hoe moet ik die werkend krijgen? Ik heb er zelf al veel tijd in gestoken maar heb hem nog niet werkend gekregen.
 
Kris Peeters

Kris Peeters

03/12/2012 11:54:27
Quote Anchor link
Voor zover ik me herinner is Dijkstra een 2D algoritme.
Gewijzigd op 03/12/2012 11:56:05 door Kris Peeters
 
Henry Wiersma

Henry Wiersma

03/12/2012 12:01:36
Quote Anchor link
Je kunt verdiepingen toch gewoon 2D zien? een trap is niets meer dan een pad die twee knooppunten met elkaar verbindt. net als je op een begaande grond 2 knooppunten met elkaar verbindt.

Als ik dat script uitvoer werkt het script niet. het script kan geen verbinding leggen tussen twee knooppunten via een ander knoopppunt. Want doe ik fout in de code waardoor het niet werkt zoals het bedoeld is?
 
Erwin H

Erwin H

03/12/2012 12:21:06
Quote Anchor link
Albert de Wit op 02/12/2012 18:19:55:
Probleem is alleen dat je school waarschijnlijk te maken heeft met meerdere verdiepingen. Ik denk niet dat het dijkstra algoritme daarop werkt.

Kris Peeters op 03/12/2012 11:54:27:
Voor zover ik me herinner is Dijkstra een 2D algoritme.

Dit is natuurlijk klinklare onzin. Het Dijkstra algoritme lost een wiskundig optimalisatie model op (het zogenaamde 'kortste pad probleem'). Zolang je het probleem dat je hebt wiskundig kan modelleren als een kortste pad probleem (het hoeft dus niet eens een echt kortste pad probleem te zijn), kan je het in principe met het Dijkstra Algoritme oplossen. In hoeveel dimensies je het probleem modeleert is echt niet van belang.

Nu is natuurlijk alleen de vraag waarom gegeven implementatie van het algoritme niet werkt. Wedervraag is dan, wat gaat er mis? Welke meldingen krijg je, tot waar loopt het nog zoals het zou moeten? Wat heb je al gedaan om het te debuggen?
 
Henry Wiersma

Henry Wiersma

03/12/2012 12:28:10
Quote Anchor link
In heb het complete script zoals ik in het begin gepost heb online gezet. Het script kan netjes de paden berekenen tussen de knooppunten zolang ze maar een verbinding met elkaar hebben. Wanneer er een tussenknooppunt tussen zit, dus van knooppunt 1 naar knooppunt 4 via knooppunt 2 en 3 dan zegt het script dat er geen verbinding mogelijk is. Het kan dus geen route berekenen van een knooppunt via andere knooppunten naar een eindknooppunt. Terwijl volgens mij hier het script voor bedoeld is.
 
Kris Peeters

Kris Peeters

03/12/2012 12:30:57
Quote Anchor link
Erwin H op 03/12/2012 12:21:06:
... Dit is natuurlijk klinklare onzin. Het Dijkstra algoritme lost een wiskundig optimalisatie model ...


Okay, laat me dit herformuleren
Deze php-class houdt geen rekening met een derde dimensie.
 
Erwin H

Erwin H

03/12/2012 12:58:00
Quote Anchor link
Kris Peeters op 03/12/2012 12:30:57:
Deze php-class houdt geen rekening met een derde dimensie.

Het gebruikte model ook niet, dus dat is niet relevant.


Maar weer teruggaand naar de eigenlijke vraag. Zonder enig commentaar in het script (erg slecht!) is het moeilijk de echte fout te traceren. Iets wat me wel opvalt is regel 40. Daar wordt een variabele $to gebruikt, die verder nog niet is geinitialiseerd. Volgens mij zit daar het begin van het probleem.
Daar zit wel het probleem maar dan anders.... $to wordt meegegeven als parameter aan de functie findShortestPath. Alleen zeg je in het commentaar dat je de route van 0 naar 13 wilt zoeken, maar roep je de functie aan met $dijkstra->findShortestPath(0); . Volgens mij moet dat $dijkstra->findShortestPath(0, 13); zijn.
Gewijzigd op 03/12/2012 13:01:25 door Erwin H
 
Henry Wiersma

Henry Wiersma

03/12/2012 17:33:36
Quote Anchor link
Dus het script is slecht, oke dan ga ik er niet meer mee verder.
Nick heeft ook een linkje gepost, zal eens kijken wat dat is.(iemand ervaring?)
 
Albert de Wit

Albert de Wit

03/12/2012 21:18:36
Quote Anchor link
Henry, als je nou verteld wat je probeert te bereiken is het misschien mogelijk dat iemand anders een veel makkelijkere oplossing heeft.

Toevoeging op 03/12/2012 21:18:47:

Henry, als je nou verteld wat je probeert te bereiken is het misschien mogelijk dat iemand anders een veel makkelijkere oplossing heeft.
 



Overzicht Reageren

 
 

Om de gebruiksvriendelijkheid van onze website en diensten te optimaliseren maken wij gebruik van cookies. Deze cookies gebruiken wij voor functionaliteiten, analytische gegevens en marketing doeleinden. U vindt meer informatie in onze privacy statement.