Contoh Algoritma mencari Jalur Terpendek menggunakan PHP

- April 04, 2013

Selamat berjumpa kembali pengunjung setia, berawal dari iseng dan rasa penasaran untuk mengimplementasikan teory yang diberikan di pascasarjana, saya mencoba membuat sedikit simulasi dengan bahasa pemrograman PHP untuk mencari jalur terpendek. Lihat soal di bawah ini :

dari soal diatas kita tentukan dulu awal keberangkatan dan tujuan kita. Contoh kali ini kita akan berangkat dari Las Vegas ke Sacramento.
Buatlah variabel nya :
Jalur 0 : (Las Vegas -> Reno -> Sacramento) nilai ( 445, 133)
Jalur 1 : (Las Vegas -> Bakersfield -> Sacramento ) nilai (291, 271)
Jalur 2 : (Las Vegas -> Los Angeles -> Bakersfield -> Sacramento ) nilai (275, 112, 271)
Jalur 3 : (Las Vegas -> Los Angeles -> San Francisco -> Sacramento ) nilai (275, 409, 95)

sebenarnya kita masih dapat melakukan penambahan jalur yang lain, tapi kali ini kita coba ke empat jalur diatas sebagai variabelnya, baiklah kita langsng ke pembuatan kode program menggunakan PHP

array(455,133,0),
     "jalur1"=>array(291,271,0),
     "jalur2"=>array(275,112,271),
     "jalur3"=>array(275,404,95)
    );
$z=0;
foreach($jalur as $item=>$value) {
 $hasil = $item." [ ";
 $tmp=0;
 foreach($value as $jalur=>$isi) {
  $hasil .=$isi." ";
  $tmp = $tmp+ $isi;
 }
 echo $hasil." ] => ".$tmp." 
";
 $angka[$z] = $tmp;
 $z++;
}
echo '
';
$jml = count($angka)-1;
for($i=0;$i<=$jml;$i++){
 echo " Jalur ke ".$i." = ".$angka[$i]." 
"; 
}
for($a=0;$a<=$jml;$a++){
 for($b=$a;$b<=$jml;$b++){
  if($angka[$b]<$angka[$a]) {
   $tmp = $angka[$b];
   $angka[$b] = $angka[$a];
   $angka[$a] = $tmp; 
  }
 }
}
echo "
 Jarak Terdeket ".$angka[0]."";
?>

Hasilnya adalah :
jalur0 [ 455 133 0 ] => 588
jalur1 [ 291 271 0 ] => 562
jalur2 [ 275 112 271 ] => 658
jalur3 [ 275 404 95 ] => 774
Jalur ke 0 = 588
Jalur ke 1 = 562
Jalur ke 2 = 658
Jalur ke 3 = 774
Jarak Terdeket 562 (Jalur ke 1)
Nah mudah sekali bukan, silahkan mencobanya dan pastikan dengan kasus yang lain apakah algoritma ini cukup efektif atau Anda memiliki algoritma tersendiri.