MAKALAH
MATEMATIKA DISKRIT
LINTASAN TERPENDEK
OLEH
Emly Yasril (19205012)
Elza Nora Yuliani (19205045)
Fadhilah Haswenova (20205007)
Rahmadina (20205025)
Dosen Pembimbing:
Prof. Dr. AHMAD FAUZAN, [Link], [Link]
PROGRAM STUDI MAGISTER PENDIDIKAN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS NEGERI PADANG
2021
KATA PENGANTAR
Puji dan syukur kehadirat Allah SWT atas limpahan rahmat dan karunia-
Nya sehingga penulis dapat menyelesaikan makalah ini dengan baik. Makalah ini
membahas tentang “Lintasan Terpendek”. Makalah disusun untuk memenuhi
persyaratan sebagai tugas mata kuliah Matematika Diskrit pada Program Studi
Pendidikan Matematika Pascasarjana Universitas Negeri Padang.
Dalam penulisan makalah ini, penulis telah banyak mendapat bantuan,
dorongan, petunjuk, dan bimbingan dari berbagai pihak. Untuk itu, penulis
mengucapkan terima kasih kepada yang terhormat,
1. Prof. Dr. Ahmad Fauzan, [Link], [Link] selaku dosen pembimbing mata
kuliah Matematika Diskrit.
2. Teman-teman yang telah memberikan sumbangan pemikiran dalam
diskusi-diskusi mengenai penulisan makalah ini.
3. Semua pihak yang telah membantu dalam menyelesaikan penulisan
makalah ini.
Semoga semua bimbingan, arahan, saran, dan bantuan yang telah diberikan
menjadi amal ibadah dan mendapat balasan dari Allah SWT. Penulis telah
berusaha semaksimal mungkin menyelesaikan makalah ini. Namun jika masih
terdapat kekurangan, penulis mengharapkan kritikan dan saran dari pembaca demi
kesempurnaan makalah ini. Atas kritik dan saran yang diberikan, penulis ucapkan
terima kasih.
Padang, Mei 2021
Pemakalah
BAB I
PENDAHULUAN
A. Latar Belakang
Matematika merupakan suatu bidang ilmu yang banyak digunakan untuk
menyelesaikan berbagai permasalahan yang muncul dalam kehidupan sehari-hari.
Berbagai permasalahan tersebut ada yang dapat di modelkan kedalam suatu model
matematika namun ada pula beberapa permasalahan yang tidak dapat dimodelkan
ke dalam model [Link] di luar bidang matematika biasanya akan
dibawa ke dalam penyelesaian matematika, yaitu dengan mencari model
matematikanya. Suatu permasalahan akan semakin mudah dipelajari, dipahami dan
diselesaikan jika dapat dimodelkan ke dalam suatu model matematika.
Setelah diperoleh model matematika dari suatu masalah, maka masalah
tersebut akan dibawa ke dalam cabang-cabang ilmu matematika untuk menentukan
penyelesaiannya. Salah satu cabang ilmu matematika yang dapat digunakan untuk
menyelesaikan permasalahan tersebut adalah teori graph. Teori graf lahir pada
tahun 1736 melalui tulisan Euler yangberisi tentang upaya pemecahan masalah
jembatan Konigsberg yang sangat terkenal di Eropa. Kurang lebih seratus tahun
setelah lahirnya tulisan Euler tersebut tidak ada perkembangan yang berarti dengan
teori [Link] G terdiri dari himpunan tak kosong dari elemen-elemen yang
disebut titik (vertex) dan daftar pasangan berurutan dari elemen-elemen yang
disebut sisi (edge)
Himpunan titik dari graph G disebut himpunan titik dari G dinyatakan
dengan V(G) dan daftar sisi dari G dinyatakan dengan E(G). SuatuGraph G = (V,E)
menyatakan graph G dengan himpunan titik-titik V(G) dan himpunan sisi
E(G).Terdapat banyak konsep dalam graph, salah satunya adalah lintasan terpendek
(Shortest Path) yang merupakan salah satu topik yang mampu mendukung
penerapan graph dalam berbagai bidang ilmu.
Makalah ini membahas tentang persoalan lintasan terpendek suatu graf
dengan algoritma dijkstra. Lintasan terpendek merupakan bagian dari teori graf. Jika
diberikan sebuah graf berbobot, masalah jarak terpendek adalah bagaimana kita
mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk
jalur tersebut. Persoalan ini adalah persoalan optimasi, dimana kita akan mencari
solusi penyelesaian yang paling efektif dari masalah penentuan lintasan terpendek
pada suatu graf.
Saat ini banyak sekali algortima-algoritma yang dapat digunakan untuk
menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari
suatu graf. Solusi yang didapat dari penelusuran algoritma tersebut dapat diberi
nama Pathing Algorithm. Ada dua algortima yang cukup terkenal yang bisa
digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma
Dijkstra dan Algoritma Bellman-Ford. Tetapi pada kesempatan ini kita hanya akan
membahas tentang algoritma dijkstra.
Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk
memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf .
Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing
sisi haruslah bernilai positif (>=0).
B. Rumusan Masalah
Sesuai dengan latar belakang masalah maka rumusan masalah yang diajukan adalah
1. Apakah yang dimaksud dengan Lintasan terpendek?
2. Bagaimana mencari jarak terpendek pada sebuah jalur ?
C. Tujuan Penulisan
Sejalan dengan rumusan masalah maka tujuan penulisan makalah ini
adalah :
1. Untuk mengetahui apakah yang dimaksud dengan Lintasan terpendek
2. Mengetahui jarak terpendek pada sebuah jalur.
D. Manfaat Penulisan
Manfaat yang diharapkan dari hasil penelitian ini adalah bisa mengetahui jarak
terpendek / menentukan rute terpendek dari suatu tempat ke tempat yang lain,
menghemat biaya (ongkos) perjalanan dan menghemat waktu dalam sebuah
perjalanan dalam kehidupan sehari-hari.
BAB II
PEMBAHASAN
A. Pengertian Lintasan Terpendek (Shortest Path)
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.
B. Persoalan Linasan Terpendek
Ada beberapa macam persoalan lintasan terpendek, antara lain:
1. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
2. Lintasan terpendek antara semua pasangan simpul (all pairs shortest
path).
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain
(single-source shortest path).
4. Lintasan terpendekan antara dua buah simpul yang melalui beberapa
simpul tertentu (intermediate shortest path).
C. Algoritma Djikstra
Algoritma ini merupakan Algoritma yang paling terkenal untuk mencari
lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu
benar untuk graf tak-berarah. Algoritma ini menggunakan Algoritma Greedy
sebagai berikut: “Pada setiap langkah, ambil sisi yang berbobot minimum yang
menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain
yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah
merupakan lintasan yang terpendek diantara semua lintasannya ke simpul simpul
yang belum terpilih.
Algoritma Djikstra merupakan salah satu metode untuk mencari lintasan
terpendek dari sebuah simpul ke semua simpul lainnya dalam graf yang hanya
memiliki bobot positif. Secara formal, masalah lintasan terpendek semua
pasangan simpul adalah untuk mencari lintasan terpendek di antara semua pasang
simpul vi , viV sedemikian sehingga ij
Dalam mencari lintasan terpendek dari suatu simpul ke semua pasangan
simpul algoritma Djikstra melalui sejumlah langkah yang menggunakan prinsip
greedy. Prinsip greedy pada algoritma Djikstra menyatakan bahwa pada setiap
langkah kita memilih sisi yang berbobot minimum dan memasukkannya dalam
himpunan solusi
Langkah-langkah dalam menentukan lintasan terpendek pada algoritma
Dijkstra yaitu:
1. Pada awalnya pilih titik dengan bobot yang terendah dari titik yang
belum terpilih, diinisialisasikan dengan „0‟ dan yang sudah terpilih
diinisialisasikan dengan „1‟.
2. Bentuk tabel yang terdiri dari titik, status, bobot dan redecessor.
Lengkapi kolom bobot yang diperoleh dari jarak titik sumber kesemua
titik yang langsung terhubung dengan titik sumber tersebut.
3. Jika titik sumber ditemukan maka tetapkan sebagai titik terpilih.
4. Tetapkan titik terpilih dengan label permanen dan perbarui titik yang
langsung terhubung
5. Tentukan titik sementara yang terubung pada titik yang sudah terpilih
sebelumnya dan merupakan bobot terkecil dilihat dari table dan tentukan
sebagai titik terpilih berikutnya.
6. Apakah titik yang tepilih merupakan titik tujuan? Jika ya, maka
kumpulan titik terpilih atau predecessor merupakan rangkaian yang
menunjukkan lintasan terpendek.
7. Begitu seterusnya sampai semua titik terpilih.
Sampai saat ini, sudah banyak algoritma untuk mencari lintasan terpendek
yang pernah ditulis orang. Algoritma lintasan terpendek yang paling terkenal
adalah algoritma Dijkstra (sesuai nama penemunya). Aslinya, algoritma Dijkstra
diterapkan untuk mencari lintasan terpendek pada graf berarah.
Ada beberapa versi algoritma Dijkstra yang ditulis pada berbagai pustaka.
Algoritma yang dibahas dibawah ini adalah :
1. Matriks Ketetanggaan M
Misalkan sebuah graf berbbot dengan n buah simpul dinyatakan dengan
matriks ketetanggaan
M = m , yang dalam hal
i mij = bobot sisi (i, j)(pada graf tak berarah)
j ini,
mij = m ji
mii = 0
mij
= , jika tidak ada sisi dari simpul i ke simpul j
2. Larik S
Selain matriks M, kita menggunakan larik S = [ si ] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3. Larik D
Larik/Tabel D = [ di ] yang dalam hal ini
di = panjang lintasan dari simpul awal s ke simpul j
D. Contoh Soal Algoritma Dijkstra
1. Diberikan graf berbobot G= (V, E) dan sebuah simpul a. Tentukan lintasan terpendek dari
a ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot
positif. (a = 1)
45
1 50 2 10
5
40
15 35
20 10 20
30
3 15 4 3
6
Gambar : Lintasan
Penyelesaian :
1. Langkah 0 (inisialisasi):
- inisialisasi si = 0 dan di = mai untuk i = 1, 2, ..., n
2. Langkah 1:
- isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah
pasti terpilih)
- isi da dengan (tidak ada lintasan terpendek dari simpul a ke a)
3. Langkah 2 :
- cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, ..., dn}
- isi sj dengan 1
- perbarui di, untuk i = 1, 2, 3, …, n dengan: di (baru) = min{di (lama), dj + mji
Pada lintasan, tambahkan simpul j sebagai simpul terpilih untuk lintasan selanjutnya.
4. Langkah 3: mengulangi langkah 2 sampai s j= 1, untuk j = 1, 2, ... ,,n
5. Membuat himpunan simpul berdasarkan urutan yang diperoleh yang merupakan
lintasan terpendek dengan bobot d
1. Tabel S
Lelara Simpul yang Lintasan S S S S S S
n dipilih 1 2 3 4 5 6
Inisial - - 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0
2 3 1,3 1 0 1 0 0 0
3 4 1,3,4 1 0 1 1 0 0
4 2 1,3,4,2 1 1 1 1 0 0
5 5 1,5 1 1 1 1 1 0
2. Tabel D
D D D D D D
1 2 3 4 5 6
0 50 10 40 45
(1,2) (1,3) (1,4) (1,5) (1,6)
50 10 40 45
(1,2) (1,3) (1,4) (1,5) (1,6)
50 10 25 45
(1,2) (1,3) (1,3,4) (1,5) (1,6)
45 10 25 45
(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)
45 10 25 45
(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)
45 10 25 45
(1,3,4,2) (1,3) (1,3,4) (1,5) (1,6)
Jadi, lintasan terpendek dari a ke setiap simpul lainnya di G adalah :
Simpul asal Simpul tujuan Lintasan terpendek Jarak
1 3 1,3 10
1 4 1,3,4 25
1 2 1,3,4,2 45
1 5 1,5 45
1 6 Tidak ada -
2. Tentukan lintasan terpendek dari kota Boston (5) ke setiap kota lainnya menggunakan
algoritma djiksra
Penyelesaian :
1. Langkah 0 (inisialisasi):
- inisialisasi si = 0 dan di = mai untuk i = 1, 2, ..., n
2. Langkah 1:
- isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti
terpilih)
- isi da dengan (tidak ada lintasan terpendek dari simpul a ke a)
3. Langkah 2 :
- cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, ..., dn}
- isi sj dengan 1
- perbarui di, untuk i = 1, 2, 3, …, n dengan: di (baru) = min{di (lama), dj + mji
Pada lintasan, tambahkan simpul j sebagai simpul terpilih untuk lintasan selanjutnya.
4. Langkah 3: mengulangi langkah 2 sampai s j= 1, untuk j = 1, 2, ... ,,n
5. Membuathimpunan simpul berdasarkan urutan yang diperoleh yang merupakan lintasan
terpendek dengan bobot d
Perhitungan lintasan terpendek dari simpul awal a = 5 dari soal diatas ke semua simpul
lainnya ditabulasikan sebagai berikut.
1. Tabel S
Lelaran Simpul yang Lintrasan S
dipilih 1 2 3 4 5 6 7 8
Inisial - - 0
1 5 5
2 6 5,6
3 7 5,6,7
4 4 5.6,4
5 8 5,6,8
6 3 5,6,4,3
7 2 5,6,4,3,2
2. Tabel D
Lelaran Simpul Lintrasan D
yang 1 2 3 4 5 6 7 8
dipilih
Inisial - - 1500 0 250
1 5 5 1500 250
2 6 5,6 1250 250 1150 1650
3 7 5,6,7 1250 250 1150 1650
4 4 5.6,4 2450 1250 250 1150 1650
5 8 5,6,8 3350 2450 1250 250 1150 1650
6 3 5,6,4,3 3350 2450 1250 250 1150 1650
7 2 5,6,4,3,2 3350 3320 2450 1250 250 1150 1650
Jadi lintasan terpendek dari kota Boston ke setiap kota lainnya adalah :
Simpul asal Simpul tujuan Lintasan terpendek Jarak
5 6 5,6 250
5 7 5,6,7 1150
5 4 5,6,4 1250
5 8 5,6,8 1650
5 3 5,6,4,3 2450
5 2 5,6,4,3,2 3250
5 1 5,6,8,1 3350
BAB III
PENUTUP
A. Kesimpulan
Pada lintasan terpendek kita bisa mengetahui rute atau jalur yang paling efisien
(terpendek) dari suatu tempat ke tempat lainnya, kita pun bisa mempersingkat waktu
dengan menggunakan jalur yang efisien, dan juga bisa menghemat biaya atau ongkos
transportasi. Biasanya pada lintasan terpendek menggunakan algoritma yang
digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada
suatu graf. Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari
masing-masing sisi haruslah bernilai positif ( >=0 ). Dalam mencari lintasan
terpendek, algoritma yang paling banyak digunakan orang ialah algoritma Dijkstra,
karena kerjanya paling efisien dan tidak membutuhkan waktu yang banyak.
B. Saran
Dalam penarikan kesimpulan dalam teori graf, banyak hal yang harus di
perhatikan agar penarikan kesimpulan dapat di lakukan dengan benar. Kepada para
pembaca yang kelak ingin membuat makalah atau karya tulis mengenai teori graf,di
sarankan agar lebih mau membaca dan mempelajari tentang teori graf. Penulis sangat
menyadari bahwa karya tulis ini masih jauh dari sempurna, oleh karena itu, penulis
sangat mengharap kritik dan saran yang membangun dari para pembaca, agar penulis
dapat memperbaiki di waktu yang akan datang.
DAFTAR PUSTAKA
Salaki, D. T. (2011) ‘Penentuan Lintasan Terpendek Dari Fmipa Ke Rektorat Dan Fakultas
Lain Di Unsrat Manado Menggunakan Algoritma Djikstra’, Jurnal Ilmiah Sains,
11(1), p. 73. doi: 10.35799/jis.11.1.2011.46.
Kevin, S. (2014) ‘Makalah Departemen Teknologi Informasi’, pp. 1–26.
Ketut, I Budayasa. 2007. Teori Graph dan Aplikasinya. Departemen Pendidikan Nasional :
Universitas Negeri Surabaya
Sutamo, Heri dkk. 2003. Matematika Diskrit. Bandung: Jurusan Matematika UPI & JICA.
[Link]