Algoritma Dijkstra untuk Pencarian Jalur Terpendek

Telah banyak dibahas mengenai algoritma pencarian jalur terpendek yaitu algoritma semut, dijkstra. Penulis

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

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

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

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