Sabtu, 01 Agustus 2015

Algoritma Dijkstra untuk Pencarian Jalur Terpendek



Telah banyak dibahas mengenai algoritma pencarian jalur terpendek yaitu algoritma semut, dijkstra. Penulis
Penulis mempunyai gambaran kasus diatas untuk mencari solusi tercepat (menggunakan teknik algoritma greedy) yaitu dijkstra sebagai visualisasi sebagai berikut







Hal utama perlu diketahui pada kasus diatas, kita akan mendapati tentang teori graph yang terdiri dari vertex dan node
Vertex – simpul yang menandakan tempat/kota
Sedangkan node – garis yang menandakan sebuah jalan
Vertex dihubungkan oleh node yang mempunyai bobot atau disebut jarak.
G(node, vertex1, vertex2, jarak)
Misalkan diatas
G(‘jl. Eri’, 0, 2, 4)
Kamu bisa baca algoritma dan melihat source code di



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class UjiAlgoritmaDijkstra 
{
  
  public static void main (String []args)
  {
      UjiAlgoritmaDijkstra test = new UjiAlgoritmaDijkstra();
      test.hitung();
  }  
  public void hitung() 
  {
    daftarKota = new ArrayList<Vertex>();
    daftarJalan = new ArrayList<Edge>();
    String [] name = new String[]{"kota 0","kota 1","kota 2","kota 3","kota 4","kota 5"};
    for (int i = 0; i < name.length; i++) 
    {
      Vertex kota = new Vertex(name[i],name[i]);
      daftarKota.add(kota);
    }
    
    tamhahkanJalanPenghubung("jl agus", 0,1,13);
    tamhahkanJalanPenghubung("jl budi", 1,3,6);
    tamhahkanJalanPenghubung("jl cinta", 3,5,5);
    tamhahkanJalanPenghubung("jl dodi", 1,2,2);    
    tamhahkanJalanPenghubung("jl eri", 0,2,4);
    tamhahkanJalanPenghubung("jl farhan", 2,4,1);
    tamhahkanJalanPenghubung("jl gigi", 4,3,5);
    tamhahkanJalanPenghubung("jl halim", 4,5,13);
    
    
    Graph graph = new Graph(daftarKota, daftarJalan);
    Dijkstra dijkstra = new Dijkstra(graph);
    dijkstra.execute(daftarKota.get(0));    
    LinkedList<Vertex> path = dijkstra.getPath(daftarKota.get(name.length-1));    
    
    
    for (Vertex vertex : path) {
      System.out.println(vertex);
    }
    
  }

  private void tamhahkanJalanPenghubung(String namaJalan, int kotaAsal, int kotaTujuan,int jarak) {
    Edge lane = new Edge(namaJalan,daftarKota.get(kotaAsal), daftarKota.get(kotaTujuan), jarak);
    daftarJalan.add(lane);
  }
  private List<Vertex> daftarKota;
  private List<Edge> daftarJalan;
}


       
 




Menghasilkan








Posting Komentar