Memahami Algoritma Dijkstra pada OSPF - Perwira Learning Center

 JALUR TERPENDEK (SHORTEST PATH)

A. Latar Belakang

Dalam kehidupan sehari-hari maupun sistem komputasi, efisiensi adalah kunci utama. Salah satu tantangan klasik dalam teori graf adalah bagaimana menemukan jalur dengan biaya (jarak, waktu, atau energi) terendah dari satu titik ke titik lainnya. Masalah ini menjadi krusial ketika struktur jaringan menjadi sangat kompleks dan memiliki ribuan titik koneksi.

B. alat dan bahan

Laptop : sebagai tools

GNS3 :  Perangkat lunak emulator 

C. Pembahasan 

Algoritma dijkstra adalah algoritma untuk menemukan jalur secara efisien, bukan sekedar terdekat. Algoritma ini dicetuskan oleh ilmuan komputer  Edsger W. Dijkstra pada tahun 1956 dan diterbitkan pada 3 tahun setelahnya, yaitu 1959. 

Prinsip kerja algoritma dijkstra: 

• Menentukan titik awal sebagai sumber.
• Memberikan nilai jarak sementara (tak hingga) ke semua titik lain dan nilai nol untuk titik asal.
• Secara bertahap mengunjungi titik terdekat yang belum dikunjungi dan memperbarui nilai jarak pada tetangganya.
• Proses berhenti ketika semua titik telah dikunjungi atau jalur terpendek ke titik tujuan telah ditemukan.

Rumus perhitungan 

S : titik awal

V : Panjang jalan

O : jarak kota sebelum 

misal : s + v = 3 + 5 = 8

             s + v = 4 + 3 = 7 < 8

maka yang di ambil yaitu yang terkecil yaitu 7.

Contoh : 

 Menentukan jalur tercepat dari A ke B

langkah 1 : 

• 0+7 = 7 
• 0 + 9 = 9 
• 0 + 14 = 14

langkah 2 kita pilih 7 karena terkecil :

• 7 + 10 = 17 > 9
• 7 + 15 = 22 > 9

langkah 3 pilih 9 

• 9+ 2 = 11
• 9+ 11 = 20 
• maka 11<20

langkah 4 pilih 11

• 11 +9 = 20

maka jarak terdekat yang ditempuh yaitu A - 3 - 6 - B

Manfaat Algoritma dijkstra: 

• Manfaat yang paling sering kita rasakan adalah kemampuannya menentukan rute tercepat, contohnya GPS.
• Algoritma ini memastikan data yang kita kirim sampai ke tujuan seefisien mungkin, contoh nya routing OSPF 
• Mencari jalur transmisi sinyal terbaik dalam jaringan telepon agar kualitas suara atau data tetap terjaga dengan latensi minimal.
• Dalam dunia bisnis, algoritma ini menjadi alat bantu penghemat biaya operasional. Seperti Membantu perusahaan logistik merencanakan rute pengiriman yang paling efisien guna menekan biaya bahan bakar.

D. Kesimpulan 

Secara keseluruhan, Algoritma Dijkstra merupakan solusi fundamental dalam teori graf yang bekerja dengan prinsip greedy untuk menemukan jalur terpendek dari satu titik awal ke titik tujuan berdasarkan bobot terkecil. Melalui proses inisialisasi dan rumus relaksasi yang sistematis, algoritma ini mampu memperbarui catatan jarak secara akurat selama seluruh bobot jalur bernilai positif.

E. Daftar Pustaka 

Dijkstra's algorithm. (2024, 21 Februari). Dalam Wikipedia. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm