perbandingan algoritma greedy dan dijkstra untuk menentukan

1

Henny Syahriza Lubis : Perbandingan Algoritma Greedy Dan Dijkstra Untuk Menentukan Lintasan Terpendek, 2009. USU Repository © 2009

PERBANDINGAN ALGORITMA GREEDY DAN DIJKSTRA UNTUK MENENTUKAN LINTASAN TERPENDEK

SKRIPSI

HENNY SYAHRIZA LUBIS 051411009

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA MEDAN

2009

2



SKRIPSI

Diajukan untuk melengkapi tugasakhir dan memenuhi syarat mencapai gelar Sarjana Sains

HENNY SYAHRIZA LUBIS 051411009

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA MEDAN

2009

3


PERSETUJUAN Judul : PERBANDINGAN ALGORITMA GREEDY DAN

DIJKSTRA UNTUK MENENTUKAN LINTASAN TERPENDEK

Kategori : SKRIPSI Nama : HENNY SYAHRIZA LUBIS Nomor Induk Mahasiswa : 051411009 Program Studi : SARJANA (S1) MATEMATIKA Departemen : MATEMATIKA Fakultas : MATEMATIKA DAN ILMU PENGETAHUAN

ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA

Diluluskan di Medan, 20 Maret 2009 Komisi Pembimbing : Pembimbing 2, Pembimbing1, Drs. Marwan Harahap, M.Eng. Drs. Sawaluddin,M.IT. NIP.130422437 NIP.132206398 Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua Dr.Saib Suwilo,M.Sc. NIP.131796149

4


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya. Medan, 20 Maret 2009 Henny Syahriza Lubis 051411009

5


PENGHARGAAN

Puji dan syukur penulis panjatkan kehadirat Tuhan Yang Maha Pemurah dan Maha Penyayang, dengan limpahan rahmat dan karunia-Nya skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terimakasih saya sampaikan kepada Bapak Drs. Syawaluddin, M.IT dan Bapak Drs. Marwan Harahap, M.Eng, selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan skripsi ini. Panduan ringkas, padat dan profesional telah diberikan kepada saya agar penulis dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Dr. Saib Suwilo, M.Sc. dan Bapak Drs. Henri Rani Sitepu, M.Si., Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen pada Departemen Matematika FMIPA USU, Pegawai di FMIPA USU, rekan-rekan kuliah. Akhirnya tidak terlupakan kepada bapak, ibu dan semua ahli keluarga yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Tuhan Yang Maha Esa membalasnya.

6


ABSTRAK

Algortima Dijkstra dan Algoritma Greedy merupakan algoritma untuk menemukan jarak terpendek dari suatu verteks ke verteks yang lainnya pada suatu graph yang berbobot, di mana jarak antar verteks adalah bobot dari tiap edge atau arc pada graph tersebut. Algoritma Dijkstra dan Greedy merupakan algoritma yang setiap langkahnya mengambil edge atau arc yang berbobot minimum yang menghubungkan sebuah verteks yang sudah terpilih dengan sebuah verteks lain yang belum terpilih, dan implementasinya dengan menggunakan bahasa pemograman Visual Basic 6.0.

7


COMPARASION OF DIJKSTRA AND GREEDY ALGORITHMS FOR CHOOSE THE SHORTEST PATH.

ABSTRACT Dijkstra Algorithms and Greedy Algorithms is an algorithms to find the shortest path from a vertex to the another one in a weighted graph, where the distance between the vertex is the weight from each edge or arc of it. Dijkstra Algorithms and Greedy is a algorithm which every step of the process takes a edge or arc that has the minimum value weight that connects a vertex which has been chosen with another vertex that has not been chosen, and the implementation would use Visual Basic 6.0

8


DAFTAR ISI

Halaman Persetujuan ii Pernyataan iii Penghargaan iv Abstrak v Abstract vi Daftar Isi vii Daftar Tabel ix Daftar Gambar x

Bab 1 Pendahuluan 1 1.1 Latar Belakang 1 1.2 Perumusan Masalah 2 1.3 Pembatasan Masalah 2 1.4 Tujuan Penelitian 3 1.5 Kontribusi Penelitian 3 1.6 Metode Penelitian 3 1.7 Tinjauan Pustaka 4 Bab 2 Landasan Teori 6 2.1 Teori Dasar Graph 6 2.1.1 Graph Berarah 6 2.1.2 Graph Tak Berarah 8 2.1.3 Graph Berbobot 9 2.1.4 Refrentasi Graph Dalam Matriks 10 2.2 Lintasan ( Path ) 11 2.2.1 Path Minimum 12 2.2.2 Lintasan Terpendek ( Shortest Path ) 14 2.3 Algoritma Greedy 15 2.3.1 Cara Kerja Algoritma Greedy 17 2.3.2 Pseudocode Algoritma Greedy 18 2.4 Algoitma Dijkstra 19 2.4.1 Sejarah Algoritma Dijkstra 19

2.4.2 Cara Kerja Algoritma Dijkstra 20

9


Bab 3 Pembahasan 23 3.1 Implementasi Algoritma Greedy 23

3.1.1 Pemeriksaan Verteks dan Lintasan Pertama 23 3.1.2 Input Graph 25

3.1.3 Proses Graph 27 3.2 Prosedure Algoritma Greedy 29 3.3 Flowchart Algoritma Greedy 31 3.4 Implementasi Algoritma Dijkstra 32 3.4.1 Input Graph 42

3.4.2 Proses Graph 44 3.5 Prosedure Algoritma Dijkstra 46 3.6 Flowchart Algoritma Dijkstra 48 3.7 Flowchart Program 49 3.7.1 Halaman Utama 50

3.7.2 Halaman Komputasi 51 3.7.3 Halaman Hasil 55 3.7.4 Kebutuhan Perangkat 57 Bab 4 Kesimpulan dan Saran 59 4.1 Kesimpulan 59 4.2 Saran 59 Daftar Pustaka 60

Lampiran Listing Program 61

10


DAFTAR TABEL

Halaman Tabel 3.1 Hasil Iterasi ke 1 33 Tabel 3.2 Hasil Iterasi ke 2 34 Tabel 3.3 Hasil Iterasi ke 3 34 Tabel 3.4 Hasil Iterasi ke 4 35 Tabel 3.5 Hasil Iterasi ke 5 35 Tabel 3.6 Hasil Iterasi ke 6 36 Tabel 3.7 Hasil Iterasi ke 7 37 Tabel 3.8 Hasil Iterasi ke 8 37 Tabel 3.9 Hasil Iterasi ke 9 38 Tabel 3.10 Hasil Iterasi ke 10 39 Tabel 3.11 Hasil dari seluruh tabel 39 Tabel 3.12 Beda Jarak Lintasan Terpendek Algoritma Greedy dan Dijkstra 57

11


DAFTAR GAMBAR

Halaman

Gambar 2.1 Graph Berarah atau Digraph 7 Gambar 2.2 Graph Berarah 8 Gambar 2.3 Graph Tak Berarah 9 Gambar 2.4 Graph Berarah Berbobot 9 Gambar 2.5 Graph Tidak Berarah dan Tidak Berbobot 10 Gambar 2.6 Graph Dengan 4 Buah Verteks 12 Gambar 2.7 Graph Dengan 6 Verteks dan 10 Edge 13 Gambar 2.8 Shortest Path(Garis Tebal) 15 Gambar 3.1 Graph Untuk Algoritma Greedy 23 Gambar 3.2 Lintasan 1 Algoritma Greedy 24 Gambar 3.3 Lintasan 2 Algoritma Greedy 24 Gambar 3.4 Lintasan 3 Algoritma Greedy 25 Gambar 3.5 Flowchart Algoritma Greedy 31 Gambar 3.6 Graph Untuk Algoritma Dijkstra 32 Gambar 3.7 Node Terpilih Pada Iterasi ke 1 33 Gambar 3.8 Node Terpilih Pada Iterasi ke 2 34 Gambar 3.9 Node Terpilih Pada Iterasi ke 3 34 Gambar 3.10 Node Terpilih Pada Iterasi ke 4 35 Gambar 3.11 Node Terpilih Pada Iterasi ke 5 36 Gambar 3.12 Node Terpilih Pada Iterasi ke 6 36 Gambar 3.13 Node Terpilih Pada Iterasi ke 7 37 Gambar 3.14 Node Terpilih Pada Iterasi ke 8 38 Gambar 3.15 Node Terpilih Pada Iterasi ke 9 38 Gambar 3.16 Node Terpilih Pada Iterasi ke 10 39 Gambar 3.17 Flowchart Algoritma Dijkstra 48 Gambar 3.18 Flowchart Aplikasi Algoritma Greedy dan Dijkstra 49 Gambar 3.19 Perancangan Diagram Halaman Utama 50 Gambar 3.20 Tampilan Output Halaman Utama 50 Gambar 3.21 Perancangan Diagram Halaman Komputasi 51 Gambar 3.22 Tampilan Menu Perancangan Lintasan Terpendek 51 Gambar 3.23 Tampilan Menu Peta 52 Gambar 3.24 Tampilan Menu Graph 52 Gambar 3.25 Tampilan Menu Cari Lintasan Terpendek 53 Gambar 3.26 Tampilan Menu Editor Titik 53

12


Gambar 3.27 Tampilan Menu Editor Jalan 54 Gambar 3.28 Tampilan Menu Editor Hapus 54 Gambar 3.29 Tampilan Menu Editor Tambah Caption 55 Gambar 3.30 Implementasi Form Graph Algoritma Dijkstra 55 Gambar 3.31 Implementasi Form Hasil Komputasi Algoritma Dijkstra 56 Gambar 3.32 Implementasi Form Graph Algoritma Greedy 56 Gambar 3.33 Implementasi Form Hasil Komputasi Algoritma Greedy 56 Gambar 3.34 Grafik Lama Proses Pencarian Lintasan Terpendek Algoritma Greedy dan Dijkstra 58

BAB 1

PENDAHULUAN

1.1 Latar Belakang

Dalam kehidupan, sering dilakukan perjalanan dari suatu tempat atau kota ke

tempat yang lain dengan mempertimbangkan efisiensi, waktu dan biaya sehingga

diperlukan ketepatan dalam menentukan jalur terpendek antar suatu kota. Hasil

penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan keputusan

untuk menunjukkan jalur yang ditempuh. Hasil yang didapatkan juga membutuhkan

kecepatan dan keakuratan dengan bantuan komputer.

Secara umum, pencarian jalur terpendek dapat dibagi menjadi 2(dua)

metode, yaitu: metode konvensional dan metode heuristik. Metode konvensional

merupakan metode yang menggunakan perhitungan matematik biasa, pada pencarian

lintasan terpendek hanya dapat diselesaikan untuk 5(lima) sampai 10(sepuluh)

verteks, untuk verteks yang lebih banyak metode heuristik lebih variatif dan waktu

perhitungan yang diperlukan lebih singkat, karena metode heuristik menggunakan

metode pendekatan dan melakukan pencarian.

Untuk menggunakan atau memfungsikan sebuah komputer harus terdapat

program yang terdistribusi di dalamnya, tanpa program tersebut komputer hanyalah

menjadi sebuah kotak yang tak berguna. Program yang terdapat pada komputer

sangat bervariasi dan setiap program tersebut pasti menggunakan algoritma.

13


Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah.

Perintah-perintahnya dapat diterjemahkan secara bertahap dari awal hingga akhir.

Masalah tersebut dapat berupa apapun dengan catatan untuk setiap masalah, memiliki

kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma.

Algoritma yang akan dipergunakan untuk mencari lintasan terpendek

dalam hal ini adalah algoritma Greedy dan algoritma Dijkstra, algoritma Dijkstra

merupakan algoritma yang paling terkenal untuk mencari lintasan terpendek yang

diterapkan pada graph berarah dan berbobot, di mana jarak antar verteks adalah bobot

dari tiap arc pada graph tersebut. Selain algoritma Dijkstra, algoritma Greedy

merupakan salah satu metode untuk memecahkan masalah optimasi, juga merupakan

program yang dapat memecahkan masalah langkah demi langkah, yang pada setiap

langkahnya mengambil pilihan yang terbaik yang diperoleh saat itu tanpa

memperhatikan konsekuensi ke depannya dengan gagasan dasar adalah membangun

solusi besar diatas solusi kecil.

1.2 Perumusan Masalah

Perumusan masalah yang akan diteliti dalam tulisan ini adalah bagaimana

mengimplementasikan algoritma Greedy dan algoritma Dijkstra sehingga diperoleh

algoritma yang tepat dan akurat untuk menyelesaikan masalah lintasan terpendek.

1.3 Pembatasan Masalah

Dalam melakukan perbandingan algoritma Greedy dan algoritma Dijkstra dilakukan

beberapa batasan sebagai berikut:

1. Algoritma Greedy dan Dijkstra yang digunakan dibatasi pada

permasalahan shortest path saja, dengan input graph yang terdiri dari

jumlah titik, nama dan koordinat titik. Letak titik dapat dibangkitkan

secara acak maupun manual.

14


2. Bobot antar titik yang ditentukan hanyalah bobot jarak. Dengan

mengabaikan bobot-bobot lainnya. Sehingga jalur terpendek berdasarkan

jarak terpendek antar titik.

3. Keluaran yang dihasilkan adalah hasil dari algoritma Greedy dan Dijkstra

yang diimplementasikan dalam suatu program sederhana dengan

menggunakan aplikasi Visual Basic 6.0

1.4 Tujuan Penelitian

Penelitian ini bertujuan untuk membandingkan pencarian lintasan terpendek manakah

yang lebih baik dari implementasi algoritma Greedy dan algoritma Dijkstra.

1.5 Kontribusi Penelitian

Dengan membandingkan algoritma Greedy dan algoritma Dijkstra dapatlah diketahui

metode mana yang baik untuk menentukan maksimal lintasan terpendek dari suatu

titik ke titik yang lain. Hal ini dapat diaplikasikan dalam peta suatu daerah, sistem

saluran air PDAM, sistem aliran listrik PLN dan sebagainya.

1.6 Metode Penelitian

Penelitian ini dilakukan dengan langkah-langkah sebagai berikut:

1. Menguraikan konsep algoritma Greedy dan Dijkstra dalam menentukan

lintasan terpendek.

2. Mengimplementasikan algoritma Greedy dan Dijkstra ke dalam suatu

program.

15


3. Melakukan analisa untuk membandingkan kinerja setiap algoritma

berdasarkan kelebihan dan kemudahannya.

4. Membuat kesimpulan dan saran dari penelitian yang dilakukan.

1.7 Tinjauan Pustaka

Arief Lutfi Hendratmono (2008) dalam makalahnya menguraikan algoritma

Dijkstra merupakan algoritma untuk menemukan jarak terpendek dari suatu verteks ke

verteks yang lainnya pada suatu graph yang berbobot dengan menggunakan strategi

Greedy. Algoritma ini menyelesaikan masalah mencari sebuah lintasan terpendek

(sebuah lintasan yang mempunyai panjang minimum) dari verteks a ke verteks z

dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui

oleh edge(arc) negatif, jika dilalui oleh edge(arc) negatif, maka penyelesaian yang

diberikan adalah infiniti.

Seymour Lipschutz dan Marc Lars dalam bukunya ”Matematika Diskrit 2”,

definisi graph adalah bahwa sebuah graph terdiri dari 2(dua) bagian yaitu: sebuah

himpunan V=V(G) memiliki elemen-elemen yang dinamakan verteks. Kemudian

sebuah kumpulan E=E(G) atau A=A(G), merupakan pasangan tak berurut dari

verteks-verteks yang berbeda dinamakan edge(arc). Sedangkan multigraph G=G(V,E)

terdiri dari suatu himpunan V(verteks) dan suatu himpunan E(edge) kecuali E

mengandung multiple edge, yaitu beberapa edge(arc) dengan menghubungkan titik-

titik ujung yang sama, dan E mungkin mengandung satu atau lebih loop, yaitu sebuah

edge yang titik-titik ujungnya adalah verteks yang sama.

16


Yeni Kurniasari (2006) dalam makalahnya menguraikan algoritma Greedy

merupakan metode untuk menemukan solusi optimum dalam persoalan optimasi

dengan solusi langkah perlangkah sebagai berikut:

1. Terdapat banyak pilihan yang perlu dikembangkan pada setiap langkah solusi.

Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam

menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak

dapat diubah lagi pada langkah selanjutnya.

2. Pendekatan yang digunakan di dalam algoritma Greedy adalah membuat

pilihan yang terlihat memberikan perolehan terbaik, yaitu dengan membuat

pilihan optimum local pada setiap langkah dan diharapkan akan mendapatkan

solusi optimum global.

Algoritma Greedy didasarkan pada pemindahan edge(arc) per edge(arc) dan

pada setiap langkah yang diambil tidak memikirkan konsekuensi ke depan, Greedy

tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada serta

sebagian masalah Greedy tidak selalu berhasil memberikan solusi yang benar-benar

optimum tapi memberikan solusi yang mendekati nilai optimum.

17


BAB 2

LANDASAN TEORI

2.1 Teori Dasar Graph

Sebuah graph G didefinisikan sebagai pasangan himpunan (V,E) di mana V=

himpunan verteks {v1,v2,…,vn} dan E=himpunan edge(arc) yang menghubungkan

verteks-verteks {e1,e2,…,en} atau dapat ditulis dengan notasi G=(V,E)(Rinaldi Munir,

2006 hal: 291).

Berdasarkan orientasi arah pada sisi, graph dapat dibedakan atas dua jenis yaitu

(Rinaldi Munir, 2006 hal: 294):

2.1.1 Graph berarah (directed graph atau digraph)

18


Pada graph tak berarah (undirected graph) elemen dari E disebut dengan edge,

sedangkan pada graph berarah (directed graph) elemen dari E(A) disebut dengan arc.

Graph berarah G terdiri dari suatu himpunan V dari verteks-verteks dan suatu

himpunan E(A) dari arc sedemikian rupa sehingga setiap arc a ε A menghubungkan

pasangan verteks terurut. Jika terdapat sebuah arc a yang menghubungkan pasangan

terurut (v,w) dari verteks-verteks, maka dapat ditulis dengan a=(v,w), yang

menyatakan sebuah arc dari v ke w.

v1

v2

v5

v3

a6

a4

a2

a5a1 a3

v4

Gambar 2.1 Graph Berarah atau Digraph

Digraph pada Gambar 2.1 adalah graph berarah dengan himpunan verteks-verteks

V(G)={v1, v2, v3, v4, v5} dan himpunan arc-arc A(G)={a1, a2, a3, a4,ae5, a6} yaitu

pasangan terurut dari {(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v5, v1), (v2, v5)}.

Pada suatu graph jika dua buah verteks v1 dan v2 dihubungkan oleh suatu edge(arc),

maka kedua verteks tersebut dikatakan adjacent. Pada Gambar 2.1 verteks v1 adjacent

(bertetangga) dengan verteks v2. Sementara itu, arc a1 dikatakan incident (bersisian)

dengan verteks v1 dan verteks v2.

Matriks yang bersesuaian dengan graph berlabel G adalah matriks adjacency A=(aij),

dengan aij = nilai arc yang menghubungkan verteks vi dengan verteks vj. Jika titik vi

tidak berhubungan langsung dengan titik vj, maka aij = ∞, dan jika i = j, maka aij=0.

Misalkan G adalah sebuah graph berarah. Sebuah arc berarah a=[u,v] dikatakan

mulai pada verteks awal u dan berakhir di verteks akhir v, u dan v dikatakan adjacent.

Derajat luar dari v, (outdeg (v)) adalah jumlah arc yang berawal pada v, dan derajat

dalam dari v (indeg (v)) adalah jumlah arc yang berakhir di v.Karena setiap arc mulai

19


dan berakhir pada suatu verteks, maka jumlah derajat-dalam dan jumlah derajat-luar

harus sama dengan n, yaitu jumlah arc pada G.

Sumber (source) adalah sebuah verteks v di G yang mempunyai derajat-luar positif

dan derajat-dalam nol. Sedangkan, tujuan (sink) adalah verteks v di G yang

mempunyai derajat-dalam positif tetapi derajat-luar nol.

Gambar 2.2 Graph Berarah

Gambar 2.2 terdiri dari:

Verteks A B C D E F G

Derajat-dalam (indegree) 0 2 2 4 1 1 2

Derajat-luar (outdegree) 4 1 0 0 3 3 1

Jumlah derajat dalam dan jumlah derajat luar sama dengan 12 yaitu jumlah busur.

Graph pada Gambar 2.2 verteks A adalah sumber (source) karena arc-nya berawal

pada A tetapi tidak berakhir di A. Sedangkan C dan D adalah verteks tujuan (sink)

karena arc-nya berakhir di C dan di D tetapi tidak berawal di verteks itu.

2.1.2 Graph tak berarah (Undirected Graph)

Graph tak berarah G terdiri dari suatu himpunan V dari verteks-verteks dan suatu

himpunan E dari edge-edge sedemikian rupa sehingga setiap sisi e ε E dikaitkan

A B

G

E D

F

C

20


dengan pasangan verteks tak terurut. Jika terdapat sebuah edge e yang

menghubungkan verteks v dan w, maka dapat dituliskan dengan e = (v,w) atau e =

(w,v) yang menyatakan sebuah edge antara v dan w.

v1

v2

v5

v3

v4

e6

e4

e2

e5e1 e3

Gambar 2.3 Graph tak Berarah

Graph pada Gambar 2.3 adalah graph tak berarah dengan himpunan verteks-verteks

V(G) = {v1, v2, v3, v4, v5} dan himpunan sisi E(G) = {e1, e2, e3, e4, e5, e6} yaitu

pasangan tak terurut dari {(v1, v2), (v2, v3), (v3, v4), (v4, v5), (v5, v2)}.

2.1.3 Graph Berbobot (Weight Graph)

Dalam memodelkan suatu masalah ke dalam graph, ada informasi yang ditambahkan

pada arc graph. Misalnya pada graph yang menggambarkan peta jalan raya antara

kota-kota, dapat ditambahkan sebuah bilangan pada setiap arc untuk menunjukkan

jarak antara kedua kota yang dihubungkan oleh arc tersebut.

Graph berbobot (weighted graph) adalah suatu graph tanpa arc paralel dimana setiap

arc-nya berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot

arc (w(a)) tersebut (Jong Jek Siang, 2002, hal: 262).

v1

v2

v5v3

2

v4

34

2

54

52

Gambar 2.4 Graph Berarah Berbobot

21


Graph tidak berarah dan tidak berbobot: tiap busur tidak mempunyai anak panah dan

tidak berbobot.

A

B

C

D

E

F

G

Gambar 2.5 Graph tidak berarah dan tidak berbobot

2.1.4 Representasi Graph dalam Matriks

Matriks dapat digunakan untuk menyatakan suatu graph, Kemudian graph

direpresentasikan pada matriks, yang dapat dibedakan sebagai berikut:

1. Matriks Adjacency

Misalkan G adalah graph berarah yang terdiri dari n verteks tanpa arc paralel. Matriks

Adjacency pada graph G adalah matriks bujur sangkar n x n, A= (aij) dengan

=ji

ji

titik vke titik vdari arc adatidak 0

titik vke titik vdari arc ada 1ija

Matriks adjacency dari graph Gambar 2.3 adalah:

A =

0000110000010001010010010

v

5

4

3

2

1

54321

vvvvv

vvvv

Jika graph yang diberikan adalah graph berbobot, maka elemen matriks yang

terhubung antara verteks adalah bobot graph.

22


2. Matriks Incidency

Matriks incidency atau matriks bersisian adalah matriks yang merepresentasikan

hubungan antara verteks dan edge(arc). Misalkan B adalah matriks dengan m baris

untuk setiap verteks dan n kolom untuk setiap edge(arc). Jika verteks terhubung

dengan edge(arc), maka elemen matriks bernilai 1. Sebaliknya, jika verteks tidak

terhubung dengan edge(arc), maka elemen matriks bernilai 0.

Matriks bersisian dari graph Gambar 2.3 adalah:

B =

10010

1100001100001100001110001

5

4

3

2

1

654321

vvvvv

eeeeee

2.2 Lintasan (Path)

Misalkan v0 dan vn adalah verteks-verteks dalam sebuah graph. Sebuah lintasan dari

v0 ke vn dengan panjang n adalah sebuah barisan berselang-seling dari n+1 verteks dan

n edge yang berawal dengan verteks v0 dan berakhir dengan verteks vn, yang

berbentuk (v0,e1,v1,e2,v2 … vn-1,en,vn) dengan edge ei insiden pada verteks vi-1 dan vi

untuk i=1,…,n (Richard Johnsonbaugh, 1998, hal: 75).

Jika semua verteks berbeda (setiap edge(arc) dilewati hanya satu kali), maka

suatu lintasan dikatakan sederhana (simple path). Jika sebuah lintasan yang berawal

dan berakhir pada verteks yang sama, v0=vn, maka disebut lintasan tertutup (close

path). Jika verteks awal dan verteks akhir dari lintasan tersebut berbeda, maka sebuah

lintasan dikatakan lintasan terbuka (open path).

Panjang lintasan pada graph adalah banyaknya edge(arc) dalam lintasan

tersebut. Pada graph berarah, lintasan harus mengikuti arah arc.

23


v2

v3

v4

v1

Gambar 2.6 Graph dengan Empat Buah Verteks

Pada Gambar 2.6:

Lintasan v1, v2, v3, v4 = lintasan sederhana dengan panjang lintasan 3(tiga).

Lintasan v1, v2, v3, v4, v1 = lintasan tertutup dengan panjang lintasan 4(empat).

Lintasan v1, v2, v3, v1, v4 = lintasan terbuka dengan panjang lintasan 4(empat).

Jika terdapat lintasan dari vi ke vj, maka suatu graph G dikatakan terhubung.

Pada graph berarah, jika setiap pasang dari verteks vi dan vj terdapat sebuah lintasan

dari vi ke vj dan dari vj ke vi, maka suatu graph dikatakan terhubung kuat (strongly

connected). Jika verteks-verteks dalam sebuah graph sebagai kota-kota dan arc-arc

sebagai jalan, maka sebuah lintasan berhubungan dengan sebuah perjalanan berawal

pada suatu kota, melalui beberapa kota dan berakhir di suatu kota.

2.2.1 Path Minimum Salah satu aplikasi graph berarah berlabel yang sering dipakai adalah mencari path

terpendek di antara 2 verteks. Jika masalahnya adalah mencari jalur tercepat, maka

path terpendek tetap dapat digunakan dengan cara mengganti nilai edge.

Misalkan G adalah suatu graph, dimana v dan w adalah 2 (dua) verteks dalam G.

Suatu Walk dari v ke w adalah barisan verteks-verteks berhubungan dan edge secara

berselang-seling, diawali dari verteks v dan diakhiri pada verteks w. Walk dengan

panjang n dari v ke w ditulis : v0 e1 v1 e2 v2 … vn-1 en vn dengan v0 = v; vn = w; vi-1

dan vi adalah verteks-verteks ujung edge ei.

24


Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua edge-nya

berbeda. Path dari v ke w dituliskan sebagai v = v0 e1 v1 e2 v2 … vn-1 en vn = w dengan

ei ≠ ej untuk i ≠ j.

Lintasan adalah suatu barisan edge ( )kiii eee .,,.........,

21 sedemikian rupa sehingga

verteks terminal jie berimpit dengan verteks awal

)1( +jie untuk 1 ≤ j ≤ k – 1.

Gambar 2.7 Graph dengan 6 verteks dan 10 edge

Pada Gambar 2.7 terdapat:

a. v1 e1 v2 e3 v3 e4 v3 e5 v4, barisan ini merupakan Path dari v1 ke v4 dengan panjang

4. Semua edge berbeda (e1, e3, e4, dan e5 masing-masing muncul sekali). Ada

verteks yang berulang (v3 muncul 2 kali). Verteks awal dan verteks akhir tidak

sama (verteks awal = v1 dan verteks akhir = v4).

b. v1 e1 v2 e3 v3 e5 v4 e5 v3 e6 v5, barisan ini merupakan walk dari v1 ke v5 dengan

panjang 5. Ada edge yang muncul lebih dari sekali, yaitu e5 (muncul 2 kali).

2.2.2 Lintasan Terpendek (Shortest Path)

Persoalan mencari lintasan terpendek di dalam graph merupakan salah satu

persoalan optimasi. Graph yang digunakan dalam mencari lintasan terpendek adalah

graph berbobot. Bobot pada sisi graph dapat menyatakan jarak antar kota, waktu,

v1 v2

v3

v6 v5

v4

e10

e9

e6

e5

e4

e7

e8

e3

e1

e2

25


biaya dan sebagainya. Dalam hal ini bobot harus bernilai positif, pada lain hal

terdapat bobot dengan nilai negatif. Lintasan terpendek dengan verteks awal s dan

verteks tujuan t didefinisikan sebagai lintasan terpendek dari s ke t dengan bobot

minimum dan berupa lintasan sederhana (simple path).

Misalkan lubang-lubang pada sebuah lempengan logam adalah verteks-verteks

pada graph yang bersesuaian, maka setiap pasangan verteks-verteks dihubungkan

dengan sebuah edge(arc) yang terdiri dari bobot waktu untuk memindahkan alat

pembor di antara lubang-lubang yang berhubungan. Untuk menghemat waktu dan

biaya, alat pembor harus digerakkan secepat mungkin. Sebuah lintasan dengan

panjang minimum yang mengunjungi verteks tepat satu kali mewakili lintasan optimal

yang dijalani alat pembor. Misalkan dalam masalah ini lintasan diperlukan untuk

memulai pada verteks a dan berakhir pada verteks e. Lintasan dengan panjang

minimum dapat ditemukan dengan mendaftar semua lintasan yang mungkin dari a ke

e yang melalui setiap verteks tepat satu kali dan memilih yang terpendek.

Dalam beberapa hal, panjang sebenarnya mewakili biaya atau beberapa nilai

lainnya. Panjang dari lintasan adalah menentukan panjang jumlah dari masing-masing

edge(arc) yang terdiri dari lintasan. Untuk verteks s dan t dalam G, ada beberapa

lintasan dari s ke t. Masalah lintasan terpendek meliputi pencarian lintasan dari s ke t

yang mempunyai lintasan terpendek dengan bobot terkecil.

Lintasan terpendek antara 2(dua) verteks dari s ke t dalam jaringan adalah lintasan

graph berarah sederhana dari s ke t dengan sifat dimana tidak ada lintasan lain yang

memiliki nilai terendah.

3

2

X7

X5 4

1 2

4

X2

X4

1

3 X3

5 X8

2 X1

26


Gambar 2.8 Shortest path (garis tebal)

Pada Gambar 2.8 dapat dilihat bahwa setiap arc terletak pada path-path dari titik 1 ke

titik 5. Lintasan terpendek dari verteks pada graph Gambar 2.8 adalah P = {1 – 4, 4 –

5} dengan kapasitas 4.

2.3 Algoritma Greedy

Algoritma Greedy adalah algoritma yang memecahkan masalah langkah demi langkah

dan merupakan salah satu metode dalam masalah optimasi.

Algoritma Greedy membentuk solusi langkah per langkah sebagai berikut:

1. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi.

Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam

menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak

dapat diubah lagi pada langkah selanjutnya.

2. Pendekatan yang digunakan di dalam algoritma Greedy adalah membuat

pilihan yang terlihat memberikan perolehan terbaik, yaitu dengan membuat

pilihan optimum local pada setiap langkah dan diharapkan akan mendapatkan

solusi optimum global.

Algoritma Greedy didasarkan pada pemindahan edge(arc) per edge(arc) dan pada

setiap langkah yang diambil tidak memikirkan konsekuensi ke depan, Greedy tidak

beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada serta sebagian

masalah Greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum

tapi pasti memberikan solusi yang mendekati nilai optimum.

5

3 1 X6

27


Masalah optimasi dalam konteks algoritma Greedy disusun oleh elemen-elemen

sebagai berikut:

1. Himpunan kandidat.

Himpunan ini berisi elemen-elemen yang memiliki peluang untuk pembentuk

solusi. Pada persoalan lintasan terpendek dalam graph, himpunan kandidat ini

adalah himpunan simpul dari graph tersebut.

2. Himpunan solusi.

Himpunan ini berisi solusi dari permasalahan yang diselesaikan dan

elemennya terdiri dari elemen dalam himpunan kandidat, namun tidak

semuanya atau dengan kata lain himpunan solusi ini adalah bagian dari

himpunan kandidat.

3. Fungsi seleksi.

Fungsi yang pada setiap langkah memilih kandidat yang paling mungkin

untuk menghasilkan solusi optimal. Kandidat yang sudah dipilih pada suatu

langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

4. Fungsi kelayakan

Fungsi yang memeriksa apakah suatu kandidat yang telah dipilih (diseleksi)

dapat memberikan solusi yang layak.

5. Fungsi obyektif

Fungsi yang memaksimumkan atau meminimumkan nilai solusi. Tujuannya

adalah memilih satu saja solusi terbaik dari masing-masing anggota himpunan

solusi.

2.3.1 Cara Kerja Algoritma Greedy

28


Diberikan sebuah sebuah graph berbobot G(V,E). Tentukan lintasan terpendek dari

verteks awal a, ke setiap verteks lainnya di G. Asumsi bahwa bobot semua edge(arc)

bernilai positif. Algoritma Greedy untuk mencari lintasan terpendek dapat

dirumuskan sebagai berikut:

1. Periksa semua edge(arc) yang langsung bersesuaian dengan verteks a. Pilih

edge(arc) yang bobotnya terkecil. Edge(arc) ini menjadi lintasan terpendek

pertama, sebut saja L(1).

2. Tentukan lintasan terpendek ke dua dengan cara sebagai berikut:

(i) Hitung d(i) = panjang L(1) + bobot edge(arc) dari verteks akhir

L(1) keverteks i yang lain.

(ii) Pilih d(i) yang terkecil

(iii) Bandingkan d(i) dengan bobot edge(arc) (a,i) lebih kecil

daripada d(i), maka L(2) = L(1) U (edge(arc) dari verteks akhir

L(i) ke verteks i)

3. Dengan cara yang sama, ulangi langkah (2) untuk menentukan lintasan

terpendek berikutnya.

2.3.2 Pseudocode Algoritma Greedy

Procedure greedy (input C: himpunan_kandidat;

output S: himpunan_solusi)

{ Menentukan solusi optimum dari persoalan optimasi dengan algoritma

Greedy

Masukan: himpunan kandidat C

Keluaran: himpunan solusi S

}

Deklarasi

x: kandidat;

29


Algoritma;

S{} { inisialisasi S dengan kosong}

While(belum SOLUSI(S)) and (C= {}) do

X SELEKSI(C); {pilih kandidat dari C }

C C – {x}

If LAYAK(S U {x} then

SS U {x}

Endif

Endwhile

{SOLUSI(S) sudah diperoleh or C = {} }

Analisa:

Ambil satu kandidat dari himpunan kandidat C lalu masukkan ke x dan

kurangi C dengan kandidat tersebut. Kemudian apakah layak x digabungkan dengan

himpunan solusi S? Jika layak, maka gabungkan x dengan solusi S dan lakukan

perulangan hingga C kosong atau solusi S sudah ditemukan.

Layak atau tidaknya x digabung dengan S, melihat tujuan yang ingin dicapai pada

kasus yang sedang dipecahkan tetapi tidak melihat apakah hasil tersebut merupakan

hasil yang mampu mengoptimalkan tujuan, yang terpenting ketika langkah tersebut

diambil setidaknya hasil pada saat itu mendekati tujuan yang ingin dicapai.

Misalkan pada kasus mencari jalur terpendek, saat menguji apakah x layak

digabungkan menjadi solusi S, yang menjadi pertimbangan adalah apakah jika x

digabungkan dengan S akan menghasilkan solusi S yang terpendek?.

2.4 Algoritma Dijkstra

2.4.1 Sejarah Algoritma Dijkstra

Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra yang merupakan

salah satu varian bentuk algoritma popular dalam pemecahan persoalan yang terkait

dengan masalah optimisasi dan bersifat sederhana. Algoritma ini menyelesaikan

masalah mencari sebuah lintasan terpendek (sebuah lintasan yang mempunyai

panjang minimum) dari verteks a ke verteks z dalam graph berbobot, bobot tersebut

30


adalah bilangan positif jadi tidak dapat dilalui oleh node negatif, namun jika terjadi

demikian, maka penyelesaian yang diberikan adalah infiniti.

Algoritma Dijkstra melibatkan pemasangan label pada verteks. Misalkan

L(v) menyatakan label dari verteks v. Pada setiap pembahasan, beberapa verteks

mempunyai label sementara dan yang lain mempunyai label tetap. Misalkan T

menyatakan himpunan verteks yang mempunyai label sementara. Dalam

menggambarkan algoritma tersebut verteks-verteks yang mempunyai label tetap akan

dilingkari. Selanjutnya, jika L(v) adalah label tetap dari verteks v, maka L(v)

merupakan panjang lintasan terpendek dari a ke v. Sebelumnya semua verteks

mempunyai label sementara. Setiap iterasi dari algoritma tersebut mengubah status

satu label dari sementara ke tetap, sehingga algoritma dapat berakhir ketika z

menerima sebuah label tetap. Pada bagian ini L(z) merupakan panjang lintasan

terpendek dari a ke z. Pada algoritma Dijkstra node digunakan, karena algoritma

Dijkstra menggunakan diagram pohon(tree) untuk penentuan jalur lintasan terpendek

dan menggunakan graph yang berarah.

2.4.2 Cara Kerja Algoritma Dijkstra

Algoritma ini mencari panjang lintasan terpendek dari verteks a ke verteks z

dalam sebuah graph berbobot tersambung.

Langkah-langkah dalam menentukan lintasan terpendek pada algoritma Dijkstra yaitu:

1. Pada awalnya pilih node dengan bobot yang terendah dari node yang belum

terpilih, diinisialisasikan dengan ’0’ dan yang sudah terpilih diinisialisasikan

dengan ’1’.

2. Bentuk tabel yang terdiri dari node, status, bobot dan predecessor. Lengkapi

kolom bobot yang diperoleh dari jarak node sumber ke semua node yang

langsung terhubung dengan node sumber tersebut.

3. Jika node sumber ditemukan maka tetapkan sebagai node terpilih.

31


4. Tetapkan node terpilih dengan lebel permanen dan perbaharui node yang

langsung terhubung.

5. Tentukan node sementara yang terhubung pada node yang sudah terpilih

sebelumnya dan merupakan bobot terkecil dilihat dari tabel dan tentukan sebagai

node terpilih berikutnya.

6. Apakah node yang terpilih merupakan node tujuan? Jika ya, maka kumpulan

node terpilih atau predecessor merupakan rangakaian yang menunjukkan lintasan

terpendek.

7. Begitu seterusnya hingga semua node terpilih.

Pseudocode algoritma Dijkstra adalah sebagai berikut:

Procedure Dijkstra(INPUT m: matriks, a: simpul awal)

{

Mencari lintasan terpendek dari simpul awal a ke semua simpul

Lainnya.

Masukan: matriks ketetanggaan (m) dari graph berbobot G dan

simpul awal a

Keluaran: lintasan terpendek dari a ke semua simpul lainnya.

}

Kamus:

S: array [1..n] of integer

d: array [1..n] of integer

i: integer

Algoritma:

{ Langkah 0 (inisialisasi:)}

Traversal [1..n]

si 0

di mai

{ Langkah 1: }

sa 1

da ∞

{ langkah 2,3,...,n-1:}

Traversal {2..n-1}

32


Cari j sedemikian sehingga sj=0

dan

dj = min {d1,d2,...,dn}

sj 1 { simpul j sudah terpilih}

perbarui d, untuk i = 1,2,3,s.d.n dengan:

di(baru) = min{di(lama,dj+ mji}

Jika menggunakan algoritma Dijkstra untuk menentukan jalur terpendek dari suatu

graph, maka akan menemukan jalur yang terbaik, karena pada waktu penentuan jalur

yang akan dipilih, akan dianalisis bobot dari node yang belum terpilih, lalu dipilih

node dengan bobot yang terkecil. Jika ternyata ada bobot yang lebih kecil melalui

node tertentu, maka bobot akan dapat berubah. Algoritma Dijkstra akan berhenti

ketika semua node sudah terpilih, dan dengan algoritma Dijkstra ini dapat

menemukan jarak terpendek dari seluruh node, tidak hanya untuk node dari asal dan

tujuan tertentu saja.

Algoritma Dijkstra menggunakan waktu sebesar O(V*logV+E) di mana V dan E

adalah banyaknya verteks dan arc. Kompleksitas algoritma Dijkstra adalah O(n2).

Sehingga untuk mencari semua pasangan verteks terpendek, total waktu asimptotik

komputasinya adalah: T(n)=n.O(n2)=O(n3), algoritma Dijktra lebih menguntungkan

dari sisi running time.

.

BAB 3

PEMBAHASAN

3.1 Implementasi Algoritma Greedy

33


Implementasi algoritma Greedy dirancang dalam bahasa pemograman Visual Basic

6.0. Berikut adalah contoh algoritma Greedy.

1. Pemeriksaan verteks dan lintasan pertama

2. Input Graph

3. Proses Graph

Gambar 3.1 Graph Untuk Algoritma Greedy

3.1.1 Pemeriksaan verteks dan lintasan pertama

Pada Gambar 3.1 terdapat 10 kota dan jalur yang menghubungkan kota-kota tersebut

beserta jarak antar kotanya dari kota A (asal) ke kota J (tujuan).

Mula-mula proses berawal dari verteks A sebagai verteks keberangkatan. Terdapat 2

jalur yang memungkinkan yaitu jalur AB dengan jarak 2 dan AD dengan jarak 3, AB

terpilih karena jaraknya lebih kecil dari AD.

34


Gambar 3.2 Lintasan 1 Algoritma Greedy

Dari B terdapat 3 jalur yang memungkinkan, yaitu BE dengan jarak 2, BC dengan

jarak 5, dan BG dengan jarak 4. BE terpilih karena jaraknya lebih kecil BC dan BG.


Dari E terdapat 4 jalur yang memungkinkan yaitu ED dengan jarak 6, EF dengan

jarak 9, EJ dengan jarak 5 dan EH dengan jarak 7. EJ terpilih karena jarak lebih kecil

dari ED, EF dan EH, karena verteks tujuan telah tercapai maka algoritma Greedy

berhenti sampai di sini. Lintasan terpendeknya adalah ABEJ dengan total

jarak 9.


3.1.2 Input Graph

Proses input graph dilakukan dengan cara menggambar titik dan jalan yang

menghubungkan setiap titik pada halaman graph. Selanjutnya adalah membuat

35


caption dari setiap titik yang akan menjadi nama titik tersebut dan caption pada jalan

akan menjadi jarak antara titik yang satu dengan yang lainnya.

1. Prosedure untuk membuat titik:

Private Sub mnuTambahTItik_Click()

theBlockCollection.AddShape 3, theBlockCollection.getFreeTagID()

End Sub

2. Prosedure untuk membuat jalan/garis tanpa panah:

Private Sub mnuJoinLine_Click()

If (PREV_SELECTED_SHAPE <> -1) And (SELECTED_SHAPE <> -1) Then

theLineCollection.AddLine

frmPeta.shp(PREV_SELECTED_SHAPE).Tag,

frmPeta.shp(SELECTED_SHAPE).Tag, False

Else

MsgBox "Two objects should be selected!"

End If

End Sub

3. Menambah caption titik/verteks dengan posisi di tengah:

Private Sub mnTbhCaptionDiTengah_Click()

If (SELECTED_SHAPE <> -1) Then

Dim s As String

s = InputBox("Enter the caption for a shape", "Caption",

theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptiontheBlockC

ollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaption = s

theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).updateShapeCaptio

nPos

Else

MsgBox "Object should be selected!"

End If

End Sub

36


4. Menambah caption titik/verteks dengan posisi di atas:

Private Sub mnuTbhCaptionDitengah_Click()


Dim s As String


theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptionUpper)

theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptionUpper = s

theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).bSetUpperCaptionD

own = False


nPos

Else


End If

End Sub

5. Menambah caption titik/verteks dengan posisi di bawah:

Private Sub mnuAddCaptionLowerToBlock_Click()

mnuAddCaptionUpperToBlock_Click


own = True


nPos

End Sub

6. Menambah caption jalan dengan posisi di tengah:

Private Sub mnuTbhCaptionJalan_Click()


Dim s As String

s = InputBox("Enter the caption")

theLineCollection.AddCaptionToLine


frmPeta.shp(SELECTED_SHAPE).Tag, s

Else

37



End If

End Sub

3.1.3 Proses Graph

Data graph yang telah diinput pada form graph selanjutnya diproses untuk

mendapatkan matriks jarak dari graph tersebut. Berikut prosedure pada proses graph:

Private Sub cmdCalcData_Click()

Dim i As Integer

Dim j As Integer

Dim toIndex As Integer

flxMap.Rows = frmPeta.theBlockCollection.Count + 1

flxMap.Cols = frmPeta.theBlockCollection.Count + 1

If frmPeta.theBlockCollection.Count > 0 Then

flxMap.FixedRows = 1

flxMap.FixedCols = 1

End If

For i = 0 To flxMap.Cols - 1

flxMap.ColWidth(i) = 530

Next i

For i = 1 To frmPeta.theBlockCollection.Count

flxMap.row = i

flxMap.col = 0

flxMap.Text = frmPeta.theBlockCollection(i).sCaption

flxMap.row = 0

flxMap.col = i


flxMap.row = i

For j = 1 To flxMap.Cols - 1

flxMap.TextMatrix(i, j) = "0"

flxMap.col = j

flxMap.CellForeColor = vbBlack

flxMap.CellFontBold = False

Next j

38


For j = 1 To frmPeta.theLineCollection.Count

If frmPeta.theLineCollection(j).sFrom =

frmPeta.theBlockCollection(i).TagID Then

toIndex =

frmPeta.theBlockCollection.getIndexFromTag(frmPeta.theLineCollection(

j).sTo)

flxMap.col = toIndex

flxMap.Text = frmPeta.theLineCollection(j).sCaption

If (flxMap.Text = "") Then flxMap.Text = "1"

flxMap.CellForeColor = vbRed

flxMap.CellFontBold = True

End If

Next j

Next i

ReDim jarak(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1)

ReDim visib(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1)

For i = 1 To Me.flxMap.Rows - 1

For j = 1 To Me.flxMap.Cols - 1

jarak(i, j) = flxMap.TextMatrix(i, j)

If jarak(i, j) = 0 Then

visib(i, j) = 0 '

Else

visib(i, j) = Round(1 / jarak(i, j), 2)

End If

Next

Next

End Sub

3.2 Prosedure Algoritma Greedy

Berikut prosedure yang digunakan pada algoritma Greedy:

Dim src As Integer

Dim dest As Integer

src = getIndexOfTabName(sFrom)

dest = getIndexOfTabName(sTo)

39


If (src = -1) Or (dest = -1) Then

MsgBox "something wrong!!!"

Exit Sub

End If

Dim ketemu as boolen

Dim CC as integer

Dim Lc() as integer

Dim Ltemp () as integer

LC(1) = src

CC(1)=LC(1)

Counter=1

While ( LC <> null and ketemu <> true ) do

CC(counter)=LC(counter)

LC(1)=0

If CC(countre) <> 0 then

For a = 0 ubound(cc)

{mulai penelusuran semua child}

If cc(a) <> Ltemp then

LC(counter+1)=cc(a)

Ltemp=CC

Endif

endif

LP(ubound+1)=CC(counter+1

if adj(lp(a,b))<> 0 then

ketemu true

endif

Loop

3.3 Flowchart Algoritma Greedy

40


Gambar 3.5 Flowchart Algoritma Greedy

3.4 Implementasi Algoritma Dijkstra

Implementasi algoritma Dijkstra dirancang dalam bahasa pemograman Visual Basic

6.0. Berikut adalah tahap proses implementasi algoritma Dijkstra:

1. Input Graph

Mulai

Tentukan Vs dan Vt

Jalur=0 Tentukan vs(V1) dan Cari V2

Bandingkan Lintasan Kesemua verteks terhubung

Vt Tercapai

Jalur Verteks Tujuan

Lintasan Terpendek Ditemukan

Selesai

41


2. Proses Graph

Pada algoritma Dijkstra node digunakan, karena algoritma Dijkstra menggunakan

diagram pohon(tree) untuk penentuan jalur lintasan terpendek dan menggunakan

graph yang berarah. Algoritma Dijkstra mencari jarak terpendek dari node asal ke

node terdekatnya, kemudian ke node berikutnya, dan seterusnya. Secara umum

sebelum dilakukan I iterasi, algoritma sudah mengidentifikasi jarak terdekat dari i-1

node terdekatnya. Jika seluruh node berbobot tertentu yang (positif), maka node

terdekat berikutnya dari node asal dapat ditemukan selama node berdekatan dengan

node Ti. Kumpulan node yang berdekatan dengan node di Ti inilah yang merupakan

kandidat dari algoritma Dijkstra untuk memilih node berikutnya dari node asal.

Adapun gambar dari graph yang akan diselesaikan dengan algoritma Dijkstra adalah

sebagai berikut:

Gambar 3.6 Graph Untuk Algoritma Dijkstra

Langkah-langkah untuk menentukan jarak terpendek dari A ke J dengan

menggunakan algoritma Dijkstra adalah sebagai berikut:

1. Pada awalnya status dari node yang belum terpilih diinisialisasikan dengan ‘0’

dan yang sudah terpilih diinisialisasi dengan ‘1’ dimulai dari node A.

2. Tentukan bobot dari node yang langsung berhubungan dengan node sumber

yaitu node A, seperti: dari node A ke node B=2, dari node A ke node C=8, dari

node A ke node D=3, dan untuk node E, F, G, H, I, J diinisialisasi dengan ‘-‘

karena tidak ada lintasan (arc) yang menghubungkan secara langsung dengan

node A.

42


3. Predecessor (node sumber) dari node A, B, C, D adalah A, karena jarak

dihitung dari node A, sehingga node A disebut sebagai predecessor (node

sumber), sedangkan untuk node F, G, H, I, J diinisialisasi dengan ‘-‘

dikarenakan tidak ada lintasan (arc) yang langsung menghubungkan dari node

A, sehingga jaraknya tidak ada.

Tabel 3.1 Hasil Iterasi Ke-1

Node A B C D E F G H I J

Status 1 0 0 0 0 0 0 0 0 0

Bobot - 2 8 3 - - - - - -

Predecessor A A A A - - - - - -

A

Gambar 3.7 Node Terpilih Pada Iterasi ke-1

Dari Tabel 3.1 pilih node yang memiliki bobot yang paling kecil dan status nya masih

‘0’, yaitu node B. Untuk itu status node B menjadi ‘1’ dan predecessor-nya masih

tetap A, dan node yang lain predecessor-nya masih sama. Jika node B sudah terpilih,

maka ada perubahan pada bobot node C, di mana awalnya bernilai 8 sekarang menjadi

7. Bobot 8 diperoleh dari node yang langsung bergerak dari A ke C, padahal terdapat

jalur yang lebih pendek yaitu melalui B, dengan bobot 7, sehingga predecessor pada

C menjadi B, karena node B sudah terpilih, selanjutnya diperoleh node E dengan

bobot 4 dan node G dengan bobot 6, predecessor E dan G adalah B, di mana untuk

mencapai node E dan G dari node A bisa melalui node B. Sehingga diperoleh:



Status 1 1 0 0 0 0 0 0 0 0

Bobot - 2 7 3 4 - 6 - - -

Predecessor A A B A B - B - - -

43


A

B

Gambar 3.8 Node terpilih pada Iterasi ke-2

Dari Tabel 3.2 di didapatkan bahwa node D memiliki bobot yang paling kecil,

sehingga statusnya akan berubah menjadi ‘1’ dan predecessor-nya masih tetap A.

Sehingga diperoleh:



Status 1 1 0 1 0 0 0 0 0 0

Bobot - 2 7 3 4 - 6 - - -


A

B D


Dari Tabel 3.3 didapatkan bahwa node E memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’. Jika node E sudah terpilih, maka node F

mempunyai bobot 13, node H bobotnya 11 dan node J bobotnya 9. Untuk mencapai

node F, H dan node J dari node A bisa melalui node B, kemudian melalui node E

dengan predecessor-nya berubah menjadi E. Sehingga diperoleh:



Status 1 1 0 1 1 0 0 0 0 0

Bobot - 2 7 3 4 13 6 11 - 9

Predecessor A A B A B E B E - E

44



Dari Tabel 3.4 didapatkan bahwa node G memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’, predecessor-nya masih tetap B. Jika node G

sudah terpilih, maka ada perubahan bobot pada node F dengan bobot 13 berubah

menjadi 12 dan predecessor E menjadi G. Sehingga diperoleh:



Status 1 1 0 1 1 0 1 0 0 0

Bobot - 2 7 3 4 12 6 11 - 9

Predecessor A A B A B G B E - E


Dari Tabel 3.5 didapatkan bahwa node C memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’, predecessor-nya masih tetap B dengan bobot 7.

Sehingga diperoleh:

45




Status 1 1 1 1 1 0 1 0 0 0

Bobot - 2 7 3 4 12 6 11 - 9



Dari Tabel 3.6 didapatkan bahwa node J memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’ dengan predecessor-nya E. Jika node J sudah

terpilih, maka diperoleh node I dengan bobot 19 yang bersumber dari node

ABEJI. Sehingga diperoleh:



Status 1 1 1 1 1 0 1 0 0 1

Bobot - 2 7 3 4 12 6 11 19 9

Predecessor A A B A B G B E J E

46



Dari Tabel 3.7 didapatkan bahwa node H memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’ dengan predecessor-nya E. Jika node J sudah

terpilih, maka diperoleh node I dengan bobot 19 berubah bobotnya menjadi 15 dengan

predecessor-nya H yang bersumber dari node ABEHI. Sehingga diperoleh:



Status 1 1 1 1 1 0 1 1 0 1

Bobot - 2 7 3 4 12 6 11 15 9

Predecessor A A B A B G B E H E


Dari Tabel 3.8 didapatkan bahwa node F memiliki bobot yang paling kecil, sehingga

statusnya akan berubah menjadi ‘1’, predecessor-nya masih tetap G dengan bobot 12.

Sehingga diperoleh:

47




Status 1 1 1 1 1 1 1 1 0 1

Bobot - 2 7 3 4 12 6 11 15 9



Semua node telah terpilih dan hanya tinggal node I yang belum terpilih, selanjutnya

status node I akan berubah menjadi ‘1’, predecessor-nya masih tetap H dengan bobot

15. Sehingga diperoleh:



Status 1 1 1 1 1 1 1 1 1 1

Bobot - 2 7 3 4 12 6 11 15 9


48



Hasil dari seluruh tabel adalah sebagai berikut:

Tabel 3.11 Hasil dari seluruh tabel

Iterasi Ke 1


Status 1 0 0 0 0 0 0 0 0 0

Bobot - 2 8 3 - - - - - -

Predecessor A A A A - - - - - -

Iterasi Ke 2


Status 1 1 0 0 0 0 0 0 0 0

Bobot - 2 7 3 4 - 6 - - -


Iterasi Ke 3


Status 1 1 0 1 0 0 0 0 0 0

Bobot - 2 7 3 4 - 6 - - -


Iterasi Ke 4

49



Status 1 1 0 1 1 0 0 0 0 0

Bobot - 2 7 3 4 13 6 11 - 9

Predecessor A A B A B E B E - E

Iterasi Ke 5


Status 1 1 0 1 1 0 1 0 0 0

Bobot - 2 7 3 4 12 6 11 - 9


Iterasi Ke 6


Status 1 1 1 1 1 0 1 0 0 0

Bobot - 2 7 3 4 12 6 11 - 9

Iterasi Ke 7


Status 1 1 1 1 1 0 1 0 0 1

Bobot - 2 7 3 4 12 6 11 19 9

Predecessor A A B A B G B E J E

Iterasi Ke 8


Status 1 1 1 1 1 0 1 1 0 1

Bobot - 2 7 3 4 12 6 11 15 9


Iterasi Ke 9


Status 1 1 1 1 1 1 1 1 0 1

Bobot - 2 7 3 4 12 6 11 15 9


Iterasi Ke 10


Status 1 1 1 1 1 1 1 1 1 1

50


Bobot - 2 7 3 4 12 6 11 15 9


Program akan berhenti karena semua node sudah terpilih. Sehingga akan

menghasilkan jalur terpendek dari node A ke setiap node yang ada. Untuk melihat

jalur mana yang terpilih dapat ditelusuri dari predecessor-nya, Sehingga akan didapat:

A B : A - B : 2

A C : A - B - C : 7

A D : A - D : 3

A E : A - B - E : 4

A F : A - B - G – F : 12

AG : A – B – G : 6

AH : A – B – E – H : 11

AI : A – B – E – H – I : 15

AJ : A – B – E – - J : 9

3.4.1 Input Graph

Proses input graph dilakukan dengan cara menggambar titik dan jalan yang

menghubungkan setiap titik pada halaman graph. Selanjutnya adalah membuat

caption dari setiap titik yang akan menjadi nama titik tersebut dan caption pada jalan

akan menjadi jarak antara titik yang satu dengan yang lainnya.

1. Prosedure untuk membuat titik:

Private Sub mnuTambahTItik_Click()

theBlockCollection.AddShape 3, theBlockCollection.getFreeTagID()

End Sub

2. Prosedure untuk membuat jalan/garis tanpa panah:

51


Private Sub mnuJoinLine_Click()


theLineCollection.AddLine


frmPeta.shp(SELECTED_SHAPE).Tag, False

Else


End If

End Sub

3. Menambah caption titik/node dengan posisi di tengah:

Private Sub mnTbhCaptionDiTengah_Click()


Dim s As String


theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptiontheBlockC

ollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaption = s


nPos

Else


End If

End Sub

4. Menambah caption titik/node dengan posisi di atas:

Private Sub mnuTbhCaptionDitengah_Click()


Dim s As String


theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptionUpper)

theBlockCollection(frmPeta.shp(SELECTED_SHAPE).Tag).sCaptionUpper = s


own = False


nPos

52


Else


End If

End Sub

5. Menambah caption titik/node dengan posisi di bawah:

Private Sub mnuAddCaptionLowerToBlock_Click()

mnuAddCaptionUpperToBlock_Click


own = True


nPos

End Sub

6. Menambah caption jalan dengan posisi di tengah:

Private Sub mnuTbhCaptionJalan_Click()


Dim s As String

s = InputBox("Enter the caption")

theLineCollection.AddCaptionToLine


frmPeta.shp(SELECTED_SHAPE).Tag, s

Else


End If

End Sub

3.4.2 Proses Graph

Data graph yang telah diinput pada form graph selanjutnya diproses untuk

mendapatkan matriks jarak dari graph tersebut. Berikut Prosedure pada proses graph:

Private Sub cmdCalcData_Click()

Dim i As Integer

Dim j As Integer

53


Dim toIndex As Integer

flxMap.Rows = frmPeta.theBlockCollection.Count + 1

flxMap.Cols = frmPeta.theBlockCollection.Count + 1

If frmPeta.theBlockCollection.Count > 0 Then

flxMap.FixedRows = 1

flxMap.FixedCols = 1

End If

For i = 0 To flxMap.Cols - 1

flxMap.ColWidth(i) = 530

Next i

For i = 1 To frmPeta.theBlockCollection.Count

flxMap.row = i

flxMap.col = 0


flxMap.row = 0

flxMap.col = i


flxMap.row = i

For j = 1 To flxMap.Cols - 1

flxMap.TextMatrix(i, j) = "0"

flxMap.col = j

flxMap.CellForeColor = vbBlack

flxMap.CellFontBold = False

Next j

For j = 1 To frmPeta.theLineCollection.Count

If frmPeta.theLineCollection(j).sFrom =

frmPeta.theBlockCollection(i).TagID Then

toIndex =

frmPeta.theBlockCollection.getIndexFromTag(frmPeta.theLineCollection(

j).sTo)

flxMap.col = toIndex

flxMap.Text = frmPeta.theLineCollection(j).sCaption

If (flxMap.Text = "") Then flxMap.Text = "1"

flxMap.CellForeColor = vbRed

flxMap.CellFontBold = True

End If

Next j

Next i

ReDim jarak(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1)

ReDim visib(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1)

54


For i = 1 To Me.flxMap.Rows - 1

For j = 1 To Me.flxMap.Cols - 1

jarak(i, j) = flxMap.TextMatrix(i, j)

If jarak(i, j) = 0 Then

visib(i, j) = 0 '

Else

visib(i, j) = Round(1 / jarak(i, j), 2)

End If

Next

Next

End Sub

3.5 Prosedure Algoritma Dijkstra

Berikut prosedure yang digunakan pada algoritma Dijkstra:

Dim src As Integer

Dim dest As Integer

src = getIndexOfTabName(sFrom)

dest = getIndexOfTabName(sTo)

If (src = -1) Or (dest = -1) Then

MsgBox "something wrong!!!"

Exit Sub

End If

Dim MAX As Integer

MAX = flxMap.Cols

Dim current As Integer

Dim dist_fc As Integer

Dim i As Integer

Dim min As Integer

Dim do_search As Boolean

55


do_search = True

current = src

dist_fc = 0

flxS.TextMatrix(1, current) = "True"

flxS.row = 1

flxS.col = current

flxS.CellForeColor = vbRed

flxS.CellFontBold = True

flxDist.TextMatrix(1, current) = 0

Do While do_search

For i = 1 To MAX - 1

If ((myVl(flxMap.TextMatrix(current, i)) <> 0) And _

(myVl(flxDist.TextMatrix(1, i)) >

myVl(flxMap.TextMatrix(current, i)) + dist_fc)) Then

flxDist.TextMatrix(1, i) =

myVl(flxMap.TextMatrix(current, i) + dist_fc)

flxPath.TextMatrix(1, i) = current

End If

Next i

min = INF

For i = 1 To MAX - 1

If ((myVl(flxDist.TextMatrix(1, i)) < min) And (flxS.TextMatrix(1, i)

= "False")) Then

min = myVl(flxDist.TextMatrix(1, i))

current = i

dist_fc = myVl(flxDist.TextMatrix(1, i))

End If

Next i

flxS.TextMatrix(1, current) = "True"

If (min = INF) Then

do_search = False

End If

Loop

56


3.6 Flowchart Algoritma Dijkstra

Mulai

Tentukan Vs dan Vt

Jalur= 0 Tentukan Vs(V1) sebagai T-node Permanen

Cari V2 sementara dengan bobot terkecil dan tetapkan Predecessor

Ubah status V2 dan tetapkan sebagai T-node

57


Tidak

Ya

Gambar 3.17 Flowchart Algoritma Dijkstra

3.7 Flowchart Program

Adapun flowchart dari program untuk menentukan lintasan terpendek dengan

menggunakan algoritma Greedy dan Dijkstra adalah sebagai berikut:

T-node=Vt

Lintasan terpendek ditemukan

Telusuri jalur Predecessor

Selesai

58


Start

Tampilkan Form Utama

Menu Graph

Tampilkan Form Graph

Input Node Asal dan Node

Tujuan

Cari Rute Terpendek

Algoritma Dijstra

Algoritma Greedy

Cari Rute terpendek berdasarkan algoritma

Yang dipilih

Tampilkan Hasil

Ya

Ya

Ya

Tidak

Ya

End

Tidak

Tidak

Gambar 3.18 Flowchart Aplikasi Algoritma Greedy dan Dijkstra

3.7.1 Halaman Utama

Pada halaman utama terdapat beberapa menu antara lain: judul aplikasi, menu utama

dan data graph.

59


Judu Aplikasi

Data Graph

Menu Utama

Gambar 3.19 Perancangan Diagram Halaman Utama

Gambar 3.20 Tampilan Output Halaman Utama

3.7.2 Halaman Komputasi

60


Halaman komputasi adalah halaman untuk input yang dibutuhkan pada saat proses

pencarian jalur terpendek, dan hasil dari komputasi. Gambar 3.21 merupakan

diagram dari halaman komputasi.

Matriks Jarak

Pilih Algoritma

Titik Awal

Titik Tujuan

Hasil Komputasi

Proses

Gambar 3.21 Perancangan Diagram Halaman Komputasi

Pada menu perancangan lintasan terpendek terdiri dari menu: Peta, graph, cari rute

terpendek, dan editor.

Gambar 3.22 Tampilan Menu Perancangan Lintasan Terpendek

Untuk menu “Peta“ pada perancangan lintasan terpendek terdiri dari menu: Buka peta

dan hapus peta.

61


Gambar 3.23 Tampilan Menu Peta

Untuk menu “Graph“ pada perancangan lintasan terpendek terdiri dari menu: Buka

graph dan simpan graph.

Gambar 3.24 Tampilan Menu Graph

Untuk menu “Cari Rute Terpendek“ pada perancangan lintasan terpendek terdiri dari

tampilan kalkulasi jarak dengan pemilihan algoritma Greedy atau Dijkstra.

62


Gambar 3.25 Tampilan Menu Cari Lintasan Terpendek

Untuk menu “Editor“ pada perancangan lintasan terpendek terdiri dari menu:

1. Titik terdiri dari:

a. Titik Baru

b. Ganti Warna Background

c. Ganti Warna Border

d. Ubah Ukuran

Gambar 3.26 Tampilan Menu Editor Titik

63


2. Jalan terdiri dari:

a. Garis

b. Panah

Gambar 3.27 Tampilan Menu Editor Jalan

3. Hapus terdiri dari:

a. Jalan

b. Titik

Gambar 3.28 Tampilan Menu Editor Hapus

4. Tambahkan Caption terdiri dari:

a. Titik terdiri dari Tengah, Atas, Bawah

64


b. Jalan

Gambar 3.29 Tampilan Menu Tambah Caption

3.7.3 Halaman Hasil

Halaman hasil digunakan untuk melihat tampilan hasil dari program aplikasi

pencarian lintasan terpendek yang telah dijalankan. Setelah menu editor dirancang

sesuai dengan kebutuhan maka untuk menu cari rute terpendek akan menampilkan

hasil kalkulasi jarak yang telah diperoleh, kemudian pilih algoritma yang diinginkan

yaitu algoritma Greedy atau Dijkstra, setelah menekan tombol cari rute terpendek

akan diperoleh hasil lintasan yang dilalui dan jarak yang minimum diperoleh.

Tampilan halaman hasil menggunakan algoritma Greedy atau Dijkstra adalah sebagai

berikut:

65


Gambar 3.30 Implementasi Form Graph Algoritma Dijkstra

Gambar 3.31 Implementasi Form Hasil Komputasi Algoritma Dijkstra

Gambar 3.32 Implementasi Form Graph Algoritma Greedy

Gambar 3.33 Implementasi Form Hasil Komputasi Algoritma Greedy

66


3.7.4 Kebutuhan Perangkat

Adapun perangkat keras dan perangkat lunak yang digunakan pada saat mplementasi

algoritma Greedy dan algoritma Dijkstra adalah dengan spesifikasi sebagai berikut:

1. Procesessor Pentium IV 1,8D GHz

2. Memory 512 MB

3. Harddisk 40 GB

4. O/S Windows XP

5. Monitor Samsung 17’’

Dari hasil percobaan yang dilakukan untuk menentukan perbedaan jarak lintasan

terpendek pada algoritma Greedy dan Dijkstra serta untuk melakukan pengujian,

dipilih sejumlah Graph dengan lintasan berbeda-beda yaitu:

Tabel 3.12 Beda Jarak

Lintasan

Terpendek Algoritma Greedy dan Dijktra

No. Nama File Jarak Lintasan Terpendek

Dijkstra Greedy

67


010203040506070

1 2 3 4 5Dijkstra Greedy

Jarak Lintasan Terpendek Algoritma Greedy dan Dijkstra

Jara

k L

inta

san

Ter

pend

ek

Gambar 3.34 Grafik Jarak Lintasan Terpendek Algoritma Greedy dan Dijkstra

1 Coba 1. tzr 10 13

2 Coba 2.tzr 12 27

3 Coba 3.tzr 14 38

4 Coba 4.tzr 18 54

5 Coba 5.tzr 20 59

68


BAB 4

KESIMPULAN DAN SARAN

4.1 Kesimpulan

Dari penelitian dan hasil implementasi mengenai perbandingan algoritma Greedy dan

Dijkstra berdasarkan jarak lintasannya, algoritma Greedy menghasilkan jarak yang

lebih besar seperti pada file Coba2.tzr jumlah jarak yang diperoleh adalah 27,

sedangkan pada algoritma Dijkstra jarak yang diperoleh adalah 12. Algoritma Greedy

tidak beroperasi secara menyeluruh terhadap semua alternatif fungsi yang ada,

sehingga lintasan terpendek hanya diperoleh dari verteks asal hingga verteks tujuan,

sedangkan algoritma Dijkstra beroperasi secara menyeluruh terhadap semua alternatif

fungsi yang ada, sehingga lintasan terpendek tidak hanya diperoleh dari node sumber

ke node tujuan saja, akan tetapi lintasan terpendek dapat diperoleh dari semua node.

4.2 Saran

Sebagai saran yang ditujukan kepada pembaca yang ingin menentukan lintasan

terpendek dengan menggunakan algoritma Greedy dan Dijkstra, agar dapat

mengembangkan aplikasi ini dan menyelesaikan persoalan lintasan terpendek dalam

69


cakupan yang lebih besar dan mengimplementasikannya dengan bahasa pemograman

yang berbeda dan menggunakan algoritma yang berbeda.

DAFTAR PUSTAKA

Chartrand, Gary and Ortrud R. O, 1993. Apllied and Algorithmic Graph Theory, McGraw. Hill, Inc.

C.L.LIU, 1995. Dasar-dasar Matematika Diskrit, Jakarta. PT. Gramedia Pustaka Utama.

Jek Siang, Jong, 2002. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer, Yogyakarta, Andi.

James, R. Evans et al Optimization for Network and Graph.

Kurniasari, Yeni, 2006. Penerapan Algoritma Greedy.

Lutfi, Hendratmono Arief, 2008. Algoritma Dijkstra untuk menemukan jarak terpendek dengan menggunakan strategi greedy.

Prama, Irvan, 2006. Algoritma Greedy Untuk Mencari Lintasan Terpendek.

Robin J. Wilson and John J. Watkins, 1990. Graphs an Introductory Approach, John Wiley & Sons, Inc.

Setiadi, Robert, 2008. Algoritma Itu Mudah, Jakarta. PT. Prima Infosarana Media.

70


Townsend, Michael, 1987. Discrete Mathemathic : Applied Combinatorics and Graph Theory, The Benjamin/Cummings Publishing Company, Inc.

Y. Fazmah, Arif, 2006. Desain dan Analisis Strategi, Bandung.

LAMPIRAN : LISTING PROGRAM Option Explicit Dim sFrom As String Dim sTo As String Const INF = 32767 ' infinity, so big so far, it should end somewhere

anyway :) Dim sRESULT(1 To 100) As String Dim iRES_SIZE As Integer Private Function TotalJarak(path As String) As Double Dim x1 As Integer, x2 As Integer TotalJarak = 0 Dim ArrPath() As String, a As Integer ArrPath = Split(path, " ") For a = LBound(ArrPath) To UBound(ArrPath) - 2 If a < UBound(ArrPath) Then x1 = ArrPath(a) x2 = ArrPath(a + 1) TotalJarak = TotalJarak + jarak(x1, x2) End If Next x1 = ArrPath(UBound(ArrPath) - 1) x2 = ArrPath(LBound(ArrPath)) TotalJarak = TotalJarak + jarak(x1, x2) End Function Private Function CariTerpendek(awal As Integer) 'On Error GoTo errhandle Dim Nc As Integer Dim s As Integer, a As Integer, b As Integer, l As Integer, k As

Integer, X As Integer, j As Integer, u As Integer, ndx As Integer

Dim N As Integer, kotadipilih As Integer, i As Integer Dim M As Integer Dim p() As Single Dim totP As Single Dim Js() As Double Dim q() As Double Dim T As Integer Dim r As Double Dim kt As String, kt2 As String Dim temu As Boolean Dim PanjangJalur() As Double Dim JlrTerpendek() As Double Dim btemp() Dim temp As Double, temp2 As Double

71


Dim Hasil() As String N = UBound(jarak) 'jlh M = UBound(jarak) Nc = 1 For a = 1 To N For b = 1 To N Tho(a, b) = Tij Dtho(a, b) = 0 Next Next Nc = 1 ReDim JlrTerpendek(Ncmax) Dim oldtimer As Single oldtimer = Timer Do ReDim Tabu(N, N) s = 0 l = 0 l = l + 1 For k = 1 To N Tabu(k, l) = k Next s = s + 1 ReDim p(N) For X = 1 To N - 1 T = X ReDim Js(N) For a = 1 To N If Tabu(a, T) <> 0 Then Js(Tabu(a, T)) = Js(Tabu(a, T)) + 1 End If Next kt = "" For a = 1 To N kt = kt & Js(a) & " " Next For j = 1 To N totP = 0 For u = 1 To N If Not CariTabu(j, u, T) Then totP = totP + Tho(Tabu(j, T), u) ^ alpa *

visib(Tabu(j, T), u) ^ Beta End If Next u kt = "" kt2 = "" For u = 1 To N If CariTabu(j, u, T) = False Then p(u) = (Tho(Tabu(j, T), u) ^ alpa * visib(Tabu(j,

T), u) ^ Beta) / totP Else p(u) = 0 End If kt = kt & Format(p(u), "#,##0.000") & " " Next 'komulatif For u = 1 To N If u = 1 Then q(u) = p(u) Else

72


q(u) = q(u - 1) + p(u) End If kt2 = kt2 & Format(q(u), "#,##0.000") & " " Next 'random ulang_random: r = Rnd(1) temu = False ndx = 1 Do While temu = False If r < q(ndx) Then temu = True kotadipilih = ndx ElseIf (r > q(ndx)) And (r <= q(ndx + 1)) Then temu = True kotadipilih = ndx + 1 End If ndx = ndx + 1 Loop Tabu(j, T + 1) = kotadipilih kt = "" For u = 1 To T + 1 kt = kt & (Tabu(j, u)) & " " Next Hasil(Nc, j) = kt Next j T = T + 1 Next ReDim PanjangJalur(N) JlrTerpendek(Nc) = 1.79769313486232E+307 temp = 0 For k = 1 To N temp = HitungLk(k) PanjangJalur(k) = temp If temp < JlrTerpendek(Nc) Then JlrTerpendek(Nc) = temp End If Next For k = 1 To N PanjangJalur(k) = HitungLk(k) For s = 1 To N - 1 Dtho(Tabu(k, s), Tabu(k, s + 1)) = _ Dtho(Tabu(k, s), Tabu(k, s + 1)) + visib(Tabu(k, s),

Tabu(k, s + 1)) / PanjangJalur(k) Next Next kt = "" For i = 1 To N kt = "" For k = 1 To N Tho(i, k) = rho * Tho(i, k) + Dtho(i, k) kt = kt & Format(Tho(i, k), "#,##0.0000") & " " Next Next Nc = Nc + 1 DoEvents Loop Until (Nc > Ncmax) Dim BandingJarak As Double, sk As Integer BandingJarak = 1.79769313486232E+307 temp = 0

73


For a = LBound(Hasil) To UBound(Hasil) temp = TotalJarak(Hasil(a, awal)) If temp < BandingJarak Then BandingJarak = temp sk = a End If Next Private Function konversiHasil(ha As String) As String makeAllLines_Black Dim arrHa() As String, Ka As String, a As Integer, sF As String, sT

As String arrHa() = Split(ha, " ") 'MsgBox frmPeta.theBlockCollection(Int(arrHa(1))).sCaption For a = LBound(arrHa) To UBound(arrHa) - 1 Ka = Ka & frmPeta.theBlockCollection(Int(arrHa(a))).sCaption & "

- " ' Debug.Print frmPeta.theBlockCollection(Int(arrHa(A))).sCaption If a = 0 Then sF = frmPeta.theBlockCollection(Int(arrHa(a))).sCaption sT = frmPeta.theBlockCollection(Int(arrHa(a))).sCaption Else sF = sT sT = frmPeta.theBlockCollection(Int(arrHa(a))).sCaption redLINE sF, sT sF = sT End If ' MsgBox Ka Next redLINE sF, sT konversiHasil = Ka End Function Private Sub CbAlgoritma_KeyPress(KeyAscii As Integer) KeyAscii = 0 End Sub Private Sub cmdCalcData_Click() Dim i As Integer Dim j As Integer Dim toIndex As Integer flxMap.Rows = frmPeta.theBlockCollection.Count + 1 flxMap.Cols = frmPeta.theBlockCollection.Count + 1 If frmPeta.theBlockCollection.Count > 0 Then flxMap.FixedRows = 1 flxMap.FixedCols = 1 End If For i = 0 To flxMap.Cols - 1 flxMap.ColWidth(i) = 530 Next i For i = 1 To frmPeta.theBlockCollection.Count flxMap.row = i flxMap.col = 0 flxMap.Text = frmPeta.theBlockCollection(i).sCaption flxMap.row = 0 flxMap.col = i flxMap.Text = frmPeta.theBlockCollection(i).sCaption flxMap.row = i For j = 1 To flxMap.Cols - 1 flxMap.TextMatrix(i, j) = "0" flxMap.col = j flxMap.CellForeColor = vbBlack

74


flxMap.CellFontBold = False Next j For j = 1 To frmPeta.theLineCollection.Count If frmPeta.theLineCollection(j).sFrom =

frmPeta.theBlockCollection(i).TagID Then toIndex =

frmPeta.theBlockCollection.getIndexFromTag(frmPeta.theLineCollection(j).sTo)

flxMap.col = toIndex flxMap.Text = frmPeta.theLineCollection(j).sCaption If (flxMap.Text = "") Then flxMap.Text = "1" ' don't

allow empty!!!! (for lines with no caption) flxMap.CellForeColor = vbRed flxMap.CellFontBold = True End If Next j Next i 'Input Jarak ReDim jarak(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1) ReDim visib(Me.flxMap.Rows - 1, Me.flxMap.Rows - 1) For i = 1 To Me.flxMap.Rows - 1 For j = 1 To Me.flxMap.Cols - 1 jarak(i, j) = flxMap.TextMatrix(i, j) If jarak(i, j) = 0 Then visib(i, j) = 0 ' Else visib(i, j) = Round(1 / jarak(i, j), 2) End If Next Next End Sub Private Sub prepareFSP() Dim i As Integer flxS.Rows = 2 flxDist.Rows = 2 flxPath.Rows = 2 flxS.Cols = flxMap.Cols flxDist.Cols = flxMap.Cols flxPath.Cols = flxMap.Cols If flxS.Cols > 1 Then flxS.FixedRows = 1 flxDist.FixedRows = 1 flxPath.FixedRows = 1 flxS.FixedCols = 1 flxDist.FixedCols = 1 flxPath.FixedCols = 1 End If For i = 0 To flxS.Cols - 1 flxS.ColWidth(i) = flxMap.ColWidth(i) flxDist.ColWidth(i) = flxMap.ColWidth(i) flxPath.ColWidth(i) = flxMap.ColWidth(i) flxS.TextMatrix(0, i) = flxMap.TextMatrix(0, i) flxDist.TextMatrix(0, i) = flxMap.TextMatrix(0, i) flxPath.TextMatrix(0, i) = flxMap.TextMatrix(0, i) Next i For i = 1 To flxS.Cols - 1 flxS.TextMatrix(1, i) = "False" flxS.row = 1 flxS.col = i flxS.CellForeColor = vbBlack

75


flxS.CellFontBold = False flxDist.TextMatrix(1, i) = "INF" flxPath.TextMatrix(1, i) = "0" Next i End Sub Private Sub cmdFindShortPath_Click() If Me.CbAlgoritma.Text = "Djakstra" Then prepareFSP Dim src As Integer Dim dest As Integer src = getIndexOfTabName(sFrom) dest = getIndexOfTabName(sTo) If (src = -1) Or (dest = -1) Then MsgBox "something wrong!!!" Exit Sub End If ' working with first row always! flxS.row = 1 flxDist.row = 1 flxPath.row = 1 Dim MAX As Integer MAX = flxMap.Cols Option Base 1 Public Sub CboKota_Click() Dim X As Integer jlhKota = CInt(CboKota.Text) jlhSemut = jlhKota If CboKota.Text <> "" Then Flex.Rows = jlhKota + 1 For X = 1 To jlhKota Flex.TextMatrix(X, 0) = X Next Flex.col = 2 Flex.row = 2 End If End Sub

76


perbandingan algoritma greedy dan dijkstra untuk menentukan

Documents