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

No comments:
Post a Comment