Read 189 times | Created 2013-07-16 02:07:33 | Updated 2013-07-16 03:58:31 | | |

 

<?php

/******************************** 
/ DIJKSTRA SHORTEST PATH
/ FILENAME     : dijkstra.php 
/ UPDATED BY   : CAHYA DSN 
/ CREATED DATE : 2013-07-16 
/*******************************
--
-- Database: `test`
--
-- Table structure for table `jarak`
--
DROP TABLE IF EXISTS `jarak`;
CREATE TABLE IF NOT EXISTS `jarak` (
  `id_jarak` int(5) NOT NULL AUTO_INCREMENT,
  `asal` int(4) NOT NULL,
  `tujuan` int(4) NOT NULL,
  `jarak` int(4) NOT NULL,
  PRIMARY KEY (`id_jarak`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;
--
-- Dumping data for table `jarak`
--
INSERT INTO `jarak` (`id_jarak`, `asal`, `tujuan`, `jarak`) VALUES
(1, 1, 2, 700),
(2, 1, 10, 750),
(3, 2, 1, 700),
(4, 2, 3, 950),
(5, 3, 2, 950),
(6, 3, 4, 800),
(7, 4, 3, 700),
(8, 4, 6, 1020),
(9, 5, 4, 1000),
(10, 5, 6, 20),
(11, 6, 7, 50),
(12, 6, 15, 800),
(13, 7, 8, 20),
(14, 7, 11, 650),
(15, 8, 7, 20),
(16, 8, 9, 10),
(17, 9, 2, 850),
(18, 9, 5, 20),
(19, 10, 8, 650),
(20, 10, 13, 50),
(21, 11, 13, 20),
(22, 12, 1, 750),
(23, 12, 10, 20),
(24, 12, 13, 20),
(25, 13, 12, 1000),
(26, 13, 14, 600),
(27, 14, 12, 600),
(28, 14, 23, 1800),
(29, 15, 6, 800),
(30, 15, 40, 1100),
(31, 16, 4, 1100),
(32, 16, 17, 1000),
(33, 17, 16, 1000),
(34, 17, 19, 1000),
(35, 17, 31, 750),
(36, 18, 17, 1000),
(37, 18, 19, 400),
(38, 19, 22, 20),
(39, 19, 41, 10),
(40, 19, 42, 50),
(41, 20, 15, 1000),
(42, 20, 40, 900),
(43, 21, 18, 20),
(44, 21, 41, 50),
(45, 21, 42, 10),
(46, 22, 21, 400),
(47, 22, 24, 1300),
(48, 23, 14, 1800),
(49, 23, 20, 1200),
(50, 23, 24, 270),
(51, 24, 21, 1300),
(52, 24, 23, 700),
(53, 24, 25, 240),
(54, 25, 24, 240),
(55, 25, 26, 300),
(56, 25, 28, 1600),
(57, 26, 25, 300),
(58, 26, 36, 3300),
(59, 27, 28, 50),
(60, 27, 29, 950),
(61, 27, 43, 400),
(62, 28, 27, 50),
(63, 28, 34, 240),
(64, 29, 27, 950),
(65, 29, 33, 550),
(66, 30, 17, 700),
(67, 30, 31, 50),
(68, 31, 32, 50),
(69, 31, 37, 800),
(70, 32, 30, 50),
(71, 32, 33, 50),
(72, 32, 39, 100),
(73, 33, 29, 550),
(74, 33, 30, 50),
(75, 33, 34, 1200),
(76, 34, 28, 240),
(77, 34, 33, 1200),
(78, 34, 35, 200),
(79, 34, 26, 1700),
(80, 35, 34, 200),
(81, 35, 36, 1200),
(82, 36, 26, 3300),
(83, 36, 35, 1200),
(84, 36, 38, 2300),
(85, 37, 31, 700),
(86, 37, 38, 750),
(87, 38, 36, 2200),
(88, 38, 37, 600),
(89, 39, 32, 100),
(90, 40, 18, 10),
(91, 40, 22, 50),
(92, 40, 41, 20),
(93, 41, 27, 400),
(94, 42, 20, 100),
(95, 43, 18, 50),
(96, 43, 22, 10),
(97, 43, 22, 20);
-- --------------------------------------------------------
--
-- Table structure for table `kota`
--
DROP TABLE IF EXISTS `kota`;
CREATE TABLE IF NOT EXISTS `kota` (
  `id_kota` int(4) NOT NULL AUTO_INCREMENT,
  `kota` varchar(4) NOT NULL,
  PRIMARY KEY (`id_kota`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 ;
--
-- Dumping data for table `kota`
--
INSERT INTO `kota` (`id_kota`, `kota`) VALUES
(1, 'A'),
(2, 'B'),
(3, 'C'),
(4, 'D'),
(5, 'E'),
(6, 'F'),
(7, 'G'),
(8, 'H'),
(9, 'I'),
(10, 'J'),
(11, 'K'),
(12, 'L'),
(13, 'M'),
(14, 'N'),
(15, 'O'),
(16, 'P'),
(17, 'Q'),
(18, 'R'),
(19, 'S'),
(20, 'T'),
(21, 'U'),
(22, 'V'),
(23, 'W'),
(24, 'X'),
(25, 'Y'),
(26, 'Z'),
(27, 'AA'),
(28, 'AB'),
(29, 'AC'),
(30, 'AD'),
(31, 'AE'),
(32, 'AF'),
(33, 'AG'),
(34, 'AH'),
(35, 'AI'),
(36, 'AJ'),
(37, 'AK'),
(38, 'AL'),
(39, 'AM'),
(40, 'AN'),
(41, 'AO'),
(42, 'AQ'),
(43, 'AR');
-- -----------------------------
*/

function dijkstra($graph_array, $source, $target) {
  $vertices = array();
  $neighbours = array();
  foreach ($graph_array as $edge) {
    array_push($vertices, $edge[0], $edge[1]);
    $neighbours[$edge[0]][] = array("end" => $edge[1], "cost" => $edge[2]);
  }
  $vertices = array_unique($vertices);
  foreach ($vertices as $vertex) {
    $dist[$vertex] = INF;
    $previous[$vertex] = NULL;
  }
  $dist[$source] = 0;
  $Q = $vertices;
  while (count($Q) > 0) {
    $min = INF;
    foreach ($Q as $vertex){
      if ($dist[$vertex] < $min) {
        $min = $dist[$vertex];
        $u = $vertex;
      }
    }
    $Q = array_diff($Q, array($u));
    if ($dist[$u] == INF or $u == $target) {
      break;
    }
    if (isset($neighbours[$u])) {
      foreach ($neighbours[$u] as $arr) {
        $alt = $dist[$u] + $arr["cost"];
        if ($alt < $dist[$arr["end"]]) {
          $dist[$arr["end"]] = $alt;
          $previous[$arr["end"]] = $u;
        }
      }
    }
  }
  $path = array();
  $u = $target;
  while (isset($previous[$u])) {
    array_unshift($path, $u);
    $u = $previous[$u];
  }
  array_unshift($path, $u);
  $distance=0;
  $num_path=count($path);
  $i=0;
  while(++$i<$num_path)
  {
    foreach($graph_array as $dist_array){
      if($dist_array[0]==$path[$i-1] && $dist_array[1]==$path[$i])
      {
        $distance+=$dist_array[2];
        break 1;
      }
    }
  }
  return array($path,$distance);
}
//-- database configuration
$dbhost='localhost';
$dbuser='root';
$dbpass='';
$dbname='test';
//-- database connection
$db=new mysqli($dbhost,$dbuser,$dbpass,$dbname);
$city_node=array();
if($result=$db->query('SELECT * FROM kota'))
{
  while($row=$result->fetch_object())
  {
    $city_node[$row->id_kota]=$row->kota;
  }
}
?>
<!DOCTYPE hmtl>
<html>
  <head>
    <title>Dijkstra</title>
  </head>
  <body>
    <div class='container'>
      <form method='POST'>
        <label>FROM</label>
        <select name='from_city'>
          <option>--select one--</option>
          <?php 
          foreach($city_node as $key=>$value)
          {
            echo "<option value='{$key}'"
                  .(isset($_POST['from_city'])?
                   ($key==$_POST['from_city']?' selected="selected"':''):'')
                  .">{$value}</option>n";
          }
          ?>
        </select>
        <label>TO</label>
        <select name='to_city'>
          <option>--select one--</option>
          <?php 
          foreach($city_node as $key=>$value)
          {
            echo "<option value='{$key}'"
                  .(isset($_POST['to_city'])?
                   ($key==$_POST['to_city']?' selected="selected"':''):'')
                  .">{$value}</option>n";
          }
          ?>
        </select>
        <input type='submit' name='submit' value='DISTANCE'/>
      </form>
      <div class='result'>
      <?php
      if(isset($_POST['submit'])){
        $result->free();
        if($result=$db->query('SELECT asal,tujuan,jarak FROM jarak'))
        {
          $graph_array=array();
          while($row=$result->fetch_object())
          {
            $graph_array[]=array($row->asal,$row->tujuan,$row->jarak);
          }
          list($path,$distance) = dijkstra($graph_array, $_POST['from_city'], $_POST['to_city']);
          $paths=array();
          foreach($path as $node) $paths[]=$city_node[$node];
          echo "Rute terdekatnya adalah: <b>".implode(" - ", $paths)."</b><br/>n"
              ."Dengan total jarak sejauh: <b>".$distance."</b>n";
        }
      }
      ?>
      </div>
    <div>
  </body>
</html>