Algoritma Divide and Conquer di Java

Dalam postingan ini, saya akan menerangkan secara sederhana tentan Algoritma Divide and Conquer beserta pengimplementasiannya di Java.

Algoritma Divide and Conquer
Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

Langkah-langkah umum algoritma Divide and Conquer :
Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.

Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif ( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif.

Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.


Contoh Algoritma Divide and Conquer
berikut adalah contoh penerapannya :
Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer, hal ini dapat dipandang
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

• Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
• Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).
• Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.
• Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
• Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung dan mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Pada algoritma di atas, dapat dilihat bahwa terdapat prosedur untuk mencari lower tangen dan upper tangen. Algoritmanya merupakan suatu algoritma berjalan yang biasa. Pada kasus ini, a diinisialisasi sebagai titik paling kanan dari HA dan b merupakan titik paling kiri dari HB. Jika pasangan ab belum merupakan lower tangen untuk HA dan HB , maka “nailkkan” a menjadi suksesor dari a dan “turunkan” b menjadi predesesor dari b, sesuai dengan kaidah arah jarum jam.

Berikut adalah gambaran umum dalam pencarian lower tangen dari HA dan HB : LowerTangen(HA, HB) :

1. Misalkan a merupakan titik terkanan dari HA
2. Misalkan b merupakan titik terkanan dari HB
3. While (ab bukan merupakan lower tangen dari HA dan HB)do - While(ab bukan merupakan lower tangen dari HA) do a -> a.predesesor - While(ab bukan merupakan lower tangen dari HA) do b-> b.suksesor
4. Return ab.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

Contoh kasus

Persoalan : Misalnya diketahui table A yang berukuran n elemen sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut.

Misalkan tabel A berisi elemen-elemen sebagai berikut :

3-10-20-5-17-1-31-2-19

Lalu algoritma melakukan divide seperti berikut :

3-10-20-5 & 17-1-31-2-19

Lalu algoritma melakukan solve seperti berikut :

dari 3-10-19-5 diketahui min=3;maks=20 , dan dari 17-1-31-2-20 diketahui min=1;maks=20.

Setelah melakukan solve, algoritma kemudian menggabungkan kedua data tersebut dan menentukan nilai min dan maks berdasarkan dari kedua data yang didapat, sehingga didapatlah min=1 maks=20.

Ilustrasi dari contoh kasus diatas bisa dilihat seperti gambar dibawah ini :

Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Implementasi di Java

berikut adalah source code bagaimana pengimplementasiannya di Java :

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Random;

public class DivideConquer

{

        public DivideConquer()

        {

                System.out.println("Divide and Conquer: maximum subarray");

               

                System.out.println("Enter number of elements in the array");

                int array_elements = 2;

                try

                {

                        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

                        array_elements = Integer.parseInt(reader.readLine());

                }

                catch (IOException e)

                {

                        e.printStackTrace();

                }

                if (array_elements < 2)

                {

                        System.out.println("Number of elements in the array should be greater or equal 2");

                }

                else

                {

                        Random random = new Random();

                        int[] A = new int[array_elements];

                        for (int i = 0; i < A.length; i++)

                                A[i] = random.nextInt(1000) - 500;

                        System.out.println("Original array");

                        for (int i : A)

                        {

                                System.out.print(String.format("%5d", i));

                        }

                        System.out.println();

                        int[] result =  find_maximum_subarray(A, 0, A.length-1);

                        System.out.println("Maximum sub-array");

                        System.out.println("Low " + result [0]);

                        System.out.println("High " + result [1]);

                        System.out.println("Sum " + result [2]);

                }

        }

       

        private int[] find_maximum_subarray(int[] A, int low, int high)

        {

                if( high == low)

                {

                        int[] result = {low, high, A[low]}; //base case: only one element

                        return result;

                }

                else

                {

                        int mid = (low + high) /2;

                        

                        int[] result1 = find_maximum_subarray (A, low, mid);

                        int[] result2 = find_maximum_subarray (A, mid+1, high);

                        int[] result3 = find_max_crossing_subarray(A, low, mid, high);

                        

                        if( result1[2] >= result2[2] && result1[2] >= result3[2] )

                        {

                                return result1;

                        }

                        else if (result2[2] >= result1[2] && result2[2] >= result3[2])

                        {

                                return result2;

                        }

                        else

                        {

                                return result3;

                        }

                }

        }

       

        private int[] find_max_crossing_subarray(int[] A, int low, int mid, int high)

        {

                int left_sum = Integer.MIN_VALUE;

               

                int sum = 0;

               

                int max_left = -1;

                int max_right = -1;

               

                for(int i = mid; i > low; i--)

                {

                        sum += A[i];

                       

                        if (sum > left_sum)

                        {

                                left_sum = sum;

                                max_left = i;

                        }

                }

               

                int right_sum = Integer.MIN_VALUE;

               

                sum = 0;

               

                for(int j = mid+1; j < high; j++)

                {

                        sum += A[j];

                       

                        if (sum > right_sum)

                        {

                                right_sum = sum;

                                max_left = j;

                        }

                }

               

               

                int[] result =  {max_left, max_right, left_sum + right_sum};

                return result;

        }

}

Semoga membantu. :D

Read More

Algoritma RSA di Java

Dalam postingan ini, saya akan menerangkan secara sederhana tentang Algoritma RSA dan bagaimana implementasinya dalam Java.

RSA
RSA di bidang kriptografi adalah sebuah algoritma pada enkripsi public key. RSA merupakan algoritma pertama yang cocok untuk digital signature seperti halnya ekripsi, dan salah satu yang paling maju dalam bidang kriptografi public key. RSA masih digunakan secara luas dalam commerce electronic protocol, dan dipercaya dalam mengamankan dengan menggunakan kunci yang cukup panjang.

Algoritma RSA pertama dijabarkan pada tahun 1977 oleh tiga orang: Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Hurus RSA itu sendiri berasal dari nama mereka masing-masin (Rivest-Shamir-Adleman).

Algoritma tersebut dipatenkan oleh MIT opada tahun 1983 di Amerika Serikat sebagai U.S. Patent 4.405.829. Paten tersebut berlaku hingga 21 September 2000. Semenjak Algoritma RSA dipublikasikan sebagai aplikasi paten, regulasi di sebagian besar negara-negara lain tidak memungkinkan penggunaan paten.

RSA merupakan terobosan baru dalam sistem enkripsi data karena sebelumnya menge

Contoh ilustrasi Algoritma RSA bekerja.

Semisal Alice berkeinginan untuk mengizinkan Bob untuk mengirimkan kepadanya sebuah pesan pribadi (private message) melalui media transmisi yang tidak aman (insecure). Alice melakukan langkah-langkah berikut untuk membuat pasangan kunci public key dan private key:

Proses pembuatan kunci:

1. Pilih dua bilangan prima p ≠ q secara acak dan terpisah untuk tiap-tiap p dan q. Hitung N = p q. N hasil perkalian dari p dikalikan dengan q.
2. Hitung φ = (p-1)(q-1).
3. Pilih bilangan bulat (integer) antara satu dan φ (1 < e < φ) yang juga merupakan koprima dari φ.
4. Hitung d hingga d e ≡ 1 (mod φ).

• bilangan prima dapat diuji probabilitasnya menggunakan Fermat's little theorem- a^(n-1) mod n = 1 jika n adalah bilangan prima, diuji dengan beberapa nilai a menghasilkan kemungkinan yang tinggi bahwa n ialah bilangan prima. Carmichael numbers (angka-angka Carmichael) dapat melalui pengujian dari seluruh a, tetapi hal ini sangatlah langka.
• langkah 3 dan 4 dapat dihasilkan dengan algoritma extended Euclidean; lihat juga aritmetika modular.
• langkah 4 dapat dihasilkan dengan menemukan integer x sehingga d = (x(p-1)(q-1) + 1)/e menghasilkan bilangan bulat, kemudian menggunakan nilai dari d (mod (p-1)(q-1));
• langkah 2 PKCS#1 v2.1 menggunakan &lamda; = lcm(p-1, q-1) selain daripada φ = (p-1)(q-1)).

Pada public key terdiri atas:

• N, modulus yang digunakan.
• e, eksponen publik (sering juga disebut eksponen enkripsi).

Pada private key terdiri atas:

• N, modulus yang digunakan, digunakan pula pada public key.
• d, eksponen pribadi (sering juga disebut eksponen dekripsi), yang harus dijaga kerahasiaannya.

Biasanya, berbeda dari bentuk private key (termasuk parameter CRT):

• p dan q, bilangan prima dari pembangkitan kunci.
• d mod (p-1) dan d mod (q-1) (dikenal sebagai dmp1 dan dmq1).
• (1/q) mod p (dikenal sebagai iqmp).

Bentuk ini membuat proses dekripsi lebih cepat dan signing menggunakan Chinese Remainder Theorem (CRT). Dalam bentuk ini, seluruh bagian dari private key harus dijaga kerahasiaannya.

Alice mengirimkan public key kepada Bob, dan tetap merahasiakan private key yang digunakan. p dan q sangat sensitif dikarenakan merupakan faktorial dari N, dan membuat perhitungan dari d menghasilkan e. Jika p dan q tidak disimpan dalam bentuk CRT dari private key, maka p dan q telah terhapus bersama nilai-nilai lain dari proses pembangkitan kunci.

Proses enkripsi pesan:
Misalkan Bob ingin mengirim pesan m ke Alice. Bob mengubah m menjadi angka n < N, menggunakan protokol yang sebelumnya telah disepakati dan dikenal sebagai padding scheme.

Maka Bob memiliki n dan mengetahui N dan e, yang telah diumumkan oleh Alice. Bob kemudian menghitung ciphertext c yang terkait pada n:
 c = n^e \mod{N}


Perhitungan tersebut dapat diselesaikan dengan cepat menggunakan metode exponentiation by squaring. Bob kemudian mengirimkan c kepada Alice.

Proses dekripsi pesan:
Alice menerima c dari Bob, dan mengetahui private key yang digunakan oleh Alice sendiri. Alice kemudian memulihkan n dari c dengan langkah-langkah berikut:
n = c^d \mod{N}

Perhitungan di atas akan menghasilkan n, dengan begitu Alice dapat mengembalikan pesan semula m. Prosedur dekripsi bekerja karena
c^d \equiv (n^e)^d \equiv n^{ed} \pmod{N}.

Kemudian, dikarenakan ed ≡ 1 (mod p-1) dan ed ≡ 1 (mod q-1), hasil dari Fermat's little theorem.
n^{ed} \equiv n \pmod{p}

dan
n^{ed} \equiv n \pmod{q}.

Dikarenakan p dan q merupakan bilangan prima yang berbeda, mengaplikasikan Chinese remainder theorem akan menghasilkan dua macam kongruen
n^{ed} \equiv n \pmod{pq}

serta
c^d \equiv n \pmod{N}.

Contoh Prosesnya
Berikut ini merupakan contoh dari enkripsi RSA dan dekripsinya. Parameter yang digunakan disini berupa bilangan kecil.

Kita membuat :

• p = 61 = bilangan prima pertama (harus dijaga kerahasiannya atau dihapus secara hati-hati)
• q = 53 = bilangan prima kedua (harus dijaga kerahasiannya atau dihapus secara hati-hati)
• N = pq = 3233 = modulus (diberikan kepada publik)
• e = 17 = eksponen publik (diberikan kepada publik)
• d = 2753 = eksponen pribadi (dijaga kerahasiannya)

Public key yang digunakan adalah (e,N). Private key yang digunakan adalah d. Fungsi pada enkripsi ialah:

• encrypt(n) = ne mod N = n17 mod 3233

dimana n adalah plaintext Fungsi dekripsi ialah:

• decrypt(c) = cd mod N = c2753 mod 3233

dimana c adalah ciphertext.

Untuk melakukan enkripsi plaintext bernilai "123", perhitungan yang dilakukan:

• encrypt(123) = 12317 mod 3233 = 855

Untuk melakukan dekripsi ciphertext bernilai "855" perhitungan yang dilakukan:

• decrypt(855) = 8552753 mod 3233 = 123

Kedua perhitungan di atas diselesaikan secara effisien menggunakan square-and-multiply algorithm pada modular exponentiation.

Gambar untuk penjelasan proses Algoritma RSA bekerja bisa dilihat dibawah ini :
















Keamanan
Penyerangan yang paling umum pada RSA ialah pada penanganan masalah faktorisasi pada bilangan yang sangat besar. Apabila terdapat faktorisasi metode yang baru dan cepat telah dikembangkan, maka ada kemungkinan untuk membongkar RSA.

Pada tahun 2005, bilangan faktorisasi terbesar yang digunakan secara umum ialah sepanjang 663 bit, menggunakan metode distribusi mutakhir. Kunci RSA pada umumnya sepanjang 1024—2048 bit. Beberapa pakar meyakini bahwa kunci 1024-bit ada kemungkinan dipecahkan pada waktu dekat (hal ini masih dalam perdebatan), tetapi tidak ada seorangpun yang berpendapat kunci 2048-bit akan pecah pada masa depan yang terprediksi.

Semisal Eve, seorang eavesdropper (pencuri dengar—penguping), mendapatkan public key N dan e, dan ciphertext c. Bagimanapun juga, Eve tidak mampu untuk secara langsung memperoleh d yang dijaga kerahasiannya oleh Alice. Masalah untuk menemukan n seperti pada ne=c mod N di kenal sebagai permasalahan RSA.

Cara paling efektif yang ditempuh oleh Eve untuk memperoleh n dari c ialah dengan melakukan faktorisasi N kedalam p dan q, dengan tujuan untuk menghitung (p-1)(q-1) yang dapat menghasilkan d dari e. Tidak ada metode waktu polinomial untuk melakukan faktorisasi pada bilangan bulat berukuran besar di komputer saat ini, tapi hal tersebut pun masih belum terbukti.

Masih belum ada bukti pula bahwa melakukan faktorisasi N adalah satu-satunya cara untuk memperoleh n dari c, tetapi tidak ditemukan adanya metode yang lebih mudah (setidaknya dari sepengetahuan publik).

Bagaimanapun juga, secara umum dianggap bahwa Eve telah kalah jika N berukuran sangat besar.

Jika N sepanjang 256-bit atau lebih pendek, N akan dapat difaktorisasi dalam beberapa jam pada Personal Computer, dengan menggunakan perangkat lunak yang tersedia secara bebas. Jika N sepanjang 512-bit atau lebih pendek, N akan dapat difaktorisasi dalam hitungan ratusan jam seperti pada tahun 1999. Secara teori, perangkat keras bernama TWIRL dan penjelasan dari Shamir dan Tromer pada tahun 2003 mengundang berbagai pertanyaan akan keamanan dari kunci 1024-bit. Santa disarankan bahwa N setidaknya sepanjang 2048-bit.

Pada thaun 1993, Peter Shor menerbitkan Algoritma Shor, menunjukkan bahwa sebuah komputer quantum secara prinsip dapat melakukan faktorisasi dalam waktu polinomial, mengurai RSA dan algoritma lainnya. Bagaimanapun juga, masih terdapat pedebatan dalam pembangunan komputer quantum secara prinsip.

Implementasi di Java
berikut adalah source code pengimplementasiannya di Java:

import java.math.BigInteger;

import java.security.SecureRandom;

public class RSA {

  private BigInteger n, d, e;

  private int bitlen = 1024;

  /** Create an instance that can encrypt using someone elses public key. */

  public RSA(BigInteger newn, BigInteger newe) {

    n = newn;

    e = newe;

  }

  /** Create an instance that can both encrypt and decrypt. */

  public RSA(int bits) {

    bitlen = bits;

    SecureRandom r = new SecureRandom();

    BigInteger p = new BigInteger(bitlen / 2, 100, r);

    BigInteger q = new BigInteger(bitlen / 2, 100, r);

    n = p.multiply(q);

    BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q

        .subtract(BigInteger.ONE));

    e = new BigInteger("3");

    while (m.gcd(e).intValue() > 1) {

      e = e.add(new BigInteger("2"));

    }

    d = e.modInverse(m);

  }

  /** Encrypt the given plaintext message. */

  public synchronized String encrypt(String message) {

    return (new BigInteger(message.getBytes())).modPow(e, n).toString();

  }

  /** Encrypt the given plaintext message. */

  public synchronized BigInteger encrypt(BigInteger message) {

    return message.modPow(e, n);

  }

  /** Decrypt the given ciphertext message. */

  public synchronized String decrypt(String message) {

    return new String((new BigInteger(message)).modPow(d, n).toByteArray());

  }

  /** Decrypt the given ciphertext message. */

  public synchronized BigInteger decrypt(BigInteger message) {

    return message.modPow(d, n);

  }

  /** Generate a new public and private key set. */

  public synchronized void generateKeys() {

    SecureRandom r = new SecureRandom();

    BigInteger p = new BigInteger(bitlen / 2, 100, r);

    BigInteger q = new BigInteger(bitlen / 2, 100, r);

    n = p.multiply(q);

    BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q

        .subtract(BigInteger.ONE));

    e = new BigInteger("3");

    while (m.gcd(e).intValue() > 1) {

      e = e.add(new BigInteger("2"));

    }

    d = e.modInverse(m);

  }

  /** Return the modulus. */

  public synchronized BigInteger getN() {

    return n;

  }

  /** Return the public key. */

  public synchronized BigInteger getE() {

    return e;

  }

  /** Trivial test program. */

  public static void main(String[] args) {

    RSA rsa = new RSA(1024);

    String text1 = "Yellow and Black Border Collies";

    System.out.println("Plaintext: " + text1);

    BigInteger plaintext = new BigInteger(text1.getBytes());

    BigInteger ciphertext = rsa.encrypt(plaintext);

    System.out.println("Ciphertext: " + ciphertext);

    plaintext = rsa.decrypt(ciphertext);

    String text2 = new String(plaintext.toByteArray());

    System.out.println("Plaintext: " + text2);

  }

}

Semoga membantu. :D

Read More

Algoritma Dijkstra di Java

Pada postingan ini, saya akan menerangkan secara sederhana tentang Algoritma Djikstra dan bagaimana implementasi nya di Java.

Algoritma Dijkstra,
(dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus atau greedy algorithm yang dipakai dalam memecahkan permasalahan untuk mencari jarak terpendek dari suatu jalan(shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices (simpul) dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota tersebut.

Input algoritma ini adalah sebuah graf berarah yang berbobot atau bisa disebut array dari beberapa kota (weighted directed graph)/G dan sebuah sumber vertex (puncak)/s dalam G dan V adalah himpunan semua vertices(simpul) dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi : w: E → [0, ∞)
jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.


Biaya (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua puncak, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang puncak s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.


Contoh Algoritma Dijkstra
Untuk bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan, yaitu :

• Beberapa Titik/simpul/daerah, titik/simpul/daerah yang bisa dijangkau secara langsung, dan juga jarak antara mereka.
• Titik/simpul/daerah awal.
• Titik/simpul/daerah tujuan.

Berikut contoh ilustrasi melalui gambar.

Setelah memasukkan array tentang 6 kota(A-F) beserta jaraknya(angka yang tertera di atas garis), algoritma Djikstra akan menghitung jarak terdekat dari suatu kota ke kota yang lain. Contohnya, jika kita ingin berkunjung ke kota F dari kota A maka langkahnya adalah sebagai berikut :

Menentukan waktu tercepat yang bisa ditempuh dari kota tujuan, ke kota terdekat, kota F hanya terhubung langsung ke kota D dan E, dan dari kota F algoritma akan mencari rute terdekat terlebih dahulu, dalam gambar diatas yaitu dari F langsung ke E butuh waktu 3 dan E ke A butuh waktu 5, jadi 3+5=8, dan kalau dari F ke D lalu ke E lalu ke A, 1+1+5=7, jadi algoritma Djikstra akan memilih rute F-D ketimbang F-E, karena itu waktu tercepat dari F ke A.

Setelah posisi sekarang ada di D, algoritma ini akan menghitung kembali seperti langkah pertama, dan karena D hanya terhubung langsung ke C dan E , maka algoritma ini kembali menghitung mana waktu tercepat yang bisa digunakan melalu C atau E untuk menuju kota awal, yaitu A. Di gambar dari D ke C butuh waktu 2, dan dari C ke A butuh waktu 5, berarti 2+5=7, sedangkan dari D ke E lalu ke A, 1+5=6 , jadi algoritma ini akan memilih rute dari D-E daripada D-C.

Setelah posisi sekarang ada di E, algoritma ini akan menghitung kembali seperti langkah pertama, dan kedua dan karena E hanya terhubung langsung ke C dan A , maka algoritma ini kembali menghitung mana waktu tercepat yang bisa digunakan melalu C atau langsung ke A untuk menuju kota awal, yaitu A. Di gambar, dari E ke C butuh waktu 1, dan dari C ke A butuh waktu 5, berarti 1+5=7, sedangkan dari E langsung ke A, butuh waktu hanya 5 , jadi algoritma ini akan tidak akan memilih rute E-C-A, dia akan memilih dari E langsung ke A karena itu lebih cepat.

Dan begitulah sekilas ilustrasi bagaimana Alogritma Dijkstra bekerja, sangat membantu dalam proses navigasi atau semacamnya.

Implementasi Algoritma Dijkstra dalam Java

dan berikut adalah source code untuk mengimplementasikannya dalam Java :

import java.util.PriorityQueue;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

class Vertex implements Comparable<Vertex>

{

    public final String name;

    public Edge[] adjacencies;

    public double minDistance = Double.POSITIVE_INFINITY;

    public Vertex previous;

    public Vertex(String argName) { name = argName; }

    public String toString() { return name; }

    public int compareTo(Vertex other)

    {

        return Double.compare(minDistance, other.minDistance);

    }

}

class Edge

{

    public final Vertex target;

    public final double weight;

    public Edge(Vertex argTarget, double argWeight)

    { target = argTarget; weight = argWeight; }

}

public class Dijkstra

{

    public static void computePaths(Vertex source)

    {

        source.minDistance = 0.;

        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();

      vertexQueue.add(source);

       while (!vertexQueue.isEmpty()) {

           Vertex u = vertexQueue.poll();

            // Visit each edge exiting u

            for (Edge e : u.adjacencies)

            {

                Vertex v = e.target;

                double weight = e.weight;

                double distanceThroughU = u.minDistance + weight;

              if (distanceThroughU < v.minDistance) {

                  vertexQueue.remove(v);

                  v.minDistance = distanceThroughU ;

                  v.previous = u;

                  vertexQueue.add(v);

              }

            }

        }

    }

    public static List<Vertex> getShortestPathTo(Vertex target)

    {

        List<Vertex> path = new ArrayList<Vertex>();

        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)

            path.add(vertex);

        Collections.reverse(path);

        return path;

    }

    public static void main(String[] args)

    {

       Vertex v0 = new Vertex("Redvile");

       Vertex v1 = new Vertex("Blueville");

       Vertex v2 = new Vertex("Greenville");

       Vertex v3 = new Vertex("Orangeville");

       Vertex v4 = new Vertex("Purpleville");

       v0.adjacencies = new Edge[]{ new Edge(v1, 5),

                                    new Edge(v2, 10),

                               new Edge(v3, 8) };

       v1.adjacencies = new Edge[]{ new Edge(v0, 5),

                                    new Edge(v2, 3),

                                    new Edge(v4, 7) };

       v2.adjacencies = new Edge[]{ new Edge(v0, 10),

                               new Edge(v1, 3) };

       v3.adjacencies = new Edge[]{ new Edge(v0, 8),

                                    new Edge(v4, 2) };

       v4.adjacencies = new Edge[]{ new Edge(v1, 7),

                               new Edge(v3, 2) };

       Vertex[] vertices = { v0, v1, v2, v3, v4 };

        computePaths(v0);

        for (Vertex v : vertices)

       {

           System.out.println("Distance to " + v + ": " + v.minDistance);

           List<Vertex> path = getShortestPathTo(v);

           System.out.println("Path: " + path);

       }

    }

}

Semoga dapat membantu. :D

Read More