Algoritma Dijkstra

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);

       }

    }

}