A. LINTASAN TERPENDEK (SHORTEST PATH)Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan dan sebagainya. Asumsi yang kita gnakaan disini adalah bahwa semua bobot bernilai positif. Kata terpendek jangan selalu diartikan secara fisik sebagai panjang minimum, sebab kata terpendek berbeda-beda maknanya bergantung pada tipikal persoalan yang akan diselesaikan. Namun secara umum terpendek berarti meminimasi bobot pada suatu lintasan di dalam graf.Ada beberapa macam persoalan lintasan terpendek, antara lain:a. Lintasan terpendek antara dua buah simpul tertentu.b. Lintasan terpendek antara semua pasang simpul.c. Lintasan terpendek dari simpul tertentu ke simpul yang lain.d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.Pada dasarnya, jenis persoalan a mirip dengan jenis persoalan c, karena pencarian lintasan terpendek pada jenis persoalan c dapat dihentikan bila simpul tujuan yang dikehendaki sudah ditemukan lintasan terpendeknya.Sebagai ilustrasi, tinjau garaf berarah pada gambar dibawah. Lintasan terpendek dari simpul 1 ke simpul lain diberikan pada table dibawah ini.Simpul asalSimpul tujuanLintasan terpendekJarak

11111342561,31,3,41,3,4,21,5Tidak ada10254545-

Sampai saat ini, sudah banyak algoritma mencari lintasan terpendek yang pernah ditulis orang. Algoritma lintasan terpendek yang paling terkenal adalah algoritma Dijkstra (sesuai dengan nama penemunya, Edsger W. Dijkstra). Dalam naskah aslinya, algoritma diterpakan pada untuk mencari lintasan terpendek pada graf berarah. Namun, algoritma ini juga benar untuk graf tak-berarah.B. ALGORITMA DIJKSTRAAlgoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy. Prinsip greedy pada algoritma Dijkstra menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi.Ada beberapa versi algoritma Dijkstra yang ditulis pada berbagai pustaka. Algoritma yang dibahas dibawah ini adalah salah satu versinya.1. Matriks Ketetanggaan M

Misalkan sebuah graf berbbot dengan n buah simpul dinyatakan dengan matriks ketetanggaan , yang dalam hal ini,

= bobot sisi (pada graf tak berarah ) = 0

= , jika tidak ada sisi dari simpul ke simpul

Contoh:Graf yang menyatakan beberapa kota

Matriks M=

2. Tabel S

Selain matriks M, kita juga menggunakaan table yang dalam hal ini

= 1, jika simpul termasuk ke dalam lintasan terpendek

= 0, jika simpul tidak termasuk ke dalam lintasan terpendek3. Table D

Table yang dalam hal ini

= panjang lintasan dari simpul awal ke simpul Contoh :Perhitungan lintasan terpendek dari simpul awal a = 5 dari soal diatas ke semua simpul lainnya ditabulasikan sebagai berikut.

Jadi, lintasan terpendek dari: 5 ke 6 adalah 5,6 dengan jarak = 250 5 ke 7 adalah 5,6,7 dengan jarak = 1150 5 ke 4 adalah 5,6,4 dengan jarak = 1250 5 ke 8 adalah 5,6,8 dengan jarak = 1650 5 ke 3 adalah 5,6,4,3 dengan jarak = 2450 5 ke 2 adalah 5,6,4,3,2 dengan jarak = 3250 5 ke1 adalah 5,6,8,1 dengan jarak = 3350