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…