lintasan terpendek

1. Pendahuluan
Persoalan lintasan terpendek yaitu menemukan lintasan terpendek antara dua atau beberapa simpul lebih yang berhubungan. Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan optimasi. Persoalan ini biasanya direpresentasikan dalam bentuk graf. Graf yang digunakan dalam pencarian lintasan terpendek atau shortest path 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.
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 gunakan di sini adalah bahwa semua bobot bernilai positif. Kata “terpendek” jangan selalu diartikan secara fisik sebagai panjang minimum, sebab kata “terpendek” berbeda-beda makanya bergantung pada tipikal perasoalan yang akan diselesaikan. Namun, secara umum “terpendek” berarti meminimalisasi bobot pada suatu lintasan di dalam graf.
Contoh-contoh terapan pencarian lintasan terpendek misalnya:
1. Misalkan simpul pada graf dapat merupakan kota, sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota. Bobot sisi graf dapat menyatakan jarak antara dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek di sini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A ke kota B.
2. Misalkan simpul pada graf dapat merupakan terminal komputer atau simpul komunikasi dalam suatu jaringan, sedangkan sisi menyatakan saluran komunikasi yang menghubungkan dua buah terminal. Bobot pada graf dapat menyatakan biaya pemakaian saluran komunikasi antara dua buah terminal, jarak antara dua buah terminal, atau waktu pengiriman pesan (message) antara dua buah terminal. Persoalan lintasan terpendek di sini adalah menentukan jalur komunikasi terpenek antara dua buah terminal komputer. Lintasan terpendek akan menghemat waktu pengiriman pesan dan biaya komunikasi.

Ada beberapa macam persoalan lintasan terpendek, antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shortest path).
d. Lintasan terpendekan antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).












DASAR TEORI

Graph merupakan struktur data yang
paling umum. Jika struktur linear
memungkinkan pendefinisian keterhubungan
sikuensial antara entitas data, struktur data tree
memungkinkan pendefinisian keterhubungan
hirarkis, maka struktur graph memungkinkan
pendefinisian keterhubungan tak terbatas antara
entitas data.
Definisi Graf adalah G = (V,E) yang
dalam hal ini :
V = himpunan tak kosong dari simpul-simpul
= {v1, v2, v3, ...}
E = himpunan sisi yang menghubungkan
sepasang simpul
= {e1, e2, e3, ...}
G adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4) }
= { e1, e2, e3, e4, e5, e6, e7}
Berdasarkan orientasi arah pada sisi, maka
secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi
arah disebut graf tak-berarah
Gbr. 2
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah
disebut sebagai graf berarah.
Gbr. 3
Dua buah simpul v1 dan simpul v2 disebut
terhubung jika terdapat lintasan dari v1 ke v2.
G disebut graf terhubung (connected
graph) jika untuk setiap pasang simpul vi dan vj
dalam himpunan V terdapat lintasan dari vi ke vj.
Jika tidak, maka G disebut graf takterhubung
(disconnected graph).


















Persoalan Lintasan Terpendek

Perhatian khusus ditujukan untuk menemukan rute terpendek antara
pasangan pusat dalam sebuah jaringan. Contohnya, sebuah perusahaan bisnis
besar dengan kantor pusat di New York mempunyai beberapa cabang utama di
negara-negara seluruh dunia. Kantor pusat mengkoordinasi seluruh kegiatan
operasi perusahaan, dan setiap hari seluruh informasi (meliputi permintaan,
penawaran dan biaya) harus diberikan dari kantor pusat ke kantor-kantor
cabang. Informasi yang ada dikirimkan via teleks. Diberikan biaya pengiriman
pesan melalui teleks antara dua perusahaan, dan ditentukan rute komunikasi
termurah dari kantor pusat dan setiap kantor cabang lainnya.
Perusahaan perbankan dengan kantor pusat di New York (NY) dan kantor
cabang di Paris (P), Zurich (Z), Berlin (B), Tokyo (T), Hongkong(HK) dan
Sydney (S). Setiap hari informasi penting (meliputi permintaan, penawaran
dan biaya) harus diberikan dari kantor pusat ke kantor-kantor cabang.
Informasi yang ada dikirimkan via teleks. Biaya pengiriman pesan antara dua
kantor cabang diberikan dalam matriks di bawah ini :









Graf yang digambarkan berdasarkan matriks di atas adalah pada Gambar 2.3.
di bawah ini :














Seperti contoh terdahulu, model graf ini memberikan himpunan semua
hubungan yang mungkin dan permasalahannya adalah memilih sebuah
himpunan bagian dari himpunan ini yang menunjukkan bahwa jaringan yang
ada sesuai dan jumlah biaya dari pengiriman informasi dari kantor pusat ke
kantor cabang dapat diminimalkan.

2.1 Persoalan Lintasan Terpendek

Persoalan yang diambil di sini yaitu single-source shortest path atau lintasan terpendek dari simpul tertentu ke semua simpul yang lain Persoalan: diberikan graf berbobot G(V, E). Tentukan lintasan terpendek dari sebuah simpul asal, a, ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot positif. untuk mencari lintasan terpendek adalah sebagai berikut: Karena kita harus meminimumkan panjang lintasan, maka sebagai ukuran optimasi dapat digunakan total jarak pada lintasan yang baru dibentuk. Dalam hal ini, lintasan dibentuk satu per satu. Lintasan berikutnya yang dibentuk ialah lintasan yang meminimumkan jumlah jaraknya.

untuk mencari lintasan terpendek dirumuskan sebagai berikut: 1. Periksa semua sisi yang langsung bersisian (incident) dengan simpul a. Pilih sisi yang bobotnya terkecil. Sisi ini menjadi lintasan terpendek pertama. Sebut lintasan itu L1. 2. Tentukan lintasan terpendek kedua dengan cara berikut: (i) hitung: d1 = Panjang (L1) + bobot sisi dari simpul akhir L1 ke simpul i yang lain (simpul i yang lain adalah simpul i yang belum termasuk di dalam L1) (ii) pilih d1 yang terkecil bandingkan d1 dengan bobot sisi (a, i). Jika bobot (a, i) lebih kecil daripada d1, maka lintasan terpendek kedua adalah L2 = (a, i), jika tidak, maka L2 = L1 u (sisi dari simpul akhir L1 ke simpul i) 3. Dengan cara yang sama, ulangi langkah 2 untuk menentukan lintasan terpendek berikutnya. Contoh: Tinjau sebuah graf berarah di bawah ini. Bobot pada setiap sisi dapat menyatakan jarak, ongkos, waktu, dan sebagainya.

Lintasan terpendek dari simpul 1 ke semua simpul lain yang diberikan pada tabel di bawah ini dihasilkan dengan mengunakan strategi greedy di atas:


6. KESIMPULAN

Graf dapat dipakai dalam menyelesaikan
permasalahan pencarian rute terpendek yang
menggunakan algoritma A*.
Untuk merepresentasikan graf dalam menyelesaikan
permasalahan dengan pencarian rute terpendek, dapat
digunakan aplikasi Graph Search yang bisa membuat
graf sesuai dengan keinginan kita.