Analisis Perbandingan

Algoritma Depth First Search dengan Algoritma

Dijkstra dalam Menentukan Jalur Terpendek

Tempat Wisata di Kota Surakarta

Artikel Ilmiah

Peneliti:

Joshua Nandhika Hutama (672014038)

Dr. Kristoko Dwi Hartomo, M.Kom.

Program Studi Teknik Informatika

Fakultas Teknologi Informasi

Universitas Kristen Satya Wacana

Salatiga

Januari 2018

Analisis Perbandingan

Algoritma Depth First Search dengan Algoritma

Dijkstra dalam Menentukan Jalur Terpendek

Tempat Wisata di Kota Surakarta

Artikel Ilmiah

Diajukan kepada

Fakultas Teknologi Informasi

untuk memperoleh Gelar Sarjana Komputer

Peneliti:

Joshua Nandhika Hutama (672014038)

Dr. Kristoko Dwi Hartomo, M.Kom.

Program Studi Teknik Informatika

Fakultas Teknologi Informasi

Universitas Kristen Satya Wacana

Salatiga

Januari 2018

1

1. Pendahuluan

Dalam mencari dan menentukan jalur terpendek yang akan dilalui, ada

beberapa metode yang dapat digunakan. Masing-masing algoritma tersebut

mempunyai kelebihan dan kelemahan yang berbeda. Metode dengan tingkat

keakuratan yang tinggi tentu menjadi algoritma yang paling baik untuk digunakan.

Saat ini berlibur adalah hal yang paling sering dilakukan oleh banyak orang. Tempat

wisata yang menarik tentu menjadi tujuan utama, namun sering kali untuk menuju

ke suatu tempat wisata tidaklah mudah, ada beberapa pilihan jalan yang dapat

dilalui. Seringkali orang-orang yang melakukan perjalanan ke tempat wisata

tersebut menggunakan kendaraan pribadi, dimana banyak dari wisatawan yang

berkunjung tidak begitu mengetahui kondisi jalanan yang ada dan seberapa jauh

jarak yang harus ditempuh. Beberapa orang beranggapan bahwa titik termudah

untuk menemukan tempat wisata adalah dengan mencari tempat transportasi umum.

Hal ini karena tempat transportasi umum sering dibangun dekat dengan tempat-

tempat yang ramai termasuk tempat wisata. Kota Surakarta memiliki beberapa

tempat wisata yang cukup sering dikunjungi dan memiliki akses yang cukup banyak

dari tempat transportasi umum yang ada. Untuk itu, penerapan algoritma pencarian

yang tepat tentu akan sangat membantu dalam menentukan jalur terpendek yang

akan dilalui. Selain itu, dalam menentukan suatu algoritma yang baik untuk

melakukan jalur terpendek, masalah yang paling sering adalah algoritma mana yang

mampu meminimalkan jumlah bobot graf jalur yang saling terhubung namun

dengan cara kerja algoritma yang berbeda [1]. Algoritma Depth First Search dan

Dijkstra menjadi metode yang cukup baik untuk diterapkan karena algoritma Depth

First Search adalah algoritma pencarian tanpa adanya informasi awal yang

diketahui (blind search), sedangkan algoritma Dijkstra adalah algoritma pencarian

dimana semua informasi awal sudah diketahui. Selain itu. Dalam menentukan nilai

optimal dari suatu algoritma, ada beberapa parameter yang menjadi penilaian yaitu

waktu yang diperlukan suatu algoritma untuk menentukan jalur yang dicari, memori

yang dipakai semakin lama waktu maka akan semakin besar memori yang

digunakan, yang terakhir adalah kompleksitas suatu algoritma dalam menentukan

jalur yang di lewati untuk sampai ke tujuan [2].

Berdasarkan latar belakang yang ada, maka dilakukan penelitian yang

bertujuan untuk melakukan analisis terhadap algoritma Depth First Search dan

Dijkstra dalam menentukan jalur terpendek dari tempat transportasi umum menuju

ke beberapa tempat wisata yang ada di Kota Surakarta. Penelitian ini dibuat untuk

menentukan tingkat keakuratan dua algoritma tersebut dengan cara melakukan

analisa terhadap hasil perbandingan antara waktu yang dibutuhkan, ketepatan

dalam memilih jalur dan memori yang digunakan sehingga dapat menghasilkan

jalur terpendek dengan tingkat keakuratan yang tinggi dan optimal

2

2. Tinjauan Pustaka

2.1 Penelitian Terdahulu

Penelitian yang berjudul Penerapan Metode Depth First Search Pada

Pencarian Rute Bus Kota Berbasis Web Mobile Di Solo telah membahas tentang

penggunaan metode Depth First Search dalam aplikasi berbasis web mobile yang

berfungsi untuk menentukan rute dari bus yang ada di Kota Solo, aplikasi ini

bermanfaat untuk para penumpang bus agar tidak salah dalam memilih bus sesuai

dengan jalur dan tujuan [3].

Penelitian yang berjudul Perbandingan Algoritma Dijkstra Dan Algoritma

Ant Colony Dalam Penentuan Jalur Terpendek membahas tentang hasil dari

perbandingan dua algoritma, dimana algoritma Dijkstra memiliki hasil yang lebih

konsisten daripada algoritma ant colony dalam menentukan jalur terpendek [1].

Penelitian yang berjudul Analysis Of Dijkstra’s And A* Algorithm To Find

The Shortest Path membahas tentang analisis perbandingan dua algoritma yaitu

Dijkstra dan A*. Analisa dilakukan dengan cara membandingkan waktu yang

ditempuh menggunakan ke dua algoritma. Dari penelitian yang dilakukan, algorima

A* jauh lebih baik karena memiliki rata-rata waktu tempuh yang lebih cepat [4].

Penelitian yang berjudul Analysis Of Optimal Route Algorithms Under

Constraint Conditions membahas tentang kelebihan dan kekurangan dari Algoritma

Dijkstra dan A*. Setelah dilakukan uji coba dengan menggunakan suatu kasus

tertentu untuk menghitung kecepatan, kompleksitas dan memori yang digunakan

menunjukkan bahwa Algoritma Dijkstra memiliki nillai optimalitas yang lebih baik

daripada Algoritma A* [2].

Penelitian yang berjudul An Investigation of Dijkstra and Floyd Algorithms

in National City Traffic Advisory Procedures membahas tentang implementasi

algoritma Dijkstra dan Floyd dalam pengambilan keputusan jalur yang optimal bagi

para wisatawan, dimana parameter yang dipakai dalam penelitian ini adalah waktu

dan biaya yang dibutuhkan untuk menempuh jarak antara suatu tempat ke tempat

yang lain dimana hasil penelitian menunjukkan bahwa Algoritma Dijkstra lebih

efektif daripada Algoritma Floyd [5].

Berdasarkan penelitian-penelitian yang pernah dilakukan terkait algoritma

Dijkstra dan Depth First Search maka akan dilakukan penelitian yang membahas

tentang analisis perbandingan antara algoritma Dijkstra dengan Depth First Search

dalam menentukan jalur terpendek untuk mencari algoritma yang paling optimal

dengan membandingkan waktu, ketepatan dan memori yang digunakan. Pada

penelitian sebelumnya, tidak ada perbandingan antara dua algoritma yang berbeda

cara kerja, seperti Depth First Search yang masuk kedalam pencarian buta atau

algoritma yang melakukan pencarian jalur terpendek tanpa melihat informasi jarak

yang ada dan melakaukan pencarian ke masing-masing titik yang saling terhubung,

sedangkan untuk Algoritma Dijkstra adalah Algoritma yang melakukan pencarian

berdasarkan informasi jarak dari satu titik ke titik yang lain, sehingga tidak

memerlukan banyak waktu untuk melakukan pengecekan ke semua titik. Dengan

3

demikian penelitian ini diharapkan dapat memberikan kemudahan dalam

menentukan algoritma yang lebih baik dalam menentukan jalur terpendek.

2.2 Algoritma

Gambar 1 Algoritma

Algoritma adalah urutan langkah-langkah logis untuk penyelesaian masalah

yang disusun secara sistematis dan logis. Kata Logis merupakan kata kunci dalam

Algoritma. Langkah-langkah dalam Algoritma harus logis dan harus dapat

ditentukan bernilai salah atau benar. Ciri Algoritma :

Algoritma harus berhenti setelah mengerjakan sejumlah langkah terbatas.

Setiap langkah harus didefinisikan dengan tepat dan tidak berarti-dua

(Ambiguitas).

Algoritma memiliki nol atau lebih masukan.

Algoritma memiliki nol atau lebih keluaran.

Algoritma harus efektif (setiap langkah harus sederhana sehingga dapat

dikerjakan dalam waktu yang masuk akal)

Melaksanakan Algoritma berarti mengerjakan langkah-langkah di dalam

Algoritma tersebut. Pemroses mengerjakan proses sesuai dengan algoritma yang

diberikan kepadanya [6].

2.3 Algoritma Dijkstra

Gambar 2 Algoritma Dijkstra

4

Algoritma yang ditemukan oleh Dijkstra untuk mencari path terpendek. Input

algoritma ini adalah sebuah graf berarah dan berbobot, G dan sebuah source vertex

s dalam G. V adalah himpunan semua simpul dalam graph G. Setiap sisi dari graph

ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke

vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan

fungsi w: E → [0, ∞]; jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex

v. Cost dari sebuah edge dapat dianggap sebagai jarak antara dua vertex, yaitu

jumlah jarak semua edge dalam path tersebut. Untuk sepasang vertex s dan t dalam

V, algoritma ini menghitung jarak terpendek dari s ke t [7]. Berikut adalah

pseudocode dari algoritma Dijkstra :

Algoritma 1 Algoritma Dijkstra

1. Input : s simpul tujuan

2. dist[] array penampung jarak

3. prev[] array penampung simpul yang telah dilalui

4. i index looping

5. f data untuk simpul yang telah dilalui

6. u data untuk simpul yang belum dilalui

7. v data untuk simpul yang akan dilalui

8. for i = 0 to |v| - 1

9. dist[i] = infinity

10. prev[i] = null

11. end for

12. dist[s] = 0

13. while (f is null)

14. for each edge of v (v1,v2)

15. if (dist[v1] + length(v1,v2) < dist[v2])

16. dist[v2] = dist[v1] + length(v1, v2)

17. prev[v2] = v1

18. end if

19. end for

20. end while

Algoritma 1 baris ke 1 sampai dengan 7 adalah inisialisasi awal yaitu s untuk

simpul tujuan , dist untuk array penampung jarak yang dilalui, prev adalah array

untuk menyimpan simpul terpilih yang telah dilalui, i untuk index perulangan sesuai

jumlah simpul, f adalah list untuk simpul-simpul yang telah dilalui, u untuk list

simpul yang belum dilalui dan v merupakan simpul tetangga atau simpul yang akan

dilalui. Pada baris ke 8 sampai dengan 11 adalah perulangan untuk merubah nilai

untuk masing-masing jarak ke simpul adalah tak terhingga sampai ada nilai yang

ditemukan, untuk array prev[i] bernilai null karena belum adanya simpul yang

dilewati dan terpilih. Pada baris 12 inisialisasi total jarak awal yaitu masukkan nilai

0 untuk jarak menuju simpul tujuan karena belum adanya jarak yang ditemukan.

Pada baris ke 13 sampai dengan ke 20 adalah perulangan untuk menentukan jarak

terkecil yang harus dilalui. Ketika list f bernilai null atau kosong maka lakukan

pengecekan dengan rumus dist[v1] + length(v1,v2) < dist[v2], jika lebih kecil maka

5

v1 merupakan simpul terpilih, kemudian masukan v1 ke dalam prev[v2] agar

simpul tersebut tidak dilalui lagi.

2.4 Algoritma Depth First Search

Gambar 3 Algoritma Depth First Search

Algoritma Depth First Search pertama kali diperkenalkan oleh Tarjan dan

Hopcroft 20 tahun lalu. Mereka menunjukkan bagaimana Depth First Search (DFS)

merupakan metode pencarian secara mendalam dan bagian dari blind search atau

pencarian buta. Pencarian dimulai dari level paling pertama, kemudian dilanjutkan

ke anak paling kiri pada level berikutnya. Demikian seterusnya sampai tidak

terdapat anak lagi atau level yang paling dalam. Jika pencarian belum menemukan

solusi, maka dilakukan penelusuran kembali ke node sebelumnya dan dilanjutkan

ke node tetangga. Proses ini diulangi terus hingga menemukan solusi [8], adapun

algoritma Depth First Search berisi antara lain :

1. Bentuk satu elemen Queue yang terdiri dari root node.

2. Until Queue empty, atau goal sudah dicapai, maka tentukan apakah elemen

pertama dalam Queue adalah goal node.

a. Jika elemen pertama adalah goal node, maka keluar.

b. Jika elemen pertama tidak goal, maka remove elemen pertama dari

Queue dan add anak elemen pertama. 3. Jika goal node sudah ditemukan maka pencarian berhenti.

Berikut ini adalah pseudocode dari algoritma Depth First Search :

Algoritma 2 Algoritma Depth First Search

1. Input : s[] array untuk menampung simpul yang telah dilalui

2. u data simpul yang akan dilalui

3. w data simpul yang akan dilalui

4. for each vertex u

5. u = false

6. end for

7. push(s[],u)

8. while (s is not null)

6

9. pop(s[1])

10. if (u = false)

11. u = true

12. for each w

13. push(s[], w)

14. end for

15. end if

16. end while

Algoritma 2 baris ke 1 sampai dengan 3 merupakan inputan yang diperlukan,

s merupakan array untuk menampung simpul-simpul yang akan dilalui, kemudian

untuk u adalah simpul yang akan dilalui dan w merupakan simpul yang berdekatan

dengan w. Pada baris ke 4 sampai dengan 6 merupakan perulangan untuk merubah

nilai-nilai dari simpul u menjadi false, sebagai tanda bahwa simpul belum dilalui.

Kemudian pada baris ke 7 merupakan fungsi dimana nilai u akan masuk ke dalam

array s yang nantinya akan dilakukan pengecekan dari masing-masing simpul.

Kemudian pada baris ke 8 sampai dengan 11 adalah fungsi untuk melakukan

pengecekan apakah u merupakan simpul yang harus dilalui dengan cara jika u

bernilai false maka rubah nilai u menjadi true. Kemudian pada baris ke 12 dan 13

merupakan langkah untuk melakukan pencarian simpul berikutnya, yaitu jika w

adalah simpul yang bertetangga dengan u, maka masukkan nilai w ke dalam array

s.

3. Metode Penelitian

Dalam penelitian ini, metode penelitian yang dipakai terbagi ke dalam lima

tahap seperti pada Gambar 3.1, yaitu (1) identifikasi masalah, (2) pengumpulan

data, (3) implementasi algoritma, (4) pengujian algoritma, (5) analisis hasil.

Gambar 4 Tahapan Penelitian

7

Tahap pertama, yaitu identifikasi masalah, dimana pada tahap ini masalah

yang sering muncul dalam pemilihan algoritma untuk menentukan sebuah jalur

sering ditemui. Masalah yang paling sering dihadapi ketika akan menggunakan

sebuah algoritma adalah mampukah algoritma pencarian jalur tersebut

meminimalkan jumlah graf yang saling terhubung untuk menemukan jalur yang

tercepat dan tentunya efektif, selain itu apakah algoritma tersebut akan mampu

memberikan sebuah solusi jika diimplementasikan kedalam sebuah sistem.

Tahap kedua, yaitu tahap pengumpulan data. Pada tahap ini hal yang

dilakukan adalah mengumpulkan data-data yang dibutuhkan, yaitu data jarak dari

satu lokasi menuju ke lokasi lain. Dalam hal ini bukan hanya data jarak dari lokasi

awal menuju lokasi akhir saja yang diperlukan, tetapi data setiap titik pergantian

jalan juga diperlukan. Data tersebut dibutuhkan karena dengan adanya data yang

lebih spesifik, maka untuk melakukan analisa terhadap suatu algoritma dapat

menghasilkan analisa yang tepat dan akurat. Dalam penelitian ini, metode

pengumpulan data yang dipakai adalah observasi lapangan dengan cara melakukan

pengamatan dan pengukuran langsung ke lapangan dengan cara pergi dari satu

lokasi menuju ke lokasi lain untuk mendapatkan data yang tepat dan akurat. Selain

dengan cara observasi lapangan, data jarak dalam penelitian ini diambil dari

pemetaan google map.

Tahap ketiga yaitu implementasi algoritma, tahap dimana algoritma yang

akan di uji diimplementasikan ke dalam sebuah sistem untuk melihat keakuratan

dari algoritma tersebut.

Tahap keempat yaitu pengujian algoritma, tahap dimana agoritma yang sudah

diimplementasikan ke dalam sebuah sistem akan diuji. Dalam pengujian ini, ada

beberapa variabel yang akan dilihat. Yang pertama adalah kemampuan algoritma

tersebut untuk menemukan jalur yang paling cepat dan tepat, hasil dari pengujian

terhadap variabel ini dapat dilihat dari total graf atau jarak yang akan dilalui sudah

memiliki nilai paling minimal daripada hasil yang lain, jika sudah maka algoritma

tersebut sudah cukup akurat dalam melakukan pencarian. Selain melakukan uji

coba dengan sistem, untuk variabel total jarak yang harus dilalui akan dilakukan uji

coba jugan dengan cara melakukan hitung manual dari jarak yang sudah ada. Untuk

variabel kedua adalah total waktu sistem tersebut untuk menemukan jalur yang

sesuai, perhitungan dilakukan terhadap beberapa lokasi yang berbeda dengan

percobaan sebanyak empat kali untuk satu jalur yang sama. Dari hasil ini akan

diketahui algoritma manakah yang mampu menjalankan task yang ada dengan

waktu seminimal mungkin. Untuk variabel ketiga adalah jumlah memori yang

dibutuhkan oleh algoritma tersebut untuk melakukan satu kali pencarian jalur.

Untuk setiap kali melakukan pencarian jalur, total memori untuk masing-masing

algoritma akan dihitung, semakin sedikit memori yang dihabiskan, maka semakin

bagus juga algoritma tersebut untuk diimplementasikan, karena penggunaan memor

yang tidak terlalu besar akan membuat sebuah sistem berjalan dengan baik.

Tahap kelima yaitu analisi hasil, tahap dimana hasil dari implementasi dan

pengujian algoritma akan dianalisa dan dibandingkan satu dengan yang lain. Dari

masing-masing variabel yang diuji akan dilihat dan dianalisa perbandingannya

untuk mengetahui kelebihan dan kelemahan dari masing-masing algoritma. Untuk

variabel pertama, yaitu total jarak yang dihasilkan oleh masing-masing algoritma

8

akan dibandingkan, mana yang paling efektif dan tepat baik hasil dari implementasi

sistem maupun perhitungan manual. Untuk variabel kedua yaitu total waktu yang

dibutuhkan dalam sekali pencarian jalur, waktu yang paling minimal adalah yang

paling baik. Untuk variabel ketiga adalah total memori yang dibutuhkan oleh

algoritma dalam sekali pencarian jalur tercepat, penggunaan memori yang paling

kecil adalah yang paling baik.

4. Hasil dan Pembahasan

Dari hasil pengujian yang telah dilakukan terhadap algoritma Dijkstra dan

Depth First Search diperoleh hasil untuk masing-masing variabel yang diujikan.

Untuk variabel yang pertama, yaitu variabel total jarak yang harus dilewati dihitung

melalui dua cara, yang pertama algoritma yang diimplementaskan ke dalam sebuah

sistem dan yang kedua adalah melalui cara penghitungan manual dengan rumus

yang ada. Untuk algoritma Depth First Search, pada kode program 1 merupakan

fungsi untuk menghitung total jarak yang harus dilalui dari lokasi asal ke lokasi

tujuan.

Kode Program 1 Fungsi Menghitung Jarak Depth First Search

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

void Lokasi(String dari, String tujuan) {

int jarak;

infolokasi f;

jarak = match(dari, tujuan);

if (jarak != 0) {

btStack.push(new infolokasi(dari, tujuan, jarak));

return;

}

f = find(dari);

if (f != null) {

btStack.push(new infolokasi(dari, tujuan, f.jarak));

Lokasi(f.dari, dari);

} else if (btStack.size() > 0) {

f = (infolokasi) btStack.pop();

lokasi(f.dari, f.tujuan);

}

}

Fungsi dari kode program 1 yang diimplementasikan adalah pada baris ke 5

sampai dengan 7 jika node lokasi awal masih ada atau tidak kosong, maka node

akan dimasukkan ke dalam stack atau kumpulan dari node-node awal sampai

dengan node akhir, pada baris ke 9 sampai dengan 15 jika kondisi awal tidak

terpenuhi maka kondisi kedua yaitu ukuran dari stack sudah melebihi batas yang

sudah ditentukan dan node asal sudah kosong maka semua node-node yang ada di

dalam stack merupakan jalur-jalur yang dihasilkan dengan jumlah jarak dari

masing-masing titik yang dijumlahkan menjadi total jarak yang harus dilalui. Untuk

algoritma Dijkstra, pada kode program 2 adalah fungsi untuk melakukan

pencarian total jarak yang harus dilalui dari lokasi asal ke lokasi tujuan.

9

Kode Program 2 Fungsi Menghitung Jarak Dijkstra

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

public static void HitungJarak(Vertex asal)

{

asal.minDistance = 0.;

PriorityQueue<Vertex> antrian = new PriorityQueue<Vertex>();

antrian.add(asal);

while (!antrian.isEmpty()) {

Vertex u = antrian.poll();

for (Edge e : u.adjacencies)

{

Vertex v = e.tujuan;

double jarak = e.jarak;

double distanceThroughU = u.minDistance + jarak;

if (distanceThroughU < v.minDistance) {

antrian.remove(v);

v.minDistance = distanceThroughU ;

v.previous = u;

antrian.add(v);

}}

}}

Fungsi kode program 2 adalah untuk menghitung total jarak, pada baris ke

3 pertama jarak minimal adalah 0, karena untuk node yang selanjutnya tidak boleh

bernilai negatif atau tak terhingga. Kemudian pada baris ke 5 masukkan node

selanjutnya ke dalam antrian, pada baris ke 8 lakukan pengecekan terus-menerus

sampai menemukan tujuan. Pada baris ke 13 sampai dengan 17 jika dalam

melakukan pencarian ditemukan dua atau lebih node yang terhubung sampai ke

tujuan, hapus node dengan nilai yang lebih tinggi dan simpan node-node yang telah

dilalui namun memiliki nilai yang terkecil, karena node-node tersebut adalah node

paling efektif untuk mencapai tujuan. Berikut ini adalah tabel perbandingan dari

hasil pengujian sistem dua algoritma :

Tabel 1 Hasil Total Jarak Sistem

Dijkstra DFS Dijkstra DFS Dijkstra DFS

Stasiun Solo Balapan Terminal Tirtonadi Bandara Adi Sumarmo

Stadion

Manahan

1902

Meter

1902

Meter

1836

Meter

2522

Meter

4616

Meter

4616

Meter

Keraton Surakarta

3102 Meter

3567 Meter

3591 Meter

6005 Meter

9633 Meter

9672

Meter

Kebun

Binatang

Jurug

4954

Meter

5872

Meter

5062

Meter

5322

Meter

8129

Meter

10956

Meter

10

Berikut ini adalah hasil dari perhitungan manual untuk data lokasi yang sama

dengan implementasi sistem :

Tabel 2 Hasil Total Jarak Manual

Dijkstra DFS Dijkstra DFS Dijkstra DFS

Stasiun Solo Balapan Terminal Tirtonadi Bandara Adi Sumarmo

Stadion

Manahan

1902

Meter

1902

Meter

1836

Meter

1836

Meter

4616

Meter

4616

Meter

Keraton Surakarta

3102 Meter

3252 Meter

3591 Meter

5905 Meter

9633 Meter

9672

Meter

Kebun

Binatang

Jurug

4954

Meter

5298

Meter

5062

Meter

5322

Meter

8129

Meter

9212

Meter

Perbedaan dari kedua algoritma yang telah diuji pada Tabel 1 dan Tabel 2

variabel jarak adalah pada algoritma depth first search akan melakukan pencarian

ke semua node akar terlebih dahulu, jika node akar adalah tujuan maka solusi

ditemukan tanpa melihat adanya solusi lain pada node akar yang ada, sedangkan

pada algoritma dijkstra node-node yang tidak bisa dilalui langsung bernilai tak

terhingga sehingga tidak akan dilakukan pengecekan, selain itu jika ada lebih dari

satu node pada level yang sama, maka akan dilakukan pengecekan untuk node

dengan bobot paling minimal, setelah itu pencarian akan dilanjutkan pada node

tetangga yang lain dan node yang telah dilalui diberi tanda agar tidak dilakukan

pengecekan lagi untuk node yang sama. Untuk jumlah node dan edge dari jalur yang

harus dilalui yaitu jalur pertama dari Stasiun Solo Balapan menuju Stadion

Manahan adalah 6 node, untuk jalur kedua yaitu dari Stasiun Solo Balapan menuju

Keraton Surakarta adalah 15 node, untuk jalur ketiga dari Stasiun Balapan menuju

Kebun Binatang Jurug adalah 11 node, untuk jalur keempat dari Terminal Tirtonadi

menuju Kebun Binatang Jurug adalah 8 node, untuk jalur kelima dari Terminal

Tirtonadi menuju Keraton Surakarta adalah 19 node, untuk jalur keenam dari

Terminal Tirtonadi menuju Stadion Manahan adalah 5 node, untuk jalur ketujuh

dari Bandara Adi Soemarmo menuju Kebun Binatang Jurug adalah 12 node, untuk

jalur kedelapan dari Bandara Adi Soemarmo menuju Keraton Surakarta adalah 25

node, untuk jalur kesembilan dari Bandara Adi Soemarmo menuju Stadion

Manahan adalah 11 node. Sehingga dalam kasus ini, algoritma dijkstra lebih

berpeluang menemukan solusi dengan total jarak yang lebih kecil yaitu rata-rata

total jarak yang dilalui adalah 4758 Meter dan untuk Algoritma Depth First Search

adalah 5603 Meter.

Untuk variabel pengujian kedua adalah total waktu yang dibutuhkan untuk

menemukan jalur tercepat menuju lokasi tujuan oleh algoritma dijkstra dan

algoritma depth first search. Berikut ini adalah tabel perbandingan dari hasil

pengujian dua algoritma :

11

Tabel 3 Hasil Total Waktu

Dijkstra DFS Dijkstra DFS Dijkstra DFS

Stasiun Solo Balapan Terminal Tirtonadi Bandara Adi Sumarmo

Stadion

Manahan

Ke -1. 2 s

Ke -2. 0 s Ke -3. 0 s

Ke -4. 0 s

Ke -1. 1 s

Ke -2. 2 s Ke -3. 1 s

Ke -4. 0 s

Ke -1. 0 s

Ke -2. 0 s Ke -3. 0 s

Ke -4. 0 s

Ke -1. 0 s

Ke -2. 2 s Ke -3. 1 s

Ke -4. 0 s

Ke -1. 0 s

Ke -2. 0 s Ke -3. 0 s

Ke -4. 0 s

Ke -1. 1 s

Ke -2. 1 s Ke -3. 0 s

Ke -4. 0 s

Keraton

Surakarta

Ke -1. 1 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 2 s

Ke -2. 0 s

Ke -3. 1 s

Ke -4. 0 s

Ke -1. 0 s

Ke -2. 1 s

Ke -3. 0 s

Ke -4. 1 s

Ke -1. 1 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 1 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 1 s

Ke -2. 0 s

Ke -3. 1 s

Ke -4. 0 s

Kebun

Binatang

Jurug

Ke -1. 1 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 3 s

Ke -2. 1 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 0 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 2 s

Ke -2. 1 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 2 s

Ke -2. 0 s

Ke -3. 0 s

Ke -4. 0 s

Ke -1. 2 s

Ke -2. 1 s

Ke -3. 0 s

Ke -4. 0 s

Dari hasil pengujian pada Tabel 3 menunjukkan bahwa algoritma Dijkstra

memerlukan rata-rata waktu yang lebih singkat dan cepat yaitu 0,25 s daripada

algoritma Depth First Search yaitu 0,69 s. Hal ini disebabkan oleh cara pencarian

algoritma dijkstra akan membandingkan terlebih dahulu node tetangga dengan nilai

yang lebih kecil, sedangkan untuk node-node yang bukan tetangga telah bernilai

tak terhingga dan tidak akan dilalui. Untuk node-node yang telah dilalui akan diberi

tanda agar node tersebut tidak dilalui untuk yang kedua kalinya, sehingga dalam

satu kali pencarian akan ditemukan rute menuju lokasi tujuan dengan nilai yang

optimal dan waktu yang paling singkat. Untuk algoritma Depth First Search cara

pencarian yang dilakukan adalah memasukan semua node akar dan melakukan

pencarian dari node akar yang paling pertama masuk sampai semua node akar

selesai dilalui, langkah tersebut akan terus dilakukan yang memungkinkan untuk

node yang pernah dilalui akan dilalui lagi untuk yang kedua kalinya, hal ini yang

menyebabkan waktu pencarian algoritma Depth First Search akan lebih lama dari

pada waktu pencarian algoritma Dijkstra.

Untuk variabel yang ketiga yaitu memori yang diperlukan dalam melakukan

satu kali pencarian. Untuk masing-masing algoritma tentu banyak memori berbeda-

beda tergantung dari lokasi yang akan dicari. Berikut ini adalah tabel perbandingan

dari hasil pengujian dua algoritma :

12

Tabel 4 Hasil Total Memori

Dijkstra DFS Dijkstra DFS Dijkstra DFS

Stasiun Solo Balapan Terminal Tirtonadi Bandara Adi Sumarmo

Stadion

Manahan

1. 16,7 MB

2. 16,9 MB

3. 12,4 MB

4. 15,3 MB

1. 7,4 MB

2. 8,8 MB

3. 10,2 MB

4. 11,2 MB

1. 0,8 MB

2. 14,7 MB

3. 12 MB

4. 11,9 MB

1. 14,7 MB

2. 12,7 MB

3. 17,2 MB

4. 21,3 MB

1. 12,1 MB

2. 3,1 MB

3. 11,9 MB

4. 12 MB

1. 12,6 MB

2. 17,9 MB

3. 16,8 MB

4. 13,1 MB

Keraton Surakarta

1. 10,4 MB 2. 12,4 MB

3. 12,6 MB

4. 12,6 MB

1. 2,2 MB 2. 4,7 MB

3. 6,8 MB

4. 8 MB

1. 34,8 MB 2. 2 MB

3. 4,5 MB

4. 3,1 MB

1. 12 MB 2. 12,7 MB

3. 12,9 MB

4. 18,5 MB

1. 7,9 MB 2. 8,9 MB

3. 11,9 MB

4. 11,8 MB

1. 7,3 MB 2. 12,6 MB

3. 13,1 MB

4. 18,8 MB

Kebun

Binatang

Jurug

1. 2,6 MB

2. 9,7 MB

3. 9,7 MB

4. 5,6 MB

1. 1,08 MB

2. 1,1 MB

3. 1,4 MB

4. 2,1 MB

1. 22 MB

2. 9,6 MB

3. 12,1 MB

4. 11,9 MB

1. 20,2 MB

2. 22 MB

3. 12,9 MB

4. 13 MB

1. 21,3 MB

2. 3 MB

3. 12 MB

4. 12 MB

1. 19,1 MB

2. 16,9 MB

3. 20,7 MB

4. 15,3 MB

Dari hasil pengujian pada Tabel 4 dapat dilihat bahwa algoritma dijkstra

membutuhkan memori yang lebih sedikit dengan rata-rata total memori 11,2 MB

sedangkan untuk Algoritma Depth First Search adalah 12,2 MB. Algoritma

Dijkstra akan membuang informasi mengenai node yang telah dilewati namun

mempunyai nilai bobot yang besar, jadi node-node selain dari node jalur tercepat

akan dihapus dari memori hal ini berbeda dari algoritma Depth First Search dimana

semua node-node akar akan dimasukkan ke dalam antrian node sampai dengan

solusi ditemukan, sehingga node-node yang bukan merupakan jalur solusi tetap

berada di dalam memori. Dalam melakukan pengujian ini, profiler akan menulis

semua data-data dan variabel yang dipakai oleh sistem dalam melakukan pencarian,

sehinggan dapat dilihat pada data mana yang paling membutuhkan memori.

Tabel 5 Perbandingan Hasil Pegujian Algoritma

Total Rata-Rata Jarak Total Rata-Rata Waktu Total Rata-Rata Memori

Dijkstra 4758 Meter 0,25 s 11,2 MB

DFS 5603 Meter 0,69 s 12,2 MB

Dari hasil perbandingan tiga variabel yang diujikan yaitu total jarak yang

diperlukan, total waktu yang dibutuhkan dan total memori yang dipakai oleh

masing-masing Algoritma menunjukkan bahwa Algoritma Dijkstra memiliki nilai

optimalitas yang lebih baik daripada Algoritma Depth First Search, hal ini dapat

13

dilihat dari variabel yang telah diujikan yaitu total jarak yang dilewati dimana rata-

rata jarak yang dihasilkan oleh Algoritma Dijktra adalah 4758 meter dibandingkan

dengan Algoritma Depth First Search adalah 5603 meter, total waktu yang

dibutuhkan dimana rata-rata waktu yang diperlukan oleh Algoritma Dijkstra adalah

0,25 s dibandingkan dengan Algoritma Depth First Search adalah 0,69s dan total

memori yang dibutuhkan dalam melakukan satu kali pencarian dimana rata-rata

memori yang diperlukan oleh Algoritma Dijkstra adalah 11,2 MB dibandingkan

dengan Algoritma Depth First Search adalah 12,2 MB.

5. Simpulan

Berdasarkan hasil dari pengujian dan pembahasan yang ada, dapat

disimpulkan bahwa algoritma Dijkstra lebih optimal daripada algoritma Depth First

Search dalam hal pencarian jalur tercepat, hal ini dapat dilihat dari variabel yang

telah diujikan yaitu total jarak yang dilewati, total waktu yang dibutuhkan dan total

memori yang dibutuhkan dalam melakukan satu kali pencarian. Hal ini tentu akan

sangat berpengaruh jika algoritma akan diimplementasikan kedalam sebuah sistem,

karena dengan keunggulan yang ada algoritma Dijkstra akan mampu untuk

melakukan pencarian jalur-jalur yang lebih luas dengan nilai optimalitas yang

tinggi.

6. Daftar Pustaka

[1] Ferdifiansyah, F., 2013. Perbandingan Algoritma Dijkstra Dan Algoritma Ant

Colony Dalam Penentuan Jalur Terpendek.

[2] Mawale, M. V., & Gandole, Y. B., 2014. Analysis Of Optimal Route

Algorithms Under Constraint Conditions.

[3] Herwanto, A., & Purnama, B. E., 2013. Penerapan Metode Depth First

Search Pada Pencarian Rute Bus Kota Berbasis Web Mobile Di Solo.

[4] Alija, A. S., 2015. Analysis Of Dijkstra’s And A* Algorithm To Find The

Shortest Path.

[5] Sangaiah, A. K., dkk., 2014. An Investigation of Dijkstra and Floyd

Algorithms in National City Traffic Advisory Procedures.

[6] Februariyanti, H., 2011. Pengertian Algoritma, Ciri Algoritma dan Contoh.

[7] Pugas, D. O., dkk., 2011. Pencarian Rute Terpendek Menggunakan

Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan

Pariwisata Kota Sawahlunto.

[8] Kusumadewi, S., 2003. Artificial Intelligence – Teori dan Aplikasinya.

Yogyakarta : Graha Ilmu.