Algoritma Dijkstra dan Contoh Program

Alogritma Dijkstra dan Contoh Program

Algoritma Dijkstra , merupakan salah satu jenis Algoritma Greedy yang dimana dalam permasalahan memecahkan jarak terpendek(Shortener Path Problem) menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap path-nya(Langkah).Dan Algoritma Dijkstra ditemukan oleh Edger dijkstra

Contoh :

Kita Akan mencari Jalur Terpendek dari A ke G dengan Algoritma Dijkstra.

• Pertama kita Buat Tabel atau Tulisan bebas untuk menandakan bahwa Node Source dan tujuan sudah tercapai atau belum tercapai dengan menuliskan Unvisited(Q) dan Visited(S),Ini hanya untuk memudahkan saja.Selanjutnya buat Kolom A sampai G seperti gambar diatas yang menunjukan keseluruhan Node,Lalu kita buat di baris pertama seperti gambar di atas.Karena Node belum ada yang dikunjungi maka kita tulis di kolom Unvisited {A,B,C,D,E,F,G} dan di kolom A sampai G dengan (takterhingga,-).
  
• Yang kedua kita masukan node pertama atau source nya yaitu A yang disebut Current Node ke kolom Current.Dan Masukan Kolom Unvisited seperti gambar diatas {B,C,D,E,F,G},Serta di kolom Node yang lain dari A sampa G masukan sesuai gambar di atas.Contoh di kolom B tertulis (16,A1) yang artinya node A ke node B berjarak 16 dan A1 artinya adalah A itu dari node pertama yang tervisited.
  
• Pada langkah ketiga ini kita cari jarak paling kecil dari baris nomor 1 terlebih dahulu yaitu di kolom C (9,A1).Lalu masukan C di kolom Current Node.Dan masukan kolom (Q) dan (S) seperti gambar diatas.Visited (A,C) dan Unvisited(B,C,D,E,F,G).A ke B tetap yaitu (16,A1) karena C tidak bisa ke B yang merupakan Current Node dan jaraknya pun tidak diketahui.Lalu di kolom A dan C tidak ditulis lagi karena merupakan Current Node.Selanjutnya D mendapatkan (24,C2) Karena jarak A - C - D adalah 9+15 = 24 dan C2 karena C merupakan Node ke 2 dan lalu mengapa di kolom D tidak (35,A1) karena 24<35 sehingga jalur terpendek yang dibutuhkan yaitu 24.Lalu di kolom E dan G ditulis (Tak terhingga,C2) karena E dan G tidak memiliki jalur langsung ke C.
  
• Lalu Di langkah ketiga kita cari Current Node pada Langkah kedua yaitu yang paling kecil adalah (16,A1) yang masuknya di Kolom B,sehingga B masuk ke Current Node selanjutnya.Unvisited(D,E,F,G) dan visited (A,B,C) dan sekarang Karena Node B hanya bisa ke D dan E maka kita inputkan dulu F dan G yang tidak terhubung.F menjadi (31,C2)Karena 31<Tak Hingga dan G (takTerhingga,B3) Karena takTerhinggaB3<takTerhinggaC2 (Diambil Current Node yang baru yaitu B).Dan kita masuk ke kolom D(24,C2) mengapa 24? karena (24,C2<(28,B3) sehingga tetap (24,C2),Lalu yang E(41,B3) karena 16+25 = 41 dan B ke E hanya ada satu pilihan jalur.

Dan seterusnya sampai kalian visit semua Node dan bertemu angka G seperti gambar di bawah ini

Beberapa Kelebihan dari Algoritma Dijkstra antara lain
1.Algoritma Dijkstra dapat menentukan jalur tercepat dengan waktu yang lebih cepat dibandingkan algoritma lainnya.
2.Menggunakan Algoritma Dijkstra mempermudah kita dalam mengetahui jarak atau lintasan terpendek dari suatu titik tertentu ke semua titik yang lain.
3.Menggunakan Algoritma Dijkstra dalam penerapan di dalam sistem geografis akan menampilakan   visualisasi data dalam bentuk peta
4.Pada penampilan rute atau peta Algoritma Dijkstra lebih mudah di baca dan di pahami.
5.Pada rute atau peta dan lintasannya dapat diberikan warna, sehingga penampilan Algoritma Dijkstra lebih menarik dan lebih mudah untuk membedakan dari suatu titik tertentu ke titik yang lain.

Berikut ini merupakan contoh program dalam Java.

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable
{
    public final String name;
    public Edge[] VertexTetangga;
    public double CekJarak = 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(CekJarak,other.CekJarak);
    }
}

class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

public class AlgoritmaDijkstra
{
    public static void computePaths(Vertex source)
    {
        source.CekJarak = 0;
        PriorityQueue vertexQueue = new PriorityQueue();
      vertexQueue.add(source);
       while (!vertexQueue.isEmpty()) {
           Vertex u = vertexQueue.poll();
            for (Edge e : u.VertexTetangga)
            {
                Vertex v = e.target;
                double weight = e.weight;
                double JarakTerpendek = u.CekJarak + weight;
              if (JarakTerpendek < v.CekJarak) {
                  vertexQueue.remove(v);
                  v.CekJarak = JarakTerpendek ;
                  v.previous = u;
                  vertexQueue.add(v);
              }
            }
        }
    }

    public static List getShortestPathTo(Vertex target)
    {
        List path = new ArrayList<>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args)
    {
       Vertex A = new Vertex("A");
       Vertex B = new Vertex("B");
       Vertex C = new Vertex("C");
       Vertex D = new Vertex("D");
       Vertex E = new Vertex("E");
       Vertex F = new Vertex("F");
       Vertex G = new Vertex("G");

       A.VertexTetangga = new Edge[]{ new Edge(B, 16),
                                    new Edge(C, 9),
                               new Edge(D, 35) };
       B.VertexTetangga = new Edge[]{ new Edge(D, 12),
                                    new Edge(E, 25),
                                    };
       C.VertexTetangga = new Edge[]{ new Edge(D, 15),
                               new Edge(F, 22) };
       D.VertexTetangga = new Edge[]{ new Edge(A, 35),
                                    new Edge(B, 12),
                                    new Edge(C, 15),
                                    new Edge(E, 14),
                                    new Edge(F, 17),
                                    new Edge(G, 19)};
       E.VertexTetangga = new Edge[]{ new Edge(G, 8),
                                   new Edge(B, 25),
                                   new Edge(D, 14),
                                                 };
       F.VertexTetangga = new Edge[]{ new Edge(G, 14),
                                   new Edge(C, 22),
                                   new Edge(D, 17),
                                                  };
       G.VertexTetangga = new Edge[]{ new Edge(F, 14),
                                   new Edge(D, 19),
                                   new Edge(E, 8),
       };
       Vertex[] vertices = { A,B,C,D,E,F,G };
       computePaths(A);
        for (Vertex v : vertices)
       {
           System.out.println("Distance to " + v + ": " + v.CekJarak);
           List path = getShortestPathTo(v);
           System.out.println("Path: " + path);
       }
    }
}

Di bawah ini Output nya :

Impor Java.util.Priorityqueue = Merupakan bentuk Struktur data yang memiliki attribut Heaps,Comparator dan Last.Priorityqueue berfungsi untuk memproses objek dalam antrian berdasarkan prioritas dalam hal ini di Algoritma Dijkstra kita memproses jarak terdekat yang akan menjadi prioritasnya.
import java.util.List = List merupakan jenis Struktur Data Array yang membolehkan adanya value duplikat atau nilai yang sama pada index berbeda.Di dalam list kita dapat menampung bermacam tipe data seperti Integer,String dan lain-lain.Setiap tipe data yang dideklarasi dalam List harus terdapat kata List seperti contoh koding diatas.

Pada List ini berbentuk tipe data ArrayList yang digunakan untuk menampung nilai ke dalam memori.

import.java.util.ArrayList = Tidak jauh dengan array primitif ArrayList lebih dinamis sehingga seberapapun jumlah array yang di masukan kita tidak perlu menambah elemen baru di dalamnya(Array Dinamis).

import.java.util.Collection = Collection merupakan istilah umum yang dipakai untuk setiap objek yang berfungsi untuk mengelompokkan beberapa objek tertentu menggunakan suatu teknik tertentu pula. Semua class yang berhubungan dengan pengelompokan objek ini dalam java tergabung dalam Java Collection Framework, dimana Framework ini diletakan dalam package java.util dan mempunyai dua interface utama, yaitu collection dan map.