Dijkstra Algorithm

Penjelasan

Algoritma dijkstra ditemukan oleh seorag ilmuwan computer berkebangsaan Belanda, bernama Edsger Dijkstra. Algoritma dijkstra ini adalah  algoritma yang digunakan untuk mencari  lintasan  terpendek  pada  sebuah graf berarah maupun tidak. Algoritma Dijkstra merupakan salah satu varian dari algoritma greedy, yaitu salah satu bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi, algoritma greedy ini hanya memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa memikirkan konsekuensi ke depan. Prinsipnya, ambillah apa yang bisa Anda dapatkan saat ini (take what you can get now!), dan keputusan yang telah diambil pada setiap langkah tidak akan bisa diubah kembali. Intinya algoritma greedy ini berupaya membuat pilihan nilai optimum lokal pada setiap langkah dan berharap agar nilai optimum lokal ini mengarah kepada nilai optimum global.

Cara kerja  Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan  simpul yang sudah terpilih dengan simpul lain yang belum terpilih. Algoritma Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan beserta  rutenya.

Pseudocode

• Masukkan banyakRouter (number_of_vertices)


• Masukkan jarak pada masing-masing router dalam matriks atau jarakMatriks[][] (adjacency_matrix[][])


• Untuk i dan j =1 hingga n (banyakRouter)

1. Jika i dan j sama maka jarakMatriks[i][j] = 0, continue;


2. Jika jarakMatriks = 0 maka jarak Matriks=Integer.maxValue;

• for (int i = 1; i <= banyakRouter; i++)

1. node = min(jarak[1, 2,….banyakRouter])  //cari simpul awal minimum yang belum masuk rute fungsi getNodeWithMinimumDistanceFromUnsettled()


2. //cari tetangga dari (evaluateNeighbours)


3. jarakMatriks[node][1….s.d.  banyakRouter]


4. Modifikasi jarak, untuk i = 1, 2, 3, s.d. banyak Router dengan :


5. jarak[j]=min(jarak[j]+jarakMatriks[node][j];)


6. for (int j = 1; j <= banyakRouter; j++)


7. cetak jarak[j]

Source

1. import java.util.*;


2. public class Main {


3.     private int distances[];


4.     private Set<Integer> settled;


5.     private Set<Integer> unsettled;


6.     private int number_of_nodes;


7.     private int adjacencyMatrix[][];


8.      public Main(int number_of_nodes) {


9.          this.number_of_nodes = number_of_nodes;


10.          distances = new int[number_of_nodes + 1];


11.          settled = new HashSet<Integer>();


12.          unsettled = new HashSet<Integer>();


13.          adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];


14.      }


15.      public void dijkstra_algorithm(int adjacency_matrix[][], int source) {


16.          int evaluationNode;


17.          for (int i = 1; i <= number_of_nodes; i++) {


18.              for (int j = 1; j <= number_of_nodes; j++) {


19.                  adjacencyMatrix[i][j] = adjacency_matrix[i][j];


20.              }


21.          }


22.          for (int i = 1; i <= number_of_nodes; i++) {


23.              distances[i] = Integer.MAX_VALUE;


24.          }


25.          unsettled.add(source);


26.          distances[source] = 0;


27.          while (!unsettled.isEmpty()) {


28.              evaluationNode = getNodeWithMinimumDistanceFromUnsettled();


29.              unsettled.remove(evaluationNode);


30.              settled.add(evaluationNode);


31.              evaluateNeighbours(evaluationNode);


32.          }


33.      }


34.    private int getNodeWithMinimumDistanceFromUnsettled() {


35.          int min;


36.          int node = 0;


37.          Iterator<Integer> iterator = unsettled.iterator();


38.          node = iterator.next();


39.          min = distances[node];


40.          for (int i = 1; i <= distances.length; i++) {


41.              if (unsettled.contains(i)) {


42.                  if (distances[i] <= min) {


43.                      min = distances[i];


44.                      node = i;


45.                  }


46.              }


47.          }


48.          return node;


49.      }


50.      private void evaluateNeighbours(int evaluationNode) {


51.          int edgeDistance = -1;


52.          int newDistance = -1;


53.          for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++) {


54.              if (!settled.contains(destinationNode)) {


55.                  if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE) {


56.                      edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];


57.                      newDistance = distances[evaluationNode] + edgeDistance;


58.                      if (newDistance < distances[destinationNode]) {


59.                          distances[destinationNode] = newDistance;


60.                      }


61.                      unsettled.add(destinationNode);


62.                  }


63.              }


64.          }


65.      }


66.      public static void main(String... arg) {


67.          System.out.println(".::Algoritma Dijkstra Dalam Bentuk Matriks::.");


68.          int adjacency_matrix[][];


69.          int number_of_vertices;


70.          Scanner scan = new Scanner(System.in);


71.          try {


72.              System.out.print("Banyak Router\t: ");


73.              number_of_vertices = scan.nextInt();


74.              adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];


75.              System.out.println("Tentukan jarak : ");


76.              System.out.print("   ");


77.              for (int i = 1; i <= number_of_vertices; i++) {


78.                  System.out.print("R" + i + " ");


79.              }


80.              System.out.println("");


81.              for (int i = 1; i <= number_of_vertices; i++) {


82.                  System.out.print("R" + i + " ");


83.                  for (int j = 1; j <= number_of_vertices; j++) {


84.                      adjacency_matrix[i][j] = scan.nextInt();


85.                      if (i == j) {


86.                          adjacency_matrix[i][j] = 0;


87.                          continue;


88.                      }


89.                     if (adjacency_matrix[i][j] == 0) {


90.                         adjacency_matrix[i][j] = Integer.MAX_VALUE;


91.                     }


92.                 }


93.             }


94.             System.out.println("\nHasil :");


95.             System.out.print("   ");


96.             for (int i = 1; i <= number_of_vertices; i++) {


97.                 System.out.print("R" + i + " ");


98.             }


99.             System.out.println("");


100.             for (int i = 0; i < number_of_vertices; i++) {


101.                 Main dijkstrasAlgorithm = new Main(number_of_vertices);


102.                 dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, i + 1);


103.                 System.out.print("R" + (i+1) + " ");


104.                 for (int j = 1; j <= dijkstrasAlgorithm.distances.length - 1; j++) {


105.                     System.out.print(dijkstrasAlgorithm.distances[j] + " ");


106.                 }


107.                 System.out.println("");


108.             }


109.         } catch (InputMismatchException inputMismatch) {


110.             System.out.println("Maaf, Anda salah input!");


111.         }


112.         scan.close();


113.     }


114. }

Output

[caption id="attachment_216" align="aligncenter" width="300" caption="Contoh Output Program Dijkstra"][/caption]

Analisa

Pada program Algoritma Dijkstra diatas, hal pertama kali yang harus kita lakukan adalah  menginputkan matriks jarak antar router setelah kita inputkan semua, proses selanjutnya adalah mencari jarak router satu dengan yang lain pencarian jarak dilakukan dengan cara : pertama dilakukan looping sebanyak router. pada setiap looping dilakukan pemanggilan method dijkstra_algorithm dengan paramter pertama berupa matriks jarak router dan parameter kedua merupakan router tujuan yg akan dicari jarak terdekatnya setelah jarak di temukan, maka hasilnya langsung di tampilkan.

Di dalam method dijkstra_algorihm terjadi proses : pertama matriks yg berisi jarak-jarak antar router tadi isinya di masukkan ke dalam matriks yg lain agar nilai tidak berubah. selanjutnya isi distance dengan Integer.MAX_VALUE sebagai pengganti infinity. Masukkan target ke dalam unsettled sebagai flag bahwa target belum di kunjungi.
lakukan looping selama unsettled tidak kosong. di dalam looping, terjadi pencarian jarak terdekat dengan titik yg berada di dalam unsettled. setelah mendapatkan titip tedekat, remove titik di unsettled yg telah yg ditemukan. masukkan titik tersebut ke dalam settled, kemudian lakukan pencarian node node yg terhubung dengan titik terdekat yang di temukan. ulangi jika memang unsettled belum kosong. jika sudah kosong, maka pencarian selesai.

Download

Untuk download program Algoritma Dijkstra dapat download di sini -> Progam Algoritma Dijkstra Java
Untuk download file PDF dapat download di sini -> Algoritma Dijkstra Java PDF