Perncarian Jalur Terpendek berbasis java dengan metode Djikstra

to The Point…

membuat 4 class yaitu sebagai berikut :

==============================================
Class 1 :
==============================================
class DistPar // jarak (distance) dan induk (parent).
{ // item-item tersimpan di array sPath.
public int distance; // jarak dari start ke vertex ini.
public int parentVert; // induk (parent) vertex saat ini.
public DistPar(int pv, int d) // constructor
{
distance = d;
parentVert = pv;
}
} // end class DistPar

==============================================
Class 2 :
==============================================
class Vertex {

public char label; // label (misalnya : ‘A’)
public boolean isInTree;
// ————————————————————
public Vertex(char lab) // constructor
{
label = lab;
isInTree = false;
}
// ————————————————————
} // end class Vertex

==============================================
Class 3 :
==============================================
class Graph {

private final int MAX_VERTS = 6;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // Daftar vertex-vertex.
private int adjMat[][]; // adjacency matrix
private int nVerts; // jumlah vertex saat ini.
private int nTree; // jumlah verts di tree.
// array untuk data lintasan terpendek
// (shortest-path)
private DistPar sPath[];
private int currentVert; // vertex saat ini.
private int startToCurrent; // jarak ke currentVert.

// ————————————————————
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
nTree = 0;
// menginisialisasi adjacency matrix
// ke infinity.
for (int j = 0; j < MAX_VERTS; j++) {
for (int k = 0; k < MAX_VERTS; k++) // Lintasan terpendek (shortest path).
{
adjMat[j][k] = INFINITY;
}
}
sPath = new DistPar[MAX_VERTS];
} // end constructor

// ————————————————————
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}

// ————————————————————
public void addEdge(int start, int end, int weight) {
adjMat[start][end] = weight; // (berarah)
}

// ————————————————————
// Menemukan semua lintasan terpendek
// (shortest path).
public void path() {
int startTree = 0; // mulai dari vertex 0
vertexList[startTree].isInTree = true;
nTree = 1; // letakkan di tree
// transfer baris-baris (distances) dari
// adjMat ke sPath.
for (int j = 0; j < nVerts; j++) {
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
// hingga semua vertex ada di tree.
while (nTree < nVerts) {
// mendapat nilai minimum dari sPath.
int indexMin = getMin();
int minDist = sPath[indexMin].distance;
if (minDist == INFINITY) // jika semua infinite
{ // atau ada di tree,
System.out.println("Simpul (vertex) tidak dapat dicapai! ");
break; // sPath selesai.
} else { // melakukan pengaturan-ulang currentVert.
currentVert = indexMin; // ke vert terdekat.
startToCurrent = sPath[indexMin].distance;
// jarak minimum dari startTree adalah
// ke currentVert, dan startToCurrent.
}
// Letakkan vertex saat ini ke tree.
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath(); // perbaharui array sPath[].
} // end while(nTree<nVerts)
displayPaths(); // tampilkan isi sPath[]
nTree = 0; // hapus tree.
for (int j = 0; j < nVerts; j++) {
vertexList[j].isInTree = false;
}
} // end path()

// ————————————————————
public int getMin() // mendapatkan entry dari sPath
{ // yang memiliki jarak minimum.
int minDist = INFINITY; // asumsikan minimum.
int indexMin = 0;
for (int j = 1; j < nVerts; j++) // untuk setiap vertex,
{ // jika ada di tree dan
if (!vertexList[j].isInTree && // lebih kecil dari yang lama.
sPath[j].distance < minDist) {
minDist = sPath[j].distance;
indexMin = j; // update minimum
}
} // end for
return indexMin; // mengembalikan index minimum
} // end getMin()

// ————————————————————
public void adjust_sPath() {
// mengatur nilai-nilai dalam array sPath
// yang berisi lintasan terpendek.
int column = 1; // lompati vertex awal.
while (column < nVerts) // melintas kolom.
{
// jika kolom vertex ada di tree, lompati.
if (vertexList[column].isInTree) {
column++;
continue;
}
// hitung jarak dari suatu entry sPath,
// dapatkan lintasan (edge) dari currentVert ke kolom.
int currentToFringe = adjMat[currentVert][column];
// tambahkan jarak dari start
int startToFringe = startToCurrent + currentToFringe;
// dapatkan jarak (distance) entri sPath saat ini.
int sPathDist = sPath[column].distance;
// bandingkan jarak (distance) dari
// start dengan entri sPath.
if (startToFringe < sPathDist) // jika lebih pendek,
{ // perbaharui sPath
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
} // end adjust_sPath()

// ————————————————————
public void displayPaths() {
// Menampilkan isi array sPath.
for (int j = 0; j < nVerts; j++) {
System.out.print(vertexList[j].label + "="); // B=
if (sPath[j].distance == INFINITY) {
System.out.print("inf"); // inf
} else {
System.out.print(sPath[j].distance); // 50
}
char parent = vertexList[sPath[j].parentVert].label;
System.out.print("(" + parent + ") "); // (A)
}
System.out.println("");
}
// ————————————————————
} // end class Graph

==============================================
Class 4 :
==============================================
class PathApp {

public static void main(String[] args) {
Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0 (start)
theGraph.addVertex('C'); // 2
theGraph.addVertex('B'); // 1
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 1, 50); // AB 50
theGraph.addEdge(0, 3, 80); // AD 80
theGraph.addEdge(1, 2, 60); // BC 60
theGraph.addEdge(1, 3, 90); // BD 90
theGraph.addEdge(2, 4, 40); // CE 40
theGraph.addEdge(3, 2, 20); // DC 20
theGraph.addEdge(3, 4, 70); // DE 70
theGraph.addEdge(4, 1, 50); // EB 50

System.out.println("Shortest paths");
theGraph.path(); // shortest paths
System.out.println();
} // end main()
} // end class PathApp
=================================================================================

silakan dipelajari lagi ya, cuz saya juga lagi belajar ini.. besok kalau saya sudah mempelajarinya saya akan tuliskan penjelasan lebih lengkapnya.. GoodLuck…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: