Algoritmo di Dijkstra..!

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Ragazzi pensavo di implementare l'algoritmo di Dijkstra in PHP, in modo da poter calcolare il cammino minimo dal mio luogo fino ad una destinazione (ad esempio un utente dalla lista) passando prima attraverso altri utenti, così da avere un'ottimizzazione della spedizione. Ribadisco che il tutto è a titolo di studio!
Secondo voi mi basta avere la distanza di ogni utente dal mio locale per poter calcolare il cammino minimo tra vari utenti??? sono curioso di provare questo algoritmo in una paginetta PHP, dato che per ora ho un database con salvate all'interno tutte le distanze degli utenti dal mio luogo..


Girando per la rete ho trovato vari algoritmi tra cui questo:
PHP:
<?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
<?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>';
?>
 

Eliox

Utente Attivo
25 Feb 2005
4.390
3
0
Dovrei ripassare perchè mi riaddormentai alla prima lezione sui grafi e da allora non m svegliai più :)
Comunque qui c'è una proposta di implementazione tramite una funzione
 

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Allora, mi sono letto un pò di cosucce a riguardo ed da come ho potuto capire c'è bisogno di avere tutte le distanze tra tutti i punti (correggettemi se sbaglio)!

quindi nel caso il mio punto
A (Inizio) ------>2Km da B ---->3Km da C, ed B----->1Km da C ed ancora avere che B--->6 Km da D, C---->4Km da D,

in questo caso il cammino minimo da A a D è dato da A+B+C+D (2+1+4=7) spero che ho capito il funzionamento...quindi ora sono dell'idea che c'è bisogno non solo di avere la distanza dal mio punto di partenza ma anche quella tra ogni punto con un'altro punto adiacente...

ps. Ho visto la function, solo che il tipo non specifica l'array come deve essere per poterlo testare! mo faccio qualche tentativo!
 

Eliox

Utente Attivo
25 Feb 2005
4.390
3
0
in questo caso il cammino minimo da A a D è dato da A+B+C+D (2+1+4=7) spero che ho capito il funzionamento...quindi ora sono dell'idea che c'è bisogno non solo di avere la distanza dal mio punto di partenza ma anche quella tra ogni punto con un'altro punto adiacente...

Correggimi tu se sbaglio, ma il percorso da te indicato è linerare, questo perché per coprire la distanza minima devi attraversare tutti i punti; hai la possibilità di realizzare un semplice grafo A-D sulla base delle distanze indicate e di postarlo qui?

Qualcosa del genere:

dijkstra-algorithm.jpg
 

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Oggi ho perso un pò di tempo a ragionare..e quello che non riesco a capire o almeno non trovo in nessuna descrizione è questo, quanti nodi collego al Nodo principale (ossia di partenza)?? eppoi volevo sapere anche,per decidere l'ordine del grafo ho pensato di andare a controllare le distanza dal nodo principale e quindi avvicinare vicino al nodo principale quelli più vicini per cercare di iniziare la creazione del grafo..purtroppo sembra un pò complessa la cosa, dato che bisogna gestire indirizzi dai quali bisogna calcolare la distanza con il nodo successivo e salvarla in un campo del database..ho un pò di perplessità ma continuerò a riflettere sulla cosa.
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
quanti nodi collego al Nodo principale (ossia di partenza)??
una risposta valida potrebbe essere "dipende", cioè dipende dai nodi che devi attraversare e dalla "strada" che devi fare per raggiungerli.
facciamo un esempio che tu debba fare delle consegne partendo da padova nelle città di venezia, trento, treviso, vicenza, verona, per poi tornare a padova
il primo nodo sarà pd_partenza
l'ultimo nodo sara pd_arrivo
il buon senzo ti dice intanto che non ci deve essere un collegamento diretto tra partenza ed arrivo in quanto il peso (distanza) è uguale a 0, quindi sarebbe sempre il percorso minimo.
poi verifichi le altre strade (guarda che invento un po')
esiste una strada che colleghi direttamente padova con
- venezia: si -> creo il collegamento con il suo peso
- vicenza: si -> creo il collegamento con il suo peso
- verona: no -> non posso creare il collegamento
...ecc... per padova
passo al secondo nodo es. vicenza:
esiste un collegamento tra vicenza e:
- padova: già fatto
- venezia: no -> non posso creare il collegamento
- verona: si -> creo il collegamento con il suo peso
..ecc..
ecc... con tutti i nodi
penso che questo sia il metodo per costruirsi il grafo (con molta pazienza)
 

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Ho capito perfettamente quello che hai scritto :) anzi ti ringrazio per avermi schiarito un pò le idee.

Ma quindi se metto caso io volessi anallizzare il problema in altro modo e cioè ad esempio ho un 2 ordini e so che quegli ordini uno deve essere consegnato ad esempio a NAPOLI (in via dei mille) e l'altro deve essere consegnato sempre a NAPOLI però a (via roma) che sono strade pressochè vicine tra loro, ora per evitare una doppia spedizione separata nel tempo, potrei farne solo 1 di spedizione anche se questa mi costa 1 ora in più nella preparazione dell'ordine..qualche idea su come gestire la cosa? io pensavo che magari potrei per prima cosa dividere gli ordini (fancedo una query sul database) a seconda del capoluogo dove sono diretti..ad esempio (NAPOLI) eppoi calcolare la distanza tra le 2 strade e applicare un controllo sulla distanza risultante fuori dal calcolo..potrebbe andare come cosa? o dovrei sempre tenere in ballo qualche algo come Dijkstra?
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
se devi calcolare un percorso minimo tra diverse possibilità di nodi/percorso devi ricorre a dijkstra o qualche algoritmo simile.
poi tutto dipende da quanti nodi/percorsi hai.
è evidente che se i nodi/percorsi (es.) sono due o tre credo che tu faccia prima a chiamare google maps e valutare a lume di naso.
se i nodi/percorsi sono molti il discorso cambia.
comunque penso che se vuoi farti uno script+mysql che in funzione dei nodi/percorsi ti calcoli di volta in volta il percorso minimo, tu ti stia cacciando in un ginepraio.
pensa solo a quante distanze prima devi calcolare e salvare nel db e tutte le volte crearti un grafo, cioè tutte le combinazioni realmente possibili.
solo nel semplice esempio che ti ha postato eliox (immagine) hai sei nodi, e vedi quante distanze devi calcolare, è molto facile che il numero cresca in modo esponenziale.
pensa alle combinazioni che devi avere, fai una prova con i soli capoluoghi di provincia di una regione (esclusa la valle d'aosta :)).

se vuoi implementare l'algoritmo per tuo diletto personale ok, ma se ti serve per lavoro, valutando il rapporto costi/benefici, forse ti conviene cercare qualcosa di già pronto (credo che esista)
 

vitelli

Utente Attivo
23 Mar 2012
41
0
0
ti ringrazio ancora per la risposta, si effettivamente hai ragione, calcolare tutte quelle distanze è estremamente complicato e perdipiù complesso/scocciante, penso che valuterò una soluzione semplice ossia visualizzare tutte le strade di quel determinato capoluogo e calcolare la distanza solo tra queste valutando se conviene provare a convogliare in un'unica spedizone, imposterei un controllo sulla strada più vicina al mio posto di partenze e calcolo la distanza dalla successiva strada e valuto setra se effettivamente conviene allungarsi dalla strada in corso verso la prossima consegna oppure magari conviene rifare una seconda spedizione partendo dalla base (luogo di partenza). Comunque questo progetto è a solo titolo di studio per un esame universitario e mi sono afffacciato al php da 1 mesetto quindi magari tendo a chiedere molto sul forum per imparare e capire un pò di cosuccie :) e ringrazio tutti per l'aiuto.
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
mi sono afffacciato al php da 1 mesetto quindi magari tendo a chiedere molto sul forum per imparare e capire un pò di cosuccie
no no non chiedi troppo, è che qualvolta non si dare una risposta come si vorrebbe.
quindi continua a frequentare e chiedi, passato il "mesetto" puoi iniziare anche a rispondere (non solo php);)
 

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Allora rieccomi a ripensare come migliorare la gestione delle spedizioni. Cercando su internet mi sono imbattuto in questo sito : http://findthebestrouter.com/RouteFinder.html questo sito ha dei form dove si inseriscono gli indirizzi dei vari punti di arrivo e cliccando su "Calcolate" non fa altro che calcolare la strada migliore passando per tutti i punti indicati..ora ho notato che la pagina automaticamente posiziona gli indirizzi in base alla loro distanza dal punto di partenza (in pratica è come se calcolasse prima le distanza per ogni singolo indirizzo rispetto all'indirizzo di partenza) e poi le mette ordine gli indirizzo dal più vicino al più distante e per finire effettua una query a Google Map del tipo FROM: "strada iniziare" to: Indiirzzo1 to:indirizzo2 e google non fa altro che restituire l'intero percorso con mappa...
rivolendo ricostruire questa procedura ho fatto varie prove e ho creato una paginetta con delle checkbox che stampavano gli indirizzi di spedizione ordinate in base alla distanza dal luogo di partenza, l'utente (amministratore o corriere) seleziona cliccando nel checkbox gli indirizzi che gli interessa usare per fare un percorso comune, il tutto viene rimandato sotto un'array in una seconda pagina che lo da in pasto ad una mappa di googlemap..per ora pare che la ocsa mi possa funzionare e mi pare effettivamente forse la scelta migliore senza sbattersi troppo con algoritmi o altro! l'unica cosa che chiedo, è possibile disabilitare il tasto CALCOLA??? cioè evitare che l'utente debba premerlo per calcolare il percorso???

eccovi il codice e l'immagine del funzionamento che per ora ho ottenuto:

PHP:
  <body onload="initialize()" onunload="GUnload()">
<script src=" http://maps.google.com/?file=api&amp;v=2.x&amp;key=AIzaSyBgCCJSq-1V5j3gpbUxofBEx8nu0amk2EE" type="text/javascript"></script>
 <body background="images/bg1.png">
 <script type="text/javascript">
 var map;
    var gdir;
    var geocoder = null;
    var addressMarker;

    function initialize() {
      
	  if (GBrowserIsCompatible()) {
		map = new GMap2(document.getElementById("map_canvas"));
		map.addControl(new GSmallMapControl());
		map.addControl(new GMapTypeControl());
		map.setCenter(new GLatLng(40.6256298,14.3721715), 13);
		
		var marker = new GMarker(new GLatLng(40.6256298,14.3721715))
		map.addOverlay(marker);
		marker.openInfoWindowHtml("<b>Orders Portal</b><br>Via Tasso 8<br>80067 Sorrento (NA)");
		
		gdir = new GDirections(map, document.getElementById("directions"));
		GEvent.addListener(gdir, "error", handleErrors);
	  }
    }
    
    function setDirections(fromAddress) {
	  locale="it";
	 
	 gdir.load("from: Via Tasso,8,80067 Sorrento to: " + fromAddress + " ");
    //gdir.load("from: " + fromAddress + " to: Via Tasso, 8, 80067 Sorrento");
    }

    function handleErrors(){
	   if (gdir.getStatus().code == G_GEO_UNKNOWN_ADDRESS)
	     alert("Indirizzo non trovato");
	   else if (gdir.getStatus().code == G_GEO_SERVER_ERROR)
	     alert("Si è verificato un errore nella geocodifica degli indirizzi");
	   
	   else if (gdir.getStatus().code == G_GEO_MISSING_QUERY)
	     alert("Manca un parametro");
	     
	   else if (gdir.getStatus().code == G_GEO_BAD_KEY)
	     alert("Errore nella Key Api.");

	   else if (gdir.getStatus().code == G_GEO_BAD_REQUEST)
	     alert("La richiesta non puo' essere correttamente risolta.");
	    
	   else alert("Si è verificato un errore");
	   
	}
</script>

<form> <center><input type=button value="Chiudi la finestra" onClick="javascript:window.close();"></center> </form>
<center><div id="map_canvas" style="width: 420px; height: 400px"></div>
<div id="location">
	<form action="#" onsubmit="setDirections(this.partenza.value); return false">
		Punto di consegna:<input type="text" name="partenza" value="<?php

echo ($list[0]);
 for ($i = 1; $i < count($list); $i++) 

{
echo (' to:'.$list[$i]) ;
}
 ?>"><input type="submit" value="Calcola">
	</form>
</div>

<br>
<div id="directions" style="width: 420px"></div>
</center>
</body>

http://s17.postimage.org/obai091cf/prova.jpg
 

Nefyt

Utente Attivo
17 Apr 2012
1.102
0
0
La funzione viene richiamata nel form con il tag onsubmit quindi si che si puo

setDirections(this.partenza.value); return false questa funzione potresti metterla in un altro body onload ad esempio o dove vuoi te

ho notato che l'utente deve inserire solo la via in una textbox allora potresti mettere la funzione
in un onblur= della textbox in modo che l'utente quando ha finito di scrivere parte
 
Ultima modifica:

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Ciao, purtroppo ho provato un pò a fare come dici ma noto che non mi cambia niente, devo sempre premere CALCOLA per avere il percorso...percaso potresti farmi l'esempio modificando il codice che ho allegato alla discussione precedente???
 

Nefyt

Utente Attivo
17 Apr 2012
1.102
0
0
Ciao, purtroppo ho provato un pò a fare come dici ma noto che non mi cambia niente, devo sempre premere CALCOLA per avere il percorso...percaso potresti farmi l'esempio modificando il codice che ho allegato alla discussione precedente???
Un piccolo esempio
PHP:
        Punto di consegna:<input type="text" name="partenza" onblur="setDirections(this.partenza.value); return false" value="<?php 

echo ($list[0]); 
 for ($i = 1; $i < count($list); $i++)  

{ 
echo (' to:'.$list[$i]) ; 
} 
 ?>">
 
Ultima modifica:

vitelli

Utente Attivo
23 Mar 2012
41
0
0
Ciao, ho appena provato il codice da te postato, ma purtroppo la function non si avvia in automatico, ti posto il codice così come l'ho modificato per farti capire.

PHP:
Punto di consegna:<input type="text" name="partenza" onblur="setDirections(this.partenza.value); return false" value="<?php 

echo ($list[0]); 
 for ($i = 1; $i < count($list); $i++)  

{ 
echo (' to:'.$list[$i]) ; 
} 
 ?>">


<center><div id="map_canvas" style="width: 420px; height: 400px"></div>
<div id="location">
 		
</div>

<br>
<div id="directions" style="width: 420px"></div>
</center>
</body>
 

Nefyt

Utente Attivo
17 Apr 2012
1.102
0
0
L'evento onblur si avvia quando l'utente ha finito di scrivere e clicca sulla pagina, sennò potresti usare onfocus e fare partire una funzione che dopo un tot di secondi fa partire quella principale
 

Discussioni simili