implementasi algoritma dijkstra dalam menentukan...

IMPLEMENTASI ALGORITMA DIJKSTRA DALAM MENENTUKAN

RUTE TERPENDEK 5 OBJEK WISATA POPULER DI KOTA

PONTIANAK KALIMANTAN BARAT

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Pendidikan

Program Studi Pendidikan Matematika

Disusun oleh:

PETRA KRISTER ISALOKA

NIM: 161414104

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2020

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

i

IMPLEMENTASI ALGORITMA DIJKSTRA DALAM MENENTUKAN

RUTE TERPENDEK 5 OBJEK WISATA POPULER DI KOTA

PONTIANAK KALIMANTAN BARAT

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Pendidikan

Program Studi Pendidikan Matematika

Disusun oleh:

PETRA KRISTER ISALOKA

NIM: 161414104

PROGRAM STUDI PENDIDIKAN MATEMATIKA

JURUSAN PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2020


iv

HALAMAN PERSEMBAHAN

Dengan penuh rasa syukur kepada Tuhan ku persembahkan Skripsi ini kepada :

Tuhan Yesus serta Bunda Maria yang senantiasa selalu menyertai setiap langkah

hidupku

Kedua orangtuaku, Pak Akiong dan Bu Lidya. Serta saudara kandungku, Bang

Topan, Krista, Topin dan Kristi.

Kepada yang selalu bertanya : “Kapan lulus?”

Teman-temanku di Jogja dalam suka maupun duka

Program Studi Pendidikan Matematika Universitas Sanata Dharma.

Almamaterku


v

MOTTO

“I can do all this through Christ who gives me strength”

-Philippians 4:13


viii

ABSTRAK

Penelitian ini bertujuan (1) memodelkan rute terpendek objek wisata Kota

Pontianak yang terdiri dari 5 objek wisata didalam graf, (2) Membuat sistem

pencarian jalur terpendek menggunakan Algoritma Dijkstra untuk memudahkan

wisatawan mengetahui objek wisata dan rute terpendek dari posisi objek wisata

pertama ke objek wisata selanjutnya, (3) Memudahkan wisatawan mengatahui

objek wisata terdekat dari posisi saat itu wisatawan berada.

Jenis penelitian yang digunakan dalam penelitian ini adalah penelitian

terapan. Objek dalam penelitian ini adalah rute terpendek yang menghubungkan 5

destinasi wisata popular di Kota Pontianak.

Penelitian ini menunjukan proses Algoritma Dijkstra dalam menentukan

rute terpendek jalur yang menghubungkan 5 destinasi wisata popular di Kota

Pontianak yaitu: Tugu Khatulistiwa, Aloe Vera Center, Keraton Kadriah, Taman

Alun Kapuas, Rumah Radakng. Berdasarkan analisis data diperoleh 5 rute dalam

mengunjungi 5 destinasi wisata popular di Kota Pontianak dengan posisi awal

merupakan destinasi wisata yang berbeda-beda yaitu: (1) Tugu Khatulistiwa → Aloe Vera Center→ Keraton Kadriah → Taman Alun Kapuas → Rumah Radakng dengan panjang jalur adalah 22,74 kilometer, (2) Aloe Vera Center → Keraton Kadriah → Taman Alun Kapuas→ Rumah Radakng→ Tugu Khatulistiwa dengan panjang jalur adalah 31,61 kilometer, (3) Keraton Kadriah → Aloe Center→Tugu Khatulistiwa → Taman Alun Kapuas → Rumah Radakng dengan panjang jalur adalah 29,02 kilometer, (4) Taman Alun Kapuas → Rumah Radakng→ Keraton Kadriah→ Aloe Vera Center→ Tugu Khatulistiwa dengan panjang jalur adalah 24,04 kilometer, (5) Rumah Radakng→ Taman Alun Kapuas→ Keraton Kadriah→ Tugu Khatulistiwa dengan panjang jalur adalah 23,11 kilometer.

Kata kunci: Graf, Algoritma Dijkstra, Rute terpendek, Destinasi Wisata

Populer


ix

ABSTRACT

The aims of this research were (1) to model the shortest route of

Pontianak City attractions consisting of 5 attractions in the graph, (2) Create the

shortest path search system using Dijkstra's Algorithm to make it easier for

tourists to know the attractions and the shortest route from the position of the first

tourist attraction to the attraction Furthermore, (3) Make it easy for tourists to

know the nearest tourist attraction from the current position of tourists.

The genre used in this research was applied research. The object of this

research is the shortest route that connects 5 popular tourist destinations in

Pontianak.

This research demonstrated Djikstra Algorithm process ini determining

the shortest route the connects 5 popular torist destination in Pontianak which

were; Tugu Khatulistiwa, Aloe Vera Center, Keraton Kadriah, Taman Alun

Kapuas, Rumah Radakng. Based on the data analysis, there were five shortest

route to visit those five popular tour destination in Pontianak with dissimilar start

locations, which were: (1) Tugu Khatulistiwa → Aloe Vera Center→ Keraton Kadriah → Taman Alun Kapuas → Rumah Radakng with the length of lane was 22,74 kilometres, (2) Aloe Vera Center → Keraton Kadriah → Taman Alun Kapuas→ Rumah Radakng→ Tugu Khatulistiwa with the length of lane was 31,61 kilometres, (3) Keraton Kadriah → Aloe Center→Tugu Khatulistiwa → Taman Alun Kapuas → Rumah Radakng with the length of lane was 29,02 kilometres, (4) Taman Alun Kapuas → Rumah Radakng→ Keraton Kadriah→ Aloe Vera Center→ Tugu Khatulistiwa with the length of lane was 24,04 kilometres, (5) Rumah Radakng→ Taman Alun Kapuas→ Keraton Kadriah→ Tugu Khatulistiwa with the length of lane was 23,11 kilometres.

Key words: Graph, Dijkstra Algorithm, Shortest Route, Popular Torist

Destination


x

KATA PENGANTAR

Puji dan syukur Tuhan Yang Maha Esa, atas berkat dan karunia-Nya

penulis dapat menyelesaikan skripsi dengan judul: “IMPLEMENTASI

ALGORITMA DIJKSTRA DALAM MENENTUKAN RUTE TERPENDEK

5 OBJEK WISATA POPULER DI KOTA PONTIANAK KALIMANTAN

BARAT” dengan baik dan maksimal. Skripsi ini disusun untuk memenuhi salah

satu syarat memperoleh gelar Sarjana Pendidikan pada Program Studi Pendidikan

Matematika, Jurusan Pendidikan Matamatika dan Ilmu Pengetahuan Alam,

Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sanata Dharma Yogyakarta.

Dalam proses penyusunan skripsi ini, penulis menyadari bahwa banyak

pihak yang turut erlibat dalam meberikan bantuan, dukungan, doa, serta motivasi

kepada penulis. Oleh sebab itu, penulis mengucapkan terimakasih kepada:

1) Bapak Dr. Yohanes Harsoyo, S.Pd., M.Si., selaku dekan Fakultas Keguruan

dan Ilmu Pendidikan.

2) Bapak Marcellinus Andy Rudhito, S.Pd., selaku Ketua Jurusan Pendidikan

Matematika dan Ilmu Pengetahuan Alam.

3) Bapak Beni Utomo, M.Sc., selaku Ketua Program Studi Pendidikan

Matematika.

4) Ibu Cyrenia Novella Krisnamurti, M.Sc. Selaku Dosen Pembimbing Skripsi

dan Dosen Pembimbing Akademk yang telah memberikan bimbingan dan

pengetahuan kepada penulis dalam menyusun skripsi ini serta selama masa

perkuliahan.


xi

5) Bapak dan Ibu Dosen Program Studi Pendidikan Matematika Universitas

Sanata Dharma yang telah memberikan pengetahuan-pengetahuan dalam

bidang ilmu matematika dan pendidikan matematika sehingga dapat

bermanfaat bagi penulis sebagai bekal unutk menjadi seorang guru.

6) Bapakku dan Mamaku yang selalu memberikan semangat dan memfasilitasi

berupa materil maupun non materil sehingga penulis dapat menyelesaikan

studi di Sanata Dharma.

7) Abangku dan adaik-adikku; Bang Topan Ternando, Teo krista, Nomesio

Topin dan Kristi Danau yang selalu memberikan dukungan dan motivasi

kepada penulis hingga Skripsi ini terselesaikan.

8) UKM Basket Sanata Dharma tempat saya berdinamika untuk belajar juga

nilai-nilai kehidupan dan selalu mendukung saya agar dapat membagi waktu

antara kuliah dan baske.

9) Teman “Kontrakan Cantik” yang tinggal bersama saya selama saya di Jogja

yang terus memberikan motivasi agar cepat menyelesaikan skripsi.

10) Semua Pihak yang tidak dapat penulis sebutkan satu persatu yang telah turut

Penulis menyadari bahwa skripsi ini masih memiliki banyak kekurangan dan

masih jauh dari sempurna. Oleh sebab itu , penulis mengharapkan kritik dan

saran yang membangun agar dapat bermanfaat bagi penulis dalam penulisan

karya ilmiah di kemudian hari, Penulis berharap agar kiranya skripsi ini dapat

bermanfaat bagi banyak pihak.

Yogyakarta, 18 Agustus 2020

Penulis


xii

DAFTAR ISI

HALAMAN JUDUL ............................................................................................ i

LEMBAR PERSETUJUAN DOSEN PEMBIMBING ......................................... ii

LEMBAR PENGESAHAN ................................................................................. iii

HALAMAN PERSEMBAHAN .......................................................................... iv

MOTTO............................................................................................................... v

PERNYATAAN KEASLIAN KARYA .............................................................. vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH . vii

ABSTRAK ....................................................................................................... viii

ABSTRACT ......................................................................................................... ix

KATA PENGANTAR ......................................................................................... x

DAFTAR ISI ..................................................................................................... xii

DAFTAR TABEL ............................................................................................ xvi

DAFTAR GAMBAR ........................................................................................ xix

BAB I .................................................................................................................. 1

PENDAHULUAN ............................................................................................... 1

1.1 Latar Belakang....................................................................................... 1

1.2 Rumusan Masalah .................................................................................. 4

1.3 Tujuan Penelitian ................................................................................... 5

1.5 Batasan Masalah .................................................................................... 5

1.5 Manfaat Penelitian ................................................................................. 5

1.6 Sistematika Penulisan ............................................................................ 7

BAB II ................................................................................................................. 9

TINJAUAN PUSTAKA....................................................................................... 9

2.1 Graf ....................................................................................................... 9

2.2 Representasi Graf dalam Matriks ......................................................... 13

2.3 Algoritma Dijkstra ............................................................................... 14

2.4 Implementasi Dasar Teori Graf Dalam Pembelajaran Matematika di

Sekolah .......................................................................................................... 57

1. Jalur dari rumah menuju ke pasar ............................................................ 57


xiii

2. Digunakan dalam jenis topologi (Topologi Star)penggunaan dalam

keterkaitan antar komputer. ......................................................................... 58

3. Struktur keorganisasian ........................................................................... 59

4. Silsilah keluarga...................................................................................... 60

2.5 Kerangka Pemikiran ............................................................................ 60

BAB III.............................................................................................................. 63

METODE PENELITIAN ................................................................................... 63

3.1 Jenis Penelitian .................................................................................... 63

3.2 Objek Penelitian .................................................................................. 63

3.3 Metode Penelitian ................................................................................ 63

3.4 Instrumen Pengumpulan Data .............................................................. 65

3.5 Teknik Analisis Data........................................................................... 65

3.6 Prosedur Pelaksanaan Penelitiaan Secara Keseluruhan ......................... 66

BAB IV ............................................................................................................. 67

HASIL PENELITIAN DAN PEMBAHASAN ................................................... 67

4.1 Pemilihan 5 Objek Wisata yang Telah Dikembangkan di Pontianak ..... 67

4.2 Representasi Jalan Raya dalam Bentuk Graf ........................................ 69

4.3 Mencari Rute Terpendek dengan Menggunakan Algoritma Djikstra..... 75

4.3.1 Rute Terdekat dari Tugu Khatulistiwa menuju Aloe Vera Center ..... 75

4.3.2 Rute Terdekat dari Tugu Khatulistiwa menuju Keraton Kadriah ...... 87

4.3.3 Rute Terdekat dari Tugu Khatulistiwa menuju Taman Alun Kapuas 90

4.3.4 Rute Terdekat dari Tugu Khatulistiwa menuju Rumah Radakng ...... 94

4.3.5 Rute Terdekat dari Aloe Vera Center menuju Tugu Khatulistiwa ..... 98

4.3.6 Rute Terdekat dari Aloe Vera Center Keraton Kadriah .................. 103

4.3.7 Rute Terdekat dari Aloe Vera Center menuju Taman Alun Kapuas 106

4.3.8 Rute Terdekat dari Aloe Vera Center menuju Rumah Radakng ...... 111

4.3.9 Rute Terdekat dari Keraton Kadriah menuju Aloe Vera Center ...... 117

4.3.10 Rute Terdekat dari Keraton Kadriah menuju Taman Alun Kapuas . 120

4.3.11 Rute Terdekat dari Keraton Kadriah menuju Tugu Khatulistiwa .... 123

4.3.12 Rute Terdekat dari Keraton Kadriah menuju Rumah Radakng ....... 129

4.3.13 Rute Terdekat dari Taman Alun Kapuas menuju Rumah Radakng . 133


xiv

4.3.14 Rute Terdekat dari Taman Alun Kapuas menuju Keraton Kadriah . 137

4.3.15 Rute Terdekat dari Taman Alun Kapuas menuju Aloe Vera Center 141

4.3.16 Rute Terdekat dari Taman Alun Kapuas menuju Tugu Khatulistiwa

146

4.3.17 Rute Terdekat dari Rumah Radakng menuju Taman Alun Kapuas . 150

4.3.18 Rute Terdekat dari Rumah Radakng menuju Keraton Kadriah ....... 154

4.3.19 Rute Terdekat dari Rumah Radakng menuju Aloe Vera Center ...... 157

4.3.20 Rute Terdekat dari Rumah Radakng menuju Tugu Khatulistiwa .... 162

4.4 Rute Terdekat dalam Mengunjungi 5 destinasi Wisata Populer .......... 167

4.4.1 Rute Terpendek dalam Mengunjungi 5 destinasi Wisata Populer di

Pontianak jika dimulai dari Tugu Khatulistiwa .......................................... 168


Pontianak jika dimulai dari Aloe Vera Center ........................................... 171


Pontianak jika dimulai dari Keraton Kadriah ............................................. 174


Pontianak jika dimulai dari Taman Alun Kapuas ....................................... 177


Pontianak jika dimulai dari Rumah Radakng ............................................. 180

4.4.4 Implementasi Teori Graf dalam Pembelajaran Matematika ............ 184

4.4.5 Keterbatasan Penelitian .................................................................. 184

BAB V ............................................................................................................. 185

PENUTUP ....................................................................................................... 185

5.1 Kesimpulan........................................................................................ 185

5.2 Saran ................................................................................................. 188

DAFTAR PUSTAKA ..................................................................................... xviii

LAMPIRAN ...................................................................................................... xx

A. Perhitungan Rute Terdekat dari Tugu Khatulistiwa menuju Aloe Vera Center

xx

B. Perhitungan Rute Terdekat dari Tugu Khatulistiwa menuju Keraton Kadriah

xxxiii


xv

C. Perhitungan Rute Terdekat dari Tugu Khatulistiwa menuju Taman Alun

Kapuas .................................................................................................................. l

D. Perhitungan Rute Terdekat dari Tugu Khatulistiwa menuju Rumah Radakng

lxix

E. Perhitungan Rute Terdekat dari Aloe Vera Center menuju Tugu Khatulistiwa

lxxxvii

F. Perhitungan Rute Terdekat dari Aloe Vera Center menuju Keraton Kadriah

civ

G. Perhitungan Rute Terdekat dari Aloe Vera Center menuju Taman Alun

Kapuas ............................................................................................................ cxxi

H. Perhitungan Rute Terdekat dari Aloe Vera Center menuju Rumah Radakng

cxl

I. Perhitungan Rute Terdekat dari Keraton Kadriah menuju Aloe Vera Center

clx

J. Perhitungan Rute Terdekat dari Keraton Kadriah menuju Taman Alun

Kapuas ......................................................................................................... clxxxi

K. Perhitungan Rute Terdekat dari Keraton Kadriah menuju Tugu

Khatulistiwa ....................................................................................................... cc

L. Perhitungan Rute Terdekat dari Keraton Kadriah menuju Rumah Radakng

ccxix

M. Perhitungan Rute Terdekat dari Taman Alun Kapuas menuju Rumah

Radakng...................................................................................................ccxxxviii

N. Perhitungan Rute Terdekat dari Taman Alun Kapuas menuju Keraton

Kadriah ........................................................................................................... cclv

O. Perhitungan Rute Terdekat dari Taman Alun Kapuas menuju Aloe Vera

Center cclxxiv

P. Perhitungan Rute Terdekat dari Taman Alun Kapuas menuju Tugu

Khatulistiwa .................................................................................................. ccxcii

Q. Perhitungan Rute Terdekat dari Rumah Radakng menuju Taman Alun

Kapuas ........................................................................................................... cccix

R. Perhitungan Rute Terdekat dari Rumah Radakng menuju Keraton Kadriah

cccxxiv

S. Perhitungan Rute Terdekat dari Rumah Radakng menuju Aloe Vera Center

cccxlii

T. Perhitungan Rute Terdekat dari Rumah Radakng menuju Tugu Khatulistiwa

ccclx


xvi

DAFTAR TABEL

Tabel 2.3. 1 Contoh Penamaan Vertex ............................................................... 18

Tabel 2.3. 2 Bobot Hubungan Masing-Masing Vertex ........................................ 21

Tabel 2.3. 3 D𝑣𝑗 pada iterasi ke-0 ...................................................................... 24







Tabel 2.3. 10 D𝑣𝑗 pada iterasi ke-7 .................................................................... 34



Tabel 2.3. 13 D𝑣𝑗 pada iterasi ke-10 .................................................................. 38















Tabel 2.3. 28 D𝑣𝑗 setiap iterasi .......................................................................... 52


xvii

Tabel 4.1. 1 Jumlah Potensi Wisata yang Telah Dikembangkan ......................... 67

Tabel 4.1. 2 Potensi Wisata yang Telah Dikembangkan Tahun 2013 .................. 67

Tabel 4.2. 1 Lokasi 5 Objek Wisata Terpilih Kota Pontianak ............................. 71

Tabel 4.2. 2 Nama Persimpangan dan Koordinat Google Maps .......................... 71

Tabel 4.2. 3 Nama Ruas Jalan ............................................................................ 73

Tabel 4.3. 1 Daftar Objek Wisata Awal dan Akhir ............................................. 75

Tabel 4.3.1. 1 D𝑣𝑗 pada iterasi ke-0 ................................................................... 78






Tabel 4.4. 1 Panjang Jalur antar Destinasi Wisata............................................. 167

Tabel 4.4. 2 Panjang Jalur Terpendek Dari 5 Pilihan Rute ................................ 183

Tabel 4.4.1. 1 Panjang Jalur antar Destinasi Wisata tanpa Tugu

Khatulistiwa ..................................................................................................... 169

Tabel 4.4.1. 2 Panjang Jalur antar Destinasi Wisata tanpa Tugu Khatulistiwa dan

Aloe Vera Center ............................................................................................. 169

Tabel 4.4.1. 3 Panjang Jalur antar Destinasi Wisata tanpa Tugu Khatulistiwa, Aloe

Vera Center, dan Keraton Kadriah ................................................................... 170

Tabel 4.4.1. 4 Panjang Jalur antar Destinasi Wisata tanpa Tugu Khatulistiwa, Aloe

Vera Center, Keraton Kadriah, dan T. Alun Kapuas ......................................... 171

Tabel 4.4.2. 1 Panjang Jalur antar Destinasi Wisata tanpa Aloe Vera Center .... 172

Tabel 4.4.2. 2 Panjang Jalur antar Destinasi Wisata tanpa Aloe Vera Center dan

Keraton Kadriah .............................................................................................. 172

Tabel 4.4.2. 3 Panjang Jalur antar Destinasi Wisata tanpa Aloe Vera Center,

Keraton Kadriah, dan Taman Alun Kapuas ...................................................... 173

Tabel 4.4.2. 4 Panjang Jalur antar Destinasi Wisata tanpa Aloe Vera Center,

Keraton Kadriah, Taman Alun Kapuas, dan Rumah Radakng ........................... 174

Tabel 4.4.3. 1 Panjang Jalur antar Destinasi Wisata tanpa Keraton Kadriah ...... 175


xviii

Tabel 4.4.3. 2 Panjang Jalur antar Destinasi Wisata tanpa Keraton Kadriah dan

Aloe Vera Center ............................................................................................. 175

Tabel 4.4.3. 3 Panjang Jalur antar Destinasi Wisata tanpa Keraton Kadriah, Aloe

Vera Center, dan Tugu Khatulistiwa ................................................................ 176

Tabel 4.4.3. 4 Panjang Jalur antar Destinasi Wisata tanpa Keraton Kadriah, Aloe

Vera Center, Tugu Khatulistiwa, dan Taman Alun Kapuas ............................... 177

Tabel 4.4.4. 1 Panjang Jalur antar Destinasi Wisata tanpa Taman Alun Kapuas 178

Tabel 4.4.4. 2 Panjang Jalur antar Destinasi Wisata tanpa Taman Alun Kapuas

dan Rumah Radakng ........................................................................................ 178

Tabel 4.4.4. 3 Panjang Jalur antar Destinasi Wisata tanpa Taman Alun Kapuas,

Rumah Radakng, dan Keraton Kadriah ............................................................ 179

Tabel 4.4.4. 4 Panjang Jalur antar Destinasi Wisata tanpa Taman Alun Kapuas,

Rumah Radakng, Keraton Kadriah, dan Aloe Vera Center ............................... 180

Tabel 4.4.5. 1 Panjang Jalur antar Destinasi Wisata tanpa Rumah Radakng ...... 181

Tabel 4.4.5. 2 Panjang Jalur antar Destinasi Wisata tanpa Rumah Radakng dan

Taman Alun Kapuas ........................................................................................ 181

Tabel 4.4.5. 3 Panjang Jalur antar Destinasi Wisata tanpa Rumah Radakng,

Taman Alun Kapuas, dan Keraton Kadriah ...................................................... 182

Tabel 4.4.5. 3 Panjang Jalur antar Destinasi Wisata tanpa Rumah Radakng,

Taman Alun Kapuas, Keraton Kadriah, dan Aloe Vera Center ......................... 183


xix

DAFTAR GAMBAR

Gambar 2.1. 1 Graf G(V,E) ................................................................................. 9

Gambar 2.1. 2 Graf G(V,E) ............................................................................... 10

Gambar 2.1. 3 Graf G(V,E) ............................................................................... 11

Gambar 2.1. 4 Graf G(V,E) ............................................................................... 12

Gambar 2.2. 1 .................................................................................................... 14

Gambar 2.3. 1 Jalur Kendaraan pribadi antara Kampus III USD dan Adisucipto

Internasional Airport ................................................................... 17

Gambar 2.3. 2 Panjang Lintasan Antar Lokasi Acuan......................................... 18

Gambar 2.3. 3 Graf Rute Kendaraan Pribadi dari Kampus III USD ke Adisucipto

Internasional Airpot .................................................................... 20

Gambar 4.2. 1 Peta 5 Destinasi Objek Wisata di Kota Pontianak ....................... 70

Gambar 4.2. 2 Graf Berarah dan Berbobot Jalan 5 objek Wisata Kota

Pontianak .................................................................................... 74

Gambar 5. 1 Representasi Graf G ..................................................................... 185


1

BAB I

PENDAHULUAN

1.1 Latar Belakang

Pariwisata merupakan salah satu yang dapat menjadi ciri khas suatu

daerah itu sendiri. Menurut Undang Undang No 10 tahun 2009 tentang

kepariwisataan, pariwisata adalah berbagai macam kegiatan wisata dan

didukung berbagai fasilitas serta layanan yang disediakan masyarakat,

pengusaha, Pemerintah dan Pemerintah daerah. Dengan adanya pariwisata

mampu menambah pendapatan ekonomi daerah. Dari banyaknya objek wisata

yang sering dikunjungi oleh para wisatawan asing dan juga dosmetik dapat

menjadi sumber pendapatan daerah tersebut. Guna menunjang pendapatan

daerah sektor pariwisata perlu dibutuhkan informasi mengnai jalur terpendek

dan mudah diakses para wisatawan.

Sebagai ibukota Provinsi Kalimantan Barat, Kota Pontianak memiliki

banyak predikat seperti kota budaya dan kota pariwisata. Predikat ini

menggambarkan keadaan Kota Pontianak dimana letak Kalimantan Barat yang

berbatasan langsung dengan Malaysia dan pulau kalimantan juga berbatasan

langsung dengan Brunei Darussalam. Pariwisata Kota Pontianak didukung oleh

keanekaragaman budaya penduduk Pontianak, yaitu Dayak, Melayu,

dan Tionghoa. Suku Dayak memiliki pesta syukur atas kelimpahan panen yang

disebut Gawai dan masyarakat Tionghoa memiliki kegiatan pesta tahun

baru Imlek, Cap Go Meh, dan perayaan sembahyang kubur (Cheng Beng atau

Ciet) yang memiliki daya tarik bagi para turis. Kota Pontianak juga dilintasi

oleh garis khatulistiwa yang ditandai dengan Tugu Khatulistiwa di Pontianak

Utara. Selain itu kota Pontianak juga memiliki visi menjadikan Pontianak

sebagai kota dengan pariwisata sungai. Sehingga Kota Pontianak memeiliki

banyak sekali tempat untuk di kunjungi bagi wisatawan baik dalam negeri

maupun luar negeri (Abdullah , 2016).

Pariwisata merupakan hal yang tidaklah asing bagi semua orang dan

merupakan bisnis yang besar, Industri pariwisata akan berkembang apabila


https://id.wikipedia.org/wiki/Dayakhttps://id.wikipedia.org/wiki/Melayuhttps://id.wikipedia.org/wiki/Tionghoahttps://id.wikipedia.org/wiki/Imlekhttps://id.wikipedia.org/wiki/Cap_Go_Meh

2

pertumbuhan pengunjung wisata yang terus meningkat akan memberi

kontribusi pendapatan ekonomi yang semakin meningkat , beberapa faktor

yang dapat menjamin industri paariwisata yaitu ketersediaan informasi tentang

pariwisata. Untuk berwisata yang harus ditentukan adalah jadwal berwisata,

setiap orang melakukan perjalanan pariwisata pasti memilih jarak terpendek

untuk dapat mencapai tujuan karena dapat menghemat waktu, tenaga dan biaya

bahan bakar ketika kita berwisata dengan jadwal yang tidak diatur, waktu dan

biaya tidak dapat dikontrol, Akibatnya ialah pengeluaran dari anggaran

berwisata menjadi membengkak, dan waktu berlibur yang menjadi padat.

Liburan merupakan salah satu cara yang dilakukan oleh seseorang

untuk menghilangkan rasa stress maupun kepenatan dalam kehidupan sehari-

hari. Biasanya seseorang berlibur memilih tempat yang sejuk dan nyaman.

Kota Pontianak merupakan salah satu tempat di Indonesia yang banyak

terdapat lokasi untuk berlibur, tentunya dengan banyak destinasi wisata

menarik yang layak untuk dikunjungi. Tempat-tempat menarik yang dapat

dikunjungi di Kota Pontianak di antaranya Taman Alun Kapuas. Karaton

Kadriyah Pontianak, Rumah Radang, Tugu Khatulistiwa, Digulis Monument,

Masjid Jami, Gereja Katedral St. Joseph, Museum Negeri Kalimantan Barat,

Masjid Raya Mujahidin, Aloe Vera Center. Namun dalam penelitian ini hanya

menggunakan 5 objek wisata, disesuaikan dengan data dari Dinas Pariwisata

Kota Pontianak 5 objek wisata yang dikembangkan sejak tahun 2009. Objek

wisaa yang dikembangkan menurut Dinas Pariwisata Kota Pontianak yaitu:

Tugu Khatulistiwa, Aloe Vera Center, Keraton Kadriah, Taman Alun Kapuas

dan Rumah Radakng.

Dari permasalahan dalam menentukan lokasi wisata yang berada di

Kota Pontianak maka penulis membuat sistem pencarian jalur terpendek dan

rekomendasi objek wisata, yang diharapkan dapat membantu menentukan jalur

objek wisata lain yang dapat dijadikan untuk mengatur jadwal dari berwisata

ataupun dapat digunakan menjadi bahan pertimbangan untuk menentukan

alternative lokasi obyek wisata yang satu arah atau yang lokasinya berdekatan,

sehingga menghemat waktu. Kesulitan menentukan jarak terpendek timbul


3

karena terdapat banyak jalur yang ada pada tiap daerah karena pada

kenyataannya misalnya salah satu contoh dari objek wisata di Pontianak yaitu

dari Gereja Katedral ke Rumah Radang tidak hanya dapat dilalui 1 jalur yaitu

dapat melalui 3 jalur yaitu : (1) Melalui jalan Sultan Abdurrahman yang

menempuh jarak 3,7 km dalam waktu 11 menit, (2) Melalui Jalan Alianyang

dengan jarak 4,8 km dalam waktu 14 menit (3) Melalui Jalan Putri Candramidi

yang menempuh jarak 5,1 km dalam waktu 15 menit, dengan ada 3 jalur yang

berbeda sehingga terbentuk suatu jaringan. Untuk membantu dalam

menentukan jarak terpendek dapat digunakan peta persebaran objek wisata dan

memilih mana jalur yang dianggap terpendek dari daerah asal ke daerah tujuan.

Namun hal ini dirasa kurang maksimal dan memperlambat waktu karena harus

memilih sendiri dari banyak jalur yang ada dan melakukan perhitungan sendiri

mana kira-kira jarak terpendek dari daerah asal menuju daerah tujuan yang

dikehendaki (Ardiani, 2011).

Pembelajaran matematika di sekolah dapat menjadikan pencarian rute

terpendek agar dapat meningkatkan minat siswa dengan matematika dengan

masalah nyata dalam kehidupan sehari hari. Sehingga dapat dirangsang dengan

permasalahan yang berkaitan denga teori graf. Matematika merupakan problem

posing dan problem solving. Dalam kegiatan bermatematika, pada dasarnya

anak akan berhadapan dengan dua hal yakni masalah-masalah apa yang

mungkin muncul atau diajukan dari sejumlah fakta yang dihadapi (problem

posing) serta bagaimana menyelesaikan masalah tersebut (problem solving).

Dalam kegiatan yang bersifat problem posing, anak memperoleh kesempatan

untuk mengembangkan kemampuannya mengidentifikasi fakta-fakta yang

diberikan serta permasalahan yang bisa muncul dari fakta-fakta tersebut.

Sedangkan melalui kegiatan problem solving, anak dapat mengembangkan

kemampuannya untuk menyelesaikan permasalahan tidak rutin yang memuat

berbagai tuntutan kemampuan berpikir termasuk yang tingkatannya lebih tinggi

(Suryadi, 2011)

Dari permasalahan dalam menentukan jalur terpendek, salah satu cara

untuk dapat menentukan jalur terpendek adalah dengan mengintepretasikan


4

peta kedalam suatu graf. Dalam graf, terdapat metode yang dapat digunakan

untuk menentukan jarak terpendek. Salah satu metode yang digunakan untuk

pencarian jalur terpendek adalah Algoritma Dijkstra. Algoritma ini digunakan

dalam graf berarah dimana setiap titik dihubungkan oleh sisi yang memiliki

bobot. Dengan memperhitungkan bobot pada setiap sisi, algoritma ini dapat

digunakan untuk menentukan jalur terpendek dari suatu titik ke titik akhir

tujuan (Puspika, dkk., 2012). Algoritma Dijkstra lebih intensif dalam

komputasi untuk pencarian jalur optimum dalam suatu jaringan seperti internet,

dan waktu rata-rata eksekusi algoritma Dijkstra lebih kecil dibanding algoritma

Ant Colony, maka algoritma Dijkstra banyak digunakan dalam pencarian jalur

optimum pada jaringan internet dibanding algoritma lain (Gusmão, dkk.,

2013:125). Algoritma ini biasanya diterapkan pada sebuah aplikasi pencari rute

jalan yang terdekat dari suatu daerah ke daerah lainnya. Algoritma ini dipilih

karena dapat menyelesaikan pencarian jalur terpendek dari satu simpul ke

semua simpul yang ada pada suatu graf berarah dengan bobot dan nilai tidak

negative sehingga nantinya dapat ditemukan jalur terpendek dari titik awal dan

titik tujuan yang dinputkan.

Dari penjelasan di atas penelitian ini tentunya akan berguna untuk

pembelajaran matematika disekolah, guna untuk mengetahui bahwa penerapan

matematika dikehidupan sehari-hari salah satu contohnya yaitu untuk mencari

jalur terpendek sehingga siswa dapat termotivasi untuk belajar matematika

karena penerapannya dalam kehidupan sehari-hari.

1.2 Rumusan Masalah

Berdasarkan latar belakang yang telah dijelaskan sebelumnya, rumusan

masalah yang akan dibahas pada penelitian ini adalah sebagai berikut:

1. Bagaimana memodelkan rute terpendek objek wisata Kota Pontianak yang

terdiri dari 5 objek wisata dalam bentuk graf?

2. Bagaimana menerapkan Algoritma Dijkstra dalam menentukan rute

terpendek objek wisata di Kota Pontianak?

3. Bagaimana menentukan rute terpendek dari beberapa tempat wisata Kota

Pontianak?


5

4. Bagaimana Implementasi dalam teori graf di pembelajaran matematika

disekolah untuk minat siswa?

1.3 Tujuan Penelitian

Sesuai dengan rumusan masalah yang dikemukanan diatas, maka tujuan

penelitian ini adalah antara lain :

1.1 Memodelkan rute terpendek objek wisata Kota Pontianak yang terdiri dari

10 objek wisata didalam graf

1.2 Membuat sistem pencarian jalur terpendek menggunakan Algoritma

Dijkstra untuk memudahkan wisatawan mengetahui objek wisata dan rute

terpendek dari tujuan objek wisata awal ke objek wisata selanjutnya di

kota Pontianak.

1.3 Memudahkan wisatawan untuk mengetahui objek wisata terdekat dari

posis dimana wisatawan berada.

1.4 Mengetahui implementasi teori graf disekolah walaupun sebagai dasar

sehingga menambah minat siswa.

1.5 Batasan Masalah

Batasan masalah dalam penelitian ini adalah :

1. Jalur yang dilalui searah.

2. Tempat wisata yang diteliti sebanyak 5 tempat.

3. Hanya akan menampilkan satu rute terpendek.

4. Pencarian rute terpendek menggunakan Algoritma Dijkstra

5. Ruang lingkup pengambilan data dan survei dilakukan di Dinas Pariwisata

Kota Pontianak.

6. Ruang lingkup untuk pengambilan data jarak lokasi diambil dari Google

Maps.

1.5 Manfaat Penelitian

Adapun manfaat yang diharapkan dari pelaksanaan penelitian ini adalah

sebagai berikut:

1.5.1 Bagi Peneliti

Penelitian ini memiliki manfaat bagi peneliti, yaitu:


6

1. Dapat menambah wawasan dan pengetahuan tentang masalah

pencarian rute terpendek.

2. Dapat mengetahui cara kerja pencarian rute terdekat menggunakan

metode Algoritma Dijkstra dalam kehidupan sehari-hari.

1.5.2 Bagi Universitas Sanata Dharma

Penelitian ini memiliki manfaat bagi Universitas Sanata Dharma, yaitu:

1. Sebagai bahan referensi untuk nantinya dapat dijadikan sebagai

acuan pada penelitian selanjutnya.

2. Dapat dijadikan tolak ukur keberhasilan akademik dalam mendidik

dan memberikan ilmu pengetahuan.

1.5.3 Bagi Wisatawan di Pontianak

1. Mempermudah wisatawan untuk mencari lokasi objek wisata

terdekat di Kota Pontianak

2. Mempersingkat waktu dan menghemat pengeluaran wisatawan.


7

1.5.4 Bagi Masyarakat Sekitar Objek Wisata

1. Pemilik unit usaha yang dilalui jalur terpendek lokasi wisata yang

dituju mendapat keuntungan dari wisatawan. Misalnya meliputi

warung jajanan, souvenir dan pusat oleh-oleh.

2. Meningkatkan pendapatan bagi pemilik unit usaha.

1.5.5 Bagi Sekolah

1. Dapat dijadikan contoh sebagai penelitian yang menerapkan ilmu

matematika di kehidupan sehari-hari dalam bidang pariwisata

khususnya mencari rute terpendek.

2. Siswa juga dapat mengenal dasar dalam mencari rute terpendek

yaitu teori graf.

1.6 Sistematika Penulisan

Sitematika penulisan skripsi ini secara garis besar adalah sebagai berikut:

BAB I PENDAHULUAN

Bab ini membahas tentang latar belakang dilakukannya penelitian,

rumusan masalah, tujuan dari penelitian, batasan-batasan masalah

dalam penelitian, manfaat dari penelitian, sistematika penulisan,

dan kerangka berpikir.

BAB II TINJAUAN PUSTAKA

Bab ini membahas tentang graf, representasi graf dalam matriks,

dan cara kerja Algoritma Dijkstra dalam menentukan rute

terpendek.

BAB III METODE ANALISIS

Bab ini berisi tentang metode yang digunakan dalam menentukan

rute terpendek objek wisata di Kota Pontianak.

BAB IV PEMODELAN RUTE OBJEK WISATA KOTA PONTIANAK

Bab ini membahas pemodelan rute terpendek dalam mengunjungi 5

objek wisata di Kota Pontianak kedalam simbol-simbol

matematika.

BAB V PENERAPAN ALGORITMA DIJSTRA


8

Bab ini berisi tentang penerapan Algoritma Dijstra dalam

menentukan rute terpendek objek wisata di Kota Pontianak.

BAB VI KESIMPULAN DAN SARAN

Bab ini berisi hasil yang diperoleh dari hasil analisis dan

perhitungan matematis dalam menentukan rute terpendek objek

wisata Kota Pontianak.


9

BAB II

TINJAUAN PUSTAKA

Pada bab ini akan dijelaskan menegai graf dan istilah-istilah dalam graf,

repesentasi graf dalam matriks, serta cara Algoritma Dijkstra untuk menentukan

rute terpendek.

2.1 Graf

Bagian ini akan menjelaskan istilah-istilah yang akan digunakan dalam

pembahasan suatu graf serta menjelaskan jeni-jenis graf jika digolongkan

pada suatu kriteria tertentu.

Definisi 2.1.1 (Rinaldi Munir, 2005:356)

Diberikan himpunan tak kosong V={𝑣1, 𝑣2, … . . 𝑣𝑛} adalah himpunan

titik-titik atau vertex dan diberikan himpunan E={𝑒1, 𝑒2, … . . , 𝑒𝑚} adalah

himpunan yang sisi-sisi atau edge yang menghubungkan sepasang vertex.

Suatu graf G adalah himpunan yang terdiri dari vertex dan edge yang

didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi

G=(V,E). Untuk selanjutnya akan digunakan istilah vertex sebagai titik dan

edge sebagai sisi

Contoh 2.1.1

Perhatikan gambar berikut!

Gambar 2.1. 1 Graf G(V,E)

Perhatikan gambar 2.1.1 𝑣1, 𝑣2, 𝑣3 𝑑𝑎𝑛 𝑣4 merupakan vertex pada graf

G sedangkan 𝑒1, 𝑒2, 𝑑𝑎𝑛 𝑒3 , 𝑒4 pada graf G adalah sisi yang menghubungkan

sepasang vertex yang disebut dengan edge.


10

Definisi 2.1.2 (Lipschutz and Lipson, 2002)

Jika edge yang menghubungkan vertex pada graf G, maka vertex 𝑣1,

dikatakan Berhubungan atau adjacent terhadap vertex 𝑣2. Kemudian vertex

𝑣1dan 𝑣2 tersebut dikatakan Bersinggungan atau incidence dengan edge

yang menghubungan 𝑣1dan 𝑣2.

Contoh 2.1.2

Perhatikan gambar 2.1.1 graf G dengan 𝑒1 incidence pada vertex

𝑣1dan 𝑣2, serta 𝑣1dan 𝑣2 adjacent.

Definisi 2.1.3 (Jong Jek Siang, 2011: 268)

Edge yang hanya berhubungan dengan satu vertex disebut Loop.

Sedangkan pada suatu graf G dua edge yang berbeda yang menghubungkan

dua vertex yang sama disebut Multiple Edges atau Sisi Paralel

Contoh 2.1.3



Perhatikan gambar 2.1.2. edge 𝑒1 disebut sebagai loop. Kemudian,

vertex 𝑣1 dan 𝑣3 yang dihubungkan oleh edge 𝑒5 dan 𝑒4, maka edge 𝑒5 dan 𝑒4

merupakan sisi paralel.

Definisi 2.1.4 (Rinaldi Munir, 2005:357)

Diberikan graf G dibedakan menjadi 2 jenis berdasarkan:

1. Graf Sederhana atau simple graph, yaitu graf yang tidak mengandung

loop maupun sisi pararel.


11

2. Graf tak-sederhana atau un-simple graph , yaitu graf yang mengandung

Loop maupun sisi pararel.

Contoh 2.1.4

Perhatikan gambar 2.1.1 adalah contoh Graf sederhana atau simple

graph karena tidak mengandung Loop maupun Sisi Paralel. Kemudian

perhatikan gambar 2.1.2 adalah contoh un-simple graph karena mengandung

Sisi Paralel atau juga mengandung Loop.

Definisi 2.1.5 (Jong Jek Siang, 2011:268)

Graf terbagi menjadi dua jenis jika dibedakan berdasarkan arah

sisinya, yaitu:

1. Graf Berarah, yaitu graf G yang setiap edge pada graf tersebut memiliki

arah yang menunjukan titik asal dan titik tujuan.

2. Graf Tak Berarah, yaitu graf G yang setiap edge pada graf tersebut

tidak memiliki arah yang menunjukan titik asal dan titik tujuan, sehingga

hanya merupakan ruas garis yang menghubungkan dua edge.

Contoh 2.1.5



Perhatikan gambar 2.1.3 merupakan graf berarah karena setiap edge

pada graf tersebut memiliki arah yang menunjukan titik asal dan titik tujuan.

Sedangkan perhatikan gambar 2.1.2 graf G merupakan graf tidak berarah

karena setiap edge pada graf tersebut tidak memiliki arah.


12


Berdasarkan label garisnya , graf terbagi menjadi dua yaitu:

1. Graf Berlabel, yaitu graf G yang setiap edge diasosiasikan dengan suatu

bilangan riil yang menunjukan bobot hubungan antar kedua vertex.

2. Graf Tak Berlabel, yaitu graf G yang menghubungkan kedua vertex

(baik dalam graf berarah maupun tak berarah) tidak menyatakan bobot

atau kualitas hubungan tersebut.

Contoh 2.1.6



Pada gambar 2.1.4 merupakan graf berlabel karena setiap edge dari

graf tersebut terdapat suatu bilangn riil yang mempresentasikan label dari

setiap edge tersebut. Sedangkan pada gambar 2.1.3 merupakan graf tak

berlabel karena setiap edge dari graf tidak terdapat suatu bilang riil yang

merepresentasikan label dari setiap edge tersebut.


Misalkan v adalah vertex dalam suatu graf G. Derajat atau degree

vertex v adalah jumlah edge yang berhubungan dengan vertex v dan edge

suatu loop dihitung dua kali.

Contoh 2.1.7

Perhatikan gambar 2.1.3. derajat dari titik 𝑣1 adalah 3 yang dituliskan

sebagai d(𝑣1) = 3 karena terdapat 3 sisi yang terhubung dengan titik yaitu


13

𝑒5, 𝑒4 𝑑𝑎𝑛 𝑒3 . derajat dari titik 𝑣4 adalah 3 yang dituliskan sebagai d(𝑣4) = 3

karena terdapat 3 sisi yang terhubung dengan titik 𝑣4 yaitu 𝑒6, 𝑒2 𝑑𝑎𝑛 𝑒7.

Sedangkan derajat titik 𝑣2 adalah 4 yang ditulis sebagai d(𝑣2) = 4 karena

terdapat 2 sisi yang terhubung dengan titik 𝑣2 yaitu 𝑒3 dan 𝑒2, serta loop 𝑒1

yang dihitung dua kali.


Misalkan G adalah suatu graf yang memiliki vertex dan edge.

1. Walk adalah barisan berhingga dari vertex dan edge, dimulai dan diakhiri

dengan vertex, sedemikian sehingga setiap edge yang menempel dengan

vertex sebelum dan sesudahnya. Tidak ada edge yang muncul lebih dari

sekali dalam satu walk. Sedangkan vertex mungkin muncul lebih dari

satu kali.

2. Walk Berarah tidak jauh berbeda dari walk, hanya saja dalam

menentukan barisannya harus memperhatikan dan mengikuti arah dari

graf tersebut.

Contoh 2.1.8

Perhatikan gambar 2.1.3. walk dari 𝑣1 ke 𝑣4 adalah

𝑣1𝑒5𝑣3𝑒4𝑣1𝑒3𝑣2𝑒1𝑣2𝑒2𝑣4 . Pada suatu walk, suatu edge boleh dilalui lebih

dari sekali.


Lintasan atau path dari v ke w adalah walk dari v ke w yang tidak

memiliki sisi berulang.

Contoh 2.1.9

Pada gambar 2.1.2 lintasan dari 𝑣3 ke 𝑣4 adalah 𝑣3𝑒6𝑣4𝑒7𝑣5

perhatikan bahwa lintasan 𝑣3 ke 𝑣4 tidak memiliki edge berulang.

2.2 Representasi Graf dalam Matriks

Matriks adalah susunan bilangan-bilangan yang disusun dalam bentuk

persegi panjang dan diatur menurut baris dan kolom (Sulistyono, 2007: 59).

Matriks dapat merepresentasikan suatu graf. Menurut Siang (2011: 286), graf

yang diubah kedalam bentuk matriks dapat mempermudah perhitungan-


14

perhitungan yang diperlukan, dan matriks digunakan untuk

merepresentasikan suatu graf pada umumnya adalah Matriks Hubung atau

Adjacency Matrix.


𝑣1 : 𝑣2, 𝑣6

𝑣2 : 𝑣1, 𝑣3

𝑣3 : 𝑣2, 𝑣4

𝑣4 : 𝑣3, 𝑣5

𝑣5 : 𝑣4, 𝑣6

𝑣6 : 𝑣1, 𝑣5

Gambar 2.2. 1

Dari gambar diatas, bila G adalah sebuah graf tanpa loop, dengan

vertex V={𝑣1, 𝑣2, … . . 𝑣𝑛}, matriks hubung adjacency matrix. Misalkan 𝐴𝑛 𝑥 𝑛

adalah matriks berordo n x n, elemen matriks A yaitu 𝑎𝑖𝑗 adalah bilangan

yang menyatakan jumlah rusuk yang menghubungkan i dan j dengan i, j =

1,2,3,..,n merepresentasikan hubungan antara baris.

2.3 Algoritma Dijkstra

Menurut Siang (2011: 299), Algoritma Dijstra merupakan algoritma

yang ditemukan oleh Edsger W. Dijkstra untuk mencari jalur terpendek pada

sebuah graf antara 2 titik. Misalkan G adalah graf berlabel (berarah atau tidak

berarah) dengan vertex V={𝑣1, 𝑣2, … . . 𝑣𝑛} dan lintasan terpendek yang dicari

adalah dari 𝑣1 ke 𝑣𝑛. Algoritma Dijkstra dimulai dari titik 𝑣1. Dalam

iterasinya, algoritma akan mencari satu titik yang jumlah bobotnya dari vertex

1 terkecil. Vertex yang terpilih dipisahkan (disebut vertex permanen), dan

vertex tersebut tidak diperhatikan lagi dalam iterasi berikutnya.

Misalkan V(G) adalah himpunan vertex yang ada pada graf G yaitu

V={𝑣1, 𝑣2, … . . 𝑣𝑛} , L merupakan himpunan vertex pada V(G) yang sudah


15

terpilih menjadi vertex permanen dalam jalur lintasan terpendek, D(𝑣𝑗)

merupakan jumlah bobot lintasan terkecil dari 𝑣1 ke 𝑣𝑗 , W merupakan

matriks hubung yang merepresentasikan graf, dan W(i,j) adalah bobot edge

dari vertex 𝑣𝑖 ke 𝑣𝑗. Sekarang jika kita akan menentukan jalur terpendek dari

𝑣𝑎 ke 𝑣𝑛, maka langkah kerja Algoritma Dijkstra menrut jong Jek Siang

(2011: 299) adalah sebagai berikut:

1. Menentukan 𝑣𝑎 sebagai titik awal dan 𝑣𝑛 sebagai titik akhir.

2. Menentukan tabel representasi dari graf

3. Membuat matriks hubung W.

4. Untuk iterasi pertama, lakukan:

a. Inisialisasi :

L = { }

V(G) ={𝑣1, 𝑣2, … . . 𝑣𝑛}

b. Titik awal adalah 𝑣𝑎 maka lakukan D(𝑣𝑗) = {0 , 𝑗 = 𝑖∞ , 𝑗 ≠ 𝑖

, ∀𝑣𝑗 ∈ V(G).

c. ∀𝑣𝑗 ∈ V(G), tentukan D(𝑣𝑗) terkecil, maka titik permanen 𝑣𝑝 adalah

𝑣𝑗.

d. L = L ∪ {𝑣𝑝}

e. Jika vn ∈ L maka iterasi berhenti, jika vn ∉ 𝐿 maka iterasi

berlanjut.

5. Untuk iterasi kedua dan seterusnya, lakukan:

a. Inisialisasi :

L = L

V(G) = V(G) – {𝑣𝑝}

b. ∀𝑣𝑗 ∈ V(G), lakukan D(𝑣𝑗)=min(D(𝑣𝑗), D(𝑣𝑝)+ W(p,j))


𝑣𝑗.

d. L = L ∪ {𝑣𝑝}


berlanjut.


16

6. Tuliskan D(𝑣𝑗) untuk j = 1,2,3,...,n pada setiap ietrasi diatas kedalam

tabel.

7. Tentukan lintasan terpendeknya dengan mendaftar titik permanen pada

tabel diatas mulai dari iterasi terakhir hingga iterasi pertama. Perhatikan

titik permanen 𝑣𝑗 pada iterasi ke-i , apabila D(𝑣𝑗) pada iterasi ke-i

mengalami penurunan dibandingkan D(𝑣𝑗) pada iterasi sebelumnya,

maka titik permanen pada iterasi ke-i tersebut merupakan jalur yang

harus dilalui.

8. Panjanglintasan dari 𝑣𝑎 ke 𝑣𝑛 adalah D(𝑣𝑝) pada iterasi terakhir

9. Interpretasi

Contoh 2.3.1

Berikut adalah contoh perhitungan penerapan Algoritma Djikstra

untuk menentukan rute terpendek dari Kampus III Universitas Sanata Dharma

ke Adisucipto International Airport.

Pertama berdasarkan rute yang dipilih Google Maps kita peroleh peta

yang menghubungkan Kampus III Universitas Sanata Dharma Yogyakarta

dengan Adisucipto International Airport adalah sebagai berikut:


17

Gambar 2.3. 1 Jalur Kendaraan pribadi antara Kampus III USD dan

Adisucipto Internasional Airport

Berdasarkan gambar tersebut, terdapat beberapa rute yang dapat

dilalui untuk pergi ke Adisucipto International Airport dari Kampus III

Universitas Sanata Dharma. Berdasarkan rute tersebut, terdapat beberapa titik

lokasi acuan yang artinya adalah sebagai berikut:

1 = Universitas Sanata Dharma

2 = Perumahan Taman Cemara

3 = Jalan Timbulrejo

4 = Jalan Sabo

5 = Kementrian Pekerjaan Umum

6 = Perempatan Pasar Stan

7 = Pertigaan Jalan Persada

8 = Sawo Kembar Yogya Guest House

9 = Gapura Sanata Dharma Yogyakarta

10 = SMK YPKK 3 Sleman

11 = MIG Aquarium

12 = Pertamina Petrol Station

13 = Halte TJ RRU (Binamarga)

14 = Perempatan Jalan Melati dan Jalan Kenari

15 = Angkringan Naura

16 = Jalan Riang Gembira

17 = Jalan Kenanga

18 = Warung Lotek Bu Suwarjinah

19 = Jalan Flamboyan

20 = Pertigaan Jalan Anggrek

21 = Pertigaan Jalan Raya Solo

22 = Pertigaan Jalan Widoro Kandang

23 = Bakpian Kukus Tugu Jogja Raya Solo

24 = Pertigaan Adisucipto Internasional Airport


18

25 = Adisucipto Internasional Airport

Kemudian, jarak antara setiap titik acuan pada peta tersebut dijelaskan pada

gambar berikut:

Gambar 2.3. 2 Panjang Lintasan Antar Lokasi Acuan

Gambar 2.3.1 merupakan gambar peta yang menghubungkan kampus

III Universitas Sanata Dharma ke Adisucipto International Airport yang

disertai gambar 2.3.2 yang merupakan panjang lintasan antar lokasi acuan.

Selanjutnya, lokasi-lokasi tersebut kita simbolkan sebagai titik dengan

penamaan sebagai berikut:

Tabel 2.3. 1 Contoh Penamaan Vertex

Nama Lokasi Vertex

Universitas Sanata Dharma 𝑣1

Perumahan Taman Cemara 𝑣2

Jalan Timbulrejo 𝑣3

Jalan Sabo 𝑣4

Kementrian PV 𝑣5

Perempatan Pasar Stan 𝑣6

Pertigaan Jalan Persada 𝑣7


19

Sawo Kembar 𝑣8

Gapura Sadar 𝑣9

SMK YPKK 3 Sleman 𝑣10

MIG Aquarium 𝑣11

Pertamina Petrol Station 𝑣12

Halte TJ RRU 𝑣13

Perempatan Jalan Melati 𝑣14

Angkringan Naura 𝑣15

Jalan Riang Gembira 𝑣16

Jalan Kenanga 𝑣17

Warung Lotek Bu Suwarjinah 𝑣18

Jalan Flamboyan 𝑣19

Pertigaan Jalan Anggrek 𝑣20

Pertigaan Jalan Raya Solo 𝑣21

Pertigaan Jalan Widoro Kandang 𝑣22

Bakpia Kukus Jogja 𝑣23

Pertigaaan Bandara 𝑣24

Adisucipto Internasional Airport 𝑣25

Kemudian peta pada gambar 2.3.1 diubah kedalam bentuk graf agar

dapat dianalisis secara matematis. Berikut adalah graf yang

merepresentasikan Peta Kampus III dengan Adisucipto Internasional Airport:


20

Gambar 2.3. 3 Graf Rute Kendaraan Pribadi dari Kampus III USD ke

Adisucipto Internasional Airpot


21

Selanjutnya, kita akan menggunakan Algoritma Djikstra untuk menentukan rute terpendek dari Kampus III Universitas

Sanata Dharma ke Adisucipto Internasional Airport

1. Menentukan 𝑣𝑎 sebagai vertex awal dan 𝑣𝑛 sebagai vertex akhir.

Yaitu 𝑣𝑎 adalah 𝑣1 dan 𝑣𝑛 adalah 𝑣25.

2. Membuat table representasi dari graf

Tabel 2.3. 2 Bobot Hubungan Masing-Masing Vertex

𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣6 𝑣7 𝑣8 𝑣9 𝑣10 𝑣11 𝑣12 𝑣13 𝑣14 𝑣15 𝑣16 𝑣17 𝑣18 𝑣19 𝑣20 𝑣21 𝑣22 𝑣23 𝑣24 𝑣25

𝑣1 0 550 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣2 550 0 190 ∞ ∞ ∞ ∞ ∞ 500 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣3 ∞ 190 0 230 ∞ ∞ 250 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣4 ∞ ∞ 230 0 230 ∞ ∞ 350 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣5 ∞ ∞ ∞ 230 0 500 ∞ 290 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣6 ∞ ∞ ∞ ∞ 500 0 ∞ ∞ ∞ ∞ ∞ 600 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣7 ∞ ∞ 250 ∞ ∞ ∞ 0 300 ∞ 280 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣8 ∞ ∞ ∞ 350 290 ∞ 300 0 ∞ ∞ 290 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣9 ∞ 500 ∞ ∞ ∞ ∞ ∞ ∞ 0 200 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣10 ∞ ∞ ∞ ∞ ∞ ∞ 280 ∞ 200 0 200 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣11 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 290 ∞ 200 0 900 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣12 ∞ ∞ ∞ ∞ ∞ 600 ∞ ∞ ∞ ∞ 900 0 900 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣13 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 900 0 150 ∞ 400 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣14 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 150 0 350 ∞ 350 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

𝑣15 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 350 0 ∞ ∞ 350 ∞ ∞ ∞ ∞ ∞ ∞ ∞


22

𝑣16 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 400 ∞ ∞ 0 150 ∞ ∞ ∞ 350 ∞ ∞ ∞ ∞

𝑣17 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 350 ∞ 150 0 210 450 ∞ ∞ ∞ ∞ ∞ ∞

𝑣18 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 350 ∞ 210 0 ∞ 400 ∞ ∞ ∞ ∞ ∞

𝑣19 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 450 ∞ 0 400 ∞ ∞ ∞ ∞ ∞

𝑣20 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 400 400 0 ∞ ∞ 80 ∞ ∞

𝑣21 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 350 ∞ ∞ ∞ ∞ 0 130 ∞ ∞ ∞

𝑣22 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 130 0 69 ∞ ∞

𝑣23 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 80 ∞ 69 0 230 ∞

𝑣24 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 230 0 500

𝑣25 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 500 0


23

3. Membuat Matriks hubung W

𝑊 =

(

0550 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

5500

190 ∞∞∞∞∞500∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞ 190 0230∞∞250∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞ 230 0230∞∞350 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞2300500∞290 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞∞ 5000∞∞∞∞∞600 ∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞250∞∞∞0300∞ 280 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞350290∞3000∞∞290∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞500 ∞∞∞∞∞∞0 200∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞∞∞∞280∞200 0200∞∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞290∞ 2000900∞∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞∞∞600∞∞∞∞ 9000900∞∞∞∞∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞9000 150∞400∞∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞ 1500350∞350∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞ 3500∞∞350∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞400∞∞0 150∞∞∞350∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞350∞150 0210450∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞350∞2100∞400∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ 450∞0400∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ 400 4000∞∞80∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞350∞∞∞∞0130∞∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ 130 069∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ 80∞690∞∞

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ 230 0500

∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞5000 )


24

4. Untuk Iterasi pertama, lakukan :

Iterasi 0

a. Inisialisasi:

L = { }

V(G) ={𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10, 𝑣11}

b. Titik awal adalah 𝑣𝑎 maka lakukan D(𝑣𝑗) = {0 , 𝑗 = 𝑖∞ , 𝑗 ≠ 𝑖

, ∀𝑣𝑗 ∈ V(G).

Karena titik awal adalah 𝑣1 maka:

Tabel 2.3. 3 D(𝒗𝒋) pada iterasi ke-0

D(𝑣1) = 0 D(𝑣6) = ∞ D(𝑣11) = ∞ D(𝑣16) = ∞ D(𝑣21) = ∞

D(𝑣2) = ∞ D(𝑣7) = ∞ D(𝑣12) = ∞ D(𝑣17) = ∞ D(𝑣22) = ∞

D(𝑣3) = ∞ D(𝑣8) = ∞ D(𝑣13) = ∞ D(𝑣18) = ∞ D(𝑣23) = ∞

D(𝑣4) = ∞ D(𝑣9) = ∞ D(𝑣14) = ∞ D(𝑣19) = ∞ D(𝑣24) = ∞

D(𝑣5) = ∞ D(𝑣10) = ∞ D(𝑣15) = ∞ D(𝑣20) = ∞ D(𝑣25) = ∞


𝑣𝑗.

D(𝑣𝑗) terkecil adalah D(𝑣1) = 0

Maka titik permanen 𝑣𝑝 adalah 𝑣1

d. L = L ∪ {𝑣𝑝}

L = {𝑣1}


berlanjut.

𝑣25 ∉ L maka iterasi berlanjut


Iterasi 1

a. Inisialisasi:

L = L

L = {𝑣1}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15,

𝑣16, 𝑣17, 𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}


25


26



D(𝑣𝑗)=min(D(𝑣𝑗), D(𝑣𝑝)+ W(p,j)) D(𝑣𝑗)

D(𝑣2)=min(∞, 0+ 550) = min(∞, 550) = 550 550

D(𝑣3)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣4)= min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣5)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣6)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣7)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣8)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣9)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣10)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣11)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 0+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.




27

d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2}


berlanjut.



Iterasi 2

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16,

𝑣17, 𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣3)=min(∞, 550+ 190) = min(∞, 740) = 740 740

D(𝑣4)= min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣5)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣6)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣7)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣8)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣9)=min(∞, 550+ 500) = min(∞, 500) = 1050 1050

D(𝑣10)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣11)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞


28

D(𝑣18)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3}


berlanjut.


7. Untuk iterasi ke-3 dan seterusnya, lakukan:

Iterasi 3

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣4, 𝑣5, 𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣4)= min(∞, 740+ 230) = min(∞, 970) = 970 970

D(𝑣5)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞


29

D(𝑣6)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣7)=min(∞, 740+ 250) = min(∞, 990) = 990 990

D(𝑣8)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣9)=min(1240, 740+ ∞) = min(1240,∞) =1240 1240

D(𝑣10)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣11)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 740+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 550+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4}


berlanjut.



Iterasi 4

a. Inisialisasi:


30

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣5, 𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣5)=min(∞, 970+ 230) = min(∞, 1200) = 1200 1200

D(𝑣6)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣7)=min(990, 970+∞ ) = min(990,∞) = 990 990

D(𝑣8)=min(∞, 970+ 350) = min(∞, 1320) = 1320 1320

D(𝑣9)=min(1240, 970+ ∞) = min(1240,∞) =1240 1240

D(𝑣10)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣11)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



31


d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7}


berlanjut.



Iterasi 5

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣5, 𝑣6, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17, 𝑣18,

𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣5)=min(1200, 970 ) = min(1200,∞) = 1200 1200

D(𝑣6)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣8)=min(1320, 970+ 300) = min(1320,1270) = 1270 1270

D(𝑣9)=min(1240, 970+ ∞) = min(1240,∞) =1240 1240

D(𝑣10)=min(∞, 970+ 280) = min(∞, 1250) = 1250 1250

D(𝑣11)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞


32

D(𝑣23)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 970+ ∞) = min(∞,∞) = ∞ ∞


33


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7, 𝑣5}


berlanjut.



Iterasi 6

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7, 𝑣5}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣6, 𝑣8, 𝑣9, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣6)=min(∞, 1200+ 500) = min(∞, 1700) = 1700 1700

D(𝑣8)=min(1320, 1200+290 ) = min(1320,1490) = 1320 1320

D(𝑣9)=min(1240, 1200+ ∞) = min(1240,∞) =1240 1240

D(𝑣10)=min(1250, 1200+ ∞) = min(1250,∞) = 1250 1250

D(𝑣11)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞


34

D(𝑣20)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 1200+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7, 𝑣5, 𝑣9}


berlanjut.



Iterasi 7

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7, 𝑣5, 𝑣9}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣6, 𝑣8, 𝑣10, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣6)=min(1700, 1240+ ∞) = min(1700,∞) = 1700 1700

D(𝑣8)=min(1320, 1240+∞ ) = min(1320,∞) = 1320 1320

D(𝑣10)=min(1250, 1240+ 200) = min(1250,1440) = 1250 1250

D(𝑣11)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣12)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞


35

D(𝑣15)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 1240+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7, 𝑣5, 𝑣9, 𝑣10}


berlanjut.



Iterasi 8

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7, 𝑣5, 𝑣9, 𝑣10}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣6, 𝑣8, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣6)=min(1700, 1250+ ∞) = min(1700,∞) = 1700 1700

D(𝑣8)=min(1320, 1250+∞ ) = min(1320,∞) = 1320 1320


36

D(𝑣11)=min(∞, 1250+ 200) = min(∞, 1450) = 1450 1450

D(𝑣12)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 1250+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7, 𝑣5, 𝑣9, 𝑣10, 𝑣8}


berlanjut.



Iterasi 9

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7, 𝑣5, 𝑣9, 𝑣10, 𝑣8}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣6, 𝑣11,𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}



37



D(𝑣6)=min(1700, 1320+ ∞) = min(1700,∞) = 1700 1700

D(𝑣11)=min(1450, 1320+ 290) = min(1450,1610) = 1450 1450

D(𝑣12)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣13)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣17)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣18)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣19)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣20)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣21)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣22)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣23)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣24)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣25)=min(∞, 1320+ ∞) = min(∞,∞) = ∞ ∞


𝑣𝑗.



d. L = L ∪ {𝑣𝑝}

L = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣7, 𝑣5, 𝑣9, 𝑣10, 𝑣8, 𝑣11}


berlanjut.



Iterasi 10

a. Inisialisasi:

L = L

L = {𝑣1, 𝑣2, 𝑣3,𝑣4,𝑣7, 𝑣5, 𝑣9, 𝑣10, 𝑣8, 𝑣11}

V(G) = V(G) – {𝑣𝑝}

V(G) ={𝑣6, 𝑣12, 𝑣13, 𝑣14, 𝑣15, 𝑣16, 𝑣17,


38

𝑣18, 𝑣19, 𝑣20, 𝑣21,𝑣22, 𝑣23, 𝑣24, 𝑣25}




D(𝑣6)=min(1700, 1450+ ∞) = min(1700,∞) = 1700 1700

D(𝑣12)=min(∞, 1450+ 900) = min(∞, 2350) = 2350 2350

D(𝑣13)=min(∞, 1450+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣14)= min(∞, 1450+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣15)=min(∞, 1450+ ∞) = min(∞,∞) = ∞ ∞

D(𝑣16)=min(∞, 1450+ ∞) = min(∞,

implementasi algoritma dijkstra dalam menentukan...

Documents