📄 dijkstra.php
字号:
<?php
/*
djikstra alorithm, shortes path
Rendi Kasigi - 06/199839/EPA/695
http://rkasigi.net
rkasigi@gmail.com
*/
/* the graph array */
$graph['A'] = array('B' => 2, 'D' => 3);
$graph['B'] = array('A' => 2, 'C' => 1, 'E' => 4);
$graph['C'] = array('B' => 1, 'F' => 5);
$graph['D'] = array('A' => 3, 'E' => 2);
$graph['E'] = array('D' => 2, 'B' => 4, 'F' => 1 ,'K' => 15);
$graph['F'] = array('C' => 5, 'E' => 1);
$graph['K'] = array('E' => 15);
function dijkstra($graph, $start , $end = null) {
if($start == $end)
{ return 'node awal dan node akhir tidak boleh sama'; }
elseif(!isset($graph[$start]))
{ return 'node awal tidak terdapat dalam graph yang dimasukan'; }
elseif(!isset($graph[$end]))
{ return 'node akhir tidak terdapat dalam graph yang dimasukan'; }
$posisi = $start;
while (isset($posisi)) {
//menandai bahwa posisi yang sekarang sudah dikunjungi
$dikunjungi[$posisi] = 1;
/*looping pada setiap vertex yang ada diposisi sekarang
lalu menyimpan jarak dan route pada array */
foreach ($graph[$posisi] as $vertex => $distance) {
/* kalo sudah pernah dikunjungi, lewati proses dibawahnya kemudian akses vertex berikutanya */
if (isset($dikunjungi[$vertex]))
continue;
/* jarak dari $posisi ke $vertex */
$dist = (isset($paths[$posisi][0]) ? $paths[$posisi][0] : 0) + $distance;
/* jika belum memiliki path ke $vertex maka dibuat dengan cara
* pilih jarak yang paling pendek antar vertex */
//membuat tree yang menentukan jarak terpendek
$bobot = (isset($tree[$posisi]['bobot']) ? $tree[$posisi]['bobot'] : 0) + $distance;
$tree[$vertex]['bobot'] = $bobot;
$tree[$vertex]['predesesor'] = $posisi;
if (!isset($paths[$vertex]) || ($dist < $paths[$vertex][0])) {
if (isset($paths[$posisi])) {
$paths[$vertex]= $paths[$posisi];
}
$paths[$vertex]['predesessor'] = $posisi;
$paths[$vertex][0] = $dist;
}
}
unset($posisi);
/* mencari node berikutnya yang akan kita kunjungi */
foreach ($paths as $vertex => $path) {
if (isset($dikunjungi[$vertex]))
continue;
$distance = $path[0];
if ((!isset($min) || $distance < $min) || !isset($posisi)) {
$min = $distance;
$posisi = $vertex;
}
}
}
//setelah tree terbentuk baru menampilkan hasil pencarian
$ok = false;
$pos = $end;
$jalur ='';
while(!$ok) {
if(isset($tree[$pos]['predesesor'])) {
$pos = $tree[$pos]['predesesor'];
if($pos == $start)
$jalur = $pos. ''.$jalur;
else
$jalur = '-'.$pos.$jalur;
} else { $ok = true; }
}
return 'Jalur terpendek adalah : '.$jalur.'-'.$end;
}
if(isset($_POST['btnsubmit']))
$result = dijkstra($graph, strtoupper($_POST['node_awal']),strtoupper($_POST['node_akhir']));
?>
<html>
<head>
</head>
<body>
<pre>
B-------C
/ \ 1 \
2 / \ \5
/ \ \
A \4 F G
\ \ /
3 \ \ /1
\ \ /
D-------E-------------- K
2 15
diketahui graph dengan bentuk sebagai berikut.silahkan masukan node awal dan node akhir untuk mencari path terpendek
<hr />
<form method="post" action="" >
node awal : <input type="text" name="node_awal" size="5"/> <br />
node akhir : <input type="text" name="node_akhir" size="5"/>
<input type="submit" value="cari" name="btnsubmit"/>
</form>
<?php
if(isset($result))
echo '<div style="color:red">'.$result.'</div>';
?>
</pre>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -