Djikstra Algoritma , Desain Analisis algoritma

3

May 23, 2013 by Prima

Cerita bentar saya itu dapet nilai E pada Desain analisis dan algoritma jadi saya ngulang semester ini . nah dapet deh tugas suruh buat program yang mengaplikasikan algoritma djikstra dan perkalian matriks. dimana nilai nilai matriks jarak u ke v pada program djikstra dan nilai2 elemen pada program matriks adalah random integer.

oke kita mulai dengan program djikstra
djikstra adalah algoritma yang ditemukan  Edsger Dijkstra . yaitu algoritma rakus atau (greedy algorhitm) < mbuh tulisane bener po ra hahha… yang digunakan untuk mencari masalah jarak terpendek (shotest path problem)

oke anda bisa belajar dari youtube gimana jalanya algoritma djikstra atau baca disini udah ada pseudocode nya .. http://id.wikipedia.org/wiki/Algoritma_Dijkstra

oke saya mau mengaplikasikan pseudocode yang ada . sayangnya saya gak ngerti artinya jadi saya bikin sendiri programnya berdasarkan logika dari algoritma djikstra

pertama saya buat matriks atau array 2 dimensi dimana itu merupakan vertex2 pada graph misal path[0][1] adalah jarak dari vertex 0 ke 1 dan seterusnya tergantung jumlah vertex. setelah itu dengan algoritma djikstra dihitung semua jarak terpendek dari 0 ke 1, dari 0 ke 2 dan seterusnya tergantung jumlah vertex dengan mengganti bobot setiap vertex jika ada path yang baru yang lebih pendek jaraknya

oke ini programnya . jalan sih dan berhasil dan sudah sesuai dengan algoritmanya alhamdulillah walau agak mubeng dan dikerjakan dengan sangat terpaksa (coding satu malam oh indahnya -_-)

ini saya membuat file DjikstraMatriksClass.php yang isinya class untuk algoritma djikstra dan matriks disini saya tampilkan untuk class djikstra saja monggo disimak

<?php

/*
class ini dibuat dalam rangka tuas Desain Analisis Algoritma oleh
Prima Adi Pradana | M0509056 yaitu untuk algoritma djikstra dan perkalian matriks
*/

class djikstra {

    var $matriks = array();
    var $start;
    var $end;
    var $jumver;

    function __construct($matriks, $start, $end, $jumver) {
        $this->matriks = $matriks;
        $this->start = $start;
        $this->end = $end;
        $this->jumver = $jumver;
    }

    function jarak_terpendek() {
        $matriks = $this->matriks;
        $start = $this->start;
        $end = $this->end;
        $panjangm = $this->jumver;
        $wfix = array_fill(0, $panjangm + 1, 0);

        echo "<table border='2px'><tr>";
        for ($i = 0; $i <= 0; $i++) {

            for ($j = 0; $j <= $panjangm; $j++) {
                echo "<td id='angka' colspan='2' align='center'>" . $j . "</td>";
            }
        }
        echo "</tr>";
        echo "<tr>";
        for ($i = 0; $i <= 0; $i++) {
            echo "<br>";
            for ($j = 0; $j <= $panjangm; $j++) {

                $w[$j] = $wfix[$i] + $matriks[$i][$j];
                $wfix[$j] = $w[$j];
                echo "<td>=" . $i . "->" . $j . "=</td>";
                echo "<td id='angka'>" . $wfix[$j] . "</td>";
            }
        }
        echo "</tr>";

        for ($i = 1; $i <= $panjangm; $i++) {
            echo "<br><tr>";
            for ($j = 0; $j <= $panjangm; $j++) {

                $w[$j] = $wfix[$i] + $matriks[$i][$j];

                if ($w[$j] > $wfix[$j]) {
                    $wfix[$j] = $wfix[$j];
                    echo "<td>=takberubah=</td>";
                } else if ($w[$j] <= $wfix[$j]) {
                    $wfix[$j] = $w[$j];

                    if ($i == $j)
                        echo "<td>=0->" . $j . "=</td>";
                    else
                        echo "<td>=0->" . $i . "->" . $j . "=</td>";
                }
                echo "<td id='angka'>" . $wfix[$j] . "</td>";
            }
        }
    }

}

disini dituliskan fungsi jarak terpendek jika fungsi itu dijalankan maka akan langsung keluar output pengurutan pencarian jarak terpendek jika gak ngerti tapi pengen ngerti bisa komen disini buat yang matriks bisa dilihat disini plus link downloadnya.

https://prima0009.wordpress.com/2013/05/23/matriks-dan-perkalian-antar-matriks-tugas-kuliah-daa/

3 thoughts on “Djikstra Algoritma , Desain Analisis algoritma

  1. […] untuk yang program djikstra bisa dilihat disini https://prima0009.wordpress.com/2013/05/23/djikstra-algoritma-desain-analisis-algoritma/ […]

  2. aufa says:

    Romoo …you’re awesome !😀

  3. […] untuk yang program djikstra bisa dilihat disini https://prima0009.wordpress.com/2013/05/23/djikstra-algoritma-desain-analisis-algoritma/ […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: