alexa-tracking

[ ASK ] Algoritma Dijkstra

Main Content

1024
1024
KASKUS
51
244
https://www.kaskus.co.id/thread/55980501c3cb17492e8b4567/ask--algoritma-dijkstra
[ ASK ] Algoritma Dijkstra
Permisi gan, ane butuh pencerahan.
jadi gini, ane kan buat program dijkstra tentang pencarian jalur terpendek.
nah di program dijkstra ini kan ane cuma menampilkan jalur terpendek yg terseleksi.
nah disini titik permasalahn ane, dosen ane minta dimunculkan beberapa kemungkinan jalur yg dilewati
bisa jalur terpanjangnya atau jalur menengahnya

ane butuh masukannya gan, gimana logikanya, nambah codingan apa.
kalo ada yg bersedia membantu akan ane sertakan codingannya nanti.
maaf berantakan gan, ane ngetik dari hp

mohon bantuannya gan emoticon-Smilie
Code:

class Dijkstra{
private $intStartPoint;
private $aRoutes = array(); // all possible routes between each two points (single direction)
private $aPoints = array(); // all the points on the map
private $aReds = array();
private $aBlues = array();
private $aDistances = array(); // the closest distance from start point to each points
private $aPathes = array(); // path from each points to its neibor on the best path to the start point
private $aFullPathes; // path from start point to each points

/**
* Build Dijkstra model, find best path and closest distance from start point to each point on the map
* @return null
* @param object $intStartPoint
* @param object $aRoutes
*/
public function __construct($intStartPoint,$aRoutes){
$this->aRoutes = $aRoutes;
$this->intStartPoint = $intStartPoint;

foreach($aRoutes as $aRoute){
if(!in_array($aRoute[0],$this->aPoints)){
$this->aPoints[] = $aRoute[0];
}
if(!in_array($aRoute[1],$this->aPoints)){
$this->aPoints[] = $aRoute[1];
}
}

$this->aReds = array($intStartPoint);
$this->aBlues = $this->array_remove($this->aPoints, $intStartPoint);

foreach($this->aBlues as $intPoint){
$this->aDistances[$intPoint] = I;
}
$this->aDistances[$intStartPoint] = 0;

$this->findPath();
}

/**
* function to get the best path
* @return pathes for each node on the map
*/
public function getPath(){
foreach($this->aPoints as $intPoint){
$this->fillFullPath($intPoint,$intPoint);
}
return $this->aFullPathes;
}

/**
* function to get the closest distance
* @return
*/
public function getDistance(){
return $this->aDistances;
}

/**
* Remove specified element from array
* @return array
* @param array $arr : array to be processing
* @param array $value : the element to be remove from the array
*/
private function array_remove($arr,$value) {
return array_values(array_diff($arr,array($value)));
}

/**
* Dijkstra algorithm implementation
* @return null
*/
private function findPath(){
while(!empty($this->aBlues)){
$intShortest = I;
foreach($this->aReds as $intRed){
# find possible rounte
foreach($this->aRoutes as $aRoute){
if($intRed == $aRoute[0]){
$aDis[$intRed][$aRoute[1]] = $aRoute[2];

# rewrite distance
$intDistance = $this->aDistances[$intRed] + $aRoute[2];
if($this->aDistances[$aRoute[1]] > $intDistance){
$this->aDistances[$aRoute[1]] = $intDistance;
# change the path
if($intRed==$this->intStartPoint ||$intRed==$aRoute[1]){}
else{
$this->aPathes[$aRoute[1]] = $intRed;
}
}

# find the nearest neighbor
if(!in_array($aRoute[1],$this->aReds)&&$aRoute[2]<$intShortest){
$intShortest = $aRoute[2];
$intAddPoint = $aRoute[1];
}
}
}
}

$this->aReds[] = $intAddPoint;
$this->aBlues = $this->array_remove($this->aBlues, $intAddPoint);
}
}

/**
* mid step function to find full path from start point to the end point.
* @return null
* @param int $intEndPoint
* @param int $intMidPoint
*/
private function fillFullPath($intEndPoint,$intMidPoint){
if(isset($this->aPathes[$intMidPoint])){
$this->aFullPathes[$intEndPoint][] = $this->aPathes[$intMidPoint];
$this->fillFullPath($intEndPoint,$this->aPathes[$intMidPoint]);
}
else{
$this->aFullPathes[$intEndPoint][] = $this->intStartPoint;
}
}
}

# Examples
// single direction route path
$aRoutes = array(
array(0,0,0),
array(0,1,10),
array(0,3,30), // use something like array(3,0,20) to define a two way map
array(0,4,100),
array(1,1,0),
array(1,2,50),
array(2,2,0),
array(2,4,10),
array(3,3,0),
array(3,2,20),
array(3,4,60),
array(4,4,0),
);
$oDijk = new Dijkstra(0,$aRoutes); // startPoint = 0

print_r($oDijk->getPath());
print_r($oDijk->getDistance());

?>


ini yang agan cari?
Quote:


Itu nampilin kemungkinan 2 jalur ya gan ?

kemungkinan semua jalur untuk 2 titik gan..cuma dia nyari rute terbaik

nah disini agan harus oprek

private $aRoutes = array(); // all possible routes between each two points (single direction)

itu kan array untuk semua kemungkina rute

tinggal di output aja
Quote:


oh oke gan, ane coba dulu yak
tengkyu gan emoticon-Big Grin
sip sama2 gan
Quote:


ini nampilinnya tetep 1 rute terpendeknya doang ya gan? kemungkinannya udah di seleksi di aRoutes nya ya?
iya itu tetap nampilin satu rute tapi itu kan ada gan disitu:

# find the nearest neighbor

if(!in_array($aRoute[1],$this->aReds)&&$aRoute[2]<$intShortest){

$intShortest = $aRoute[2];

$intAddPoint = $aRoute[1];

}

}

}

lihat tanda lebih kecil... itu buat shortest..klo mau terpanjang tinggal reverse engineering aja keknya..

sisanya cari sendiri yaa emoticon-Big Grin