Pada Saat ini sudah Banyak Algortima mencari lintasan terpendek (Shortest Path) yang pernah ditulis. Algortima Lintasan terpendek yang paling terkenla adalah Algoritma Dijkstra yang ditemukan oleh EDSGER W. DIJKSTRA. Dalam naskah aslinya, Algortima Dijkstra siterapkan untuk mencari lintasan terpendek pada graf berarah, namun algoritma ini juga benar untuk Graf tak-berarah.

Jaringan Komputer (Computer Network) terdiri dari sejumlah komputer yang saling terhubung satu sama lain melalui saluran komunikasi (misalnya kabel, serat optik, gelombang mikro, gelombang radio). Antara suatu komputer dengan Komputer lain seringkali terpisah antara geografis (antar kota, atau antar negara), atau berada pada daerah geografis yang sama (satu gedung, atau satu area, dan sebagainya). Pesan yang dikirim dari suatu komputer ke komputer lain umumnya dipisah menjadi paket data yang berukuran lebih kecil.Saluran komunikasi yang digunakan untuk menghantarkan paket mempunyai keterbatasan dalam hal kecepatan transmisi (umumnya keceptan Transmisi dinyatakan dalam satuan kbps). Untuk menyampaikan paket data dari suatu komputer ke komputer lainnya, sistem jaringan komputer harus dapat melakukan pemilihan rute agar paket dapat sampai ke komputer tujuan dengan cepat. yang dimaksud dengaan routing (perutean) adalah menentukan lintasan yang dilalui oleh paket dari komputer pengirim ke komputer penerima.

Permasalahnnya adalah bagaimana menentukan rute yang tepat agar paket dapat samapai ke komputer tujuan secepat mungkin. Dengan menggunakan rute tersebut, paket data yang sampai ke suatu komputer dapat diarahkan ke komputer tetangga menuju komputer penerima dengan delay waktu yang minimum. Dengan kata lain kita harus menentukan Shortest Path yang akan dilalui paket menuju komputer tujuan. Perutean yang diharapakan adalah perutean yang sistem komputer dapat menentukan rute baru ketika terjadi perubahan pada topologi jaringan (misalnya ada kerusakan router, sehingga router tersebut tidak dapat dilalui, atauperubahan kecepatan trasmisi antar router, atau bahkan adanya penambahan router baru). - bersambung

Label: