Minggu, 07 Oktober 2012

Menentukan Rute Terdekat Menggunakan Djikstra’s Algorithm

Shortest path finder adalah metoda berupa algoritma yang digunakan untuk mencari rute terdekat. Ada banyak algoritma yang bisa digunakan. Dua algoritma yang paling poluler adalah Djikstra dan A* (baca: A star). Walaupun sama-sama bisa digunakan untuk mencari rute terdekat, namun keduanya memiliki prinsip yang berbeda.

Hal itu menyebabkan keduanya digunakan pada jenis kasus yang bebeda pula. Bahasan kali ini akan difokuskan pada algoritma djikstra. A* insya allah akan dibahas pada tulisan yang akan datang. Algoritma djikstra diperkenalkan pertama kali oleh Edsger Dijkstra, seorang ilmuan komputer berkebangsaan Belanda pada tahun 1959. Algoritma ini menjadi tulang punggung dari link-state routing. Link-state routing adalah satu dari dua kelas utama dari routing protocol yang digunakan pada packet switching networks dalam dunia komunikasi komputer (computer communications).

Agar bisa menentukan rute terdekat, djikstra memerlukan informasi berupa sebuah routing table. Routing table ini berisi kumpulan informasi simpul (vertex/node) dalam bentuk tabular. Sekumpulan simpul/nodes/vertex Perhatikan gambar di samping. A, B, C, D, E, dan F adalah simpul atau node atau vertex. Dari gambar terlihat bahwa simpul-simpul tersebut saling terhubung satu sama lain sedemikian sehingga membentuk rute. Bayangkan simpul tersebut adalah sebuah kota yang satu dengan lainnya dihubungkan oleh jalan. Maka untuk pergi ke kota F, seseorang yang berada di kota A sedikitnya bisa menempuh dua rute perjalanan yang berbeda, yaitu A → B → D → E → F dan A → C → F. Agar bisa sampai di kota F, tentunya orang yang melakukan perjalanan tersebut harus mempunyai informasi ke kota mana saja masing-masing kota terhubung secara langsung. Seperti pada gambar, kota A terhubung secara langsung dengan kota B dan C. Kota B terhubung langsung dengan kota A, C, dan D. Informasi inilah yang disebut sebagai informasi rute atau routing information. Informasi rute dari masing-masing kota ini yang kemudian dikumpulkan menjadi sebuah tabel rute atau routing table yang mencakup keenam kota tersebut. Kongkritnya, routing table dari kumpulan simpul/node/vertex seperti gambar di atas adalah sebagai berikut. routing table example Pada routing table di atas, selain parameter simpul asal (origin) dan simpul tujuan (destination), ada satu parameter lagi yaitu bobot (weight).

Parameter ini merepresentasikan seberapa besar usaha yang diperlukan untuk pergi dari simpul asal menuju simpul tujuan. Bobot di sini bisa direpresentasikan menjadi berbagai macam besaran seperti panjang, kerapatan, kepadatan, dan lain-lain tergantung implementasinya. Jika seperti analogi kota di atas, mungkin parameter bobot bisa merepresentasikan gabungan jarak dan kepadatan (tingkat kemacetan) yang tentu saja dengan komposisi tertentu. Agar mempermudah pemahaman, kita asumsikan saja semua jalan antar kota mempunyai bobot yang sama sehingga rute terdekat adalah sudah pasti yang jumlah simpulnya paling sedikit. Contoh, untuk pergi ke kota F dari kota A, rute A → C → F akan lebih dekat jika dibandingkan dengan A → B → D → E → F.
Atas pemahaman yang telah dipaparkan di ataslah algoritma djikstra dibuat. Animasi berikut akan membantu anda untuk lebih memahami algoritma djikstra dan lebih mudah untuk membayangkan bagaimana langkah-langkah untuk menulis kode programnya. program. Animasi djikstraDengan melihat animasi di samping, langkah-langkah dari algoritma djikstra adalah sebagai berikut:

1. Tentukan simpul asal (origin) dan simpul tujuan (destination).
 Seperti pada animasi, simpul asal adalah simpul a atau 1, sedangkan tujuannya adalah simpul b atau 5.

 2. Tandai semua simpul dengan tanda “belum dikunjungi” atau “unvisited”, kecuali simpul asal bisa langsung diset menjadi dikunjungi atau “visited”. Secara implementasi, tanda visited maupun unvisited bisa dengan cara mengeset salah satu atribut simpul dengan nilai 0 untuk mengganti tanda visited atau tak hingga (∞) untuk mengganti tanda unvisited.

 3. Untuk setiap iterasi, periksa bobot antara simpul saat ini sedang berada dengan simpul-simpul tetangganya. Misalnya sekarang sedang berada pada simpul 1, maka periksa bobot 1 → 2, 1 → 3, dan 1 → 6.

Dari gambar jelas terlihat bahwa bobot terkecil adalah 1 → 2 = 7. Sehingga jika sekarang berada pada simpul 1 maka simpul selanjutnya adalah simpul 2. Karena perjalanan telah sampai disimpul 2, maka atribut ∞ dari simpul ini diset menjadi 0 untuk menandakan telah dikunjungi.

4. Ulangi langkah 3 di atas untuk simpul selanjutnya, hingga berakhir pada pada simpul tujuan dalam kasus ini adalah simpul 5.

Pseudo code dari algoritma djikstra bisa dituliskan sebagai berikut:

function Dijkstra(Graph, source):
      for each vertex v in Graph:            // Initializations
          dist[v] := infinity ;              // Unknown distance function from source to v
          previous[v] := undefined ;         // Previous node in optimal path from source
      end for ;
      dist[source] := 0 ;                    // Distance from source to source
      Q := the set of all nodes in Graph ;   // All nodes in the graph are unoptimized - thus are in Q
      while Q is not empty:                  // The main loop
          u := vertex in Q with smallest distance in dist[] ;
          if dist[u] = infinity:
              break ;                        // all remaining vertices are inaccessible from source
          end if ;
          remove u from Q ;
          for each neighbor v of u:          // where v has not yet been removed from Q.
              alt := dist[u] + dist_between(u, v) ;
              if alt < dist[v]:              // Relax (u,v,a)
                  dist[v] := alt ;
                  previous[v] := u ;
                  decrease-key v in Q;       // Reorder v in the Queue
              end if ;
          end for ;
      end while ;
      return dist[] ;
  end Dijkstra.
 
Algoritma djikstra biasanya digunakan pada service dan aplikasi yang berhubungan dengan routing protocol.
 

Tidak ada komentar:

Posting Komentar