i

SIMULASI JARINGAN JALAN DI KOTA SEMARANG

BERBASIS ALGORITMA FLOYD-WARSHALL

UNTUK MENANGANI MASALAH LINTASAN

TERPENDEK

skripsi

disajikan sebagai salah satu syarat

untuk memperoleh gelar Sarjana Sains

Program Studi Matematika

oleh

Harsono

4111411031

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS NEGERI SEMARANG

2015

ii

iii

iv

MOTTO DAN PERSEMBAHAN

Motto:

Jadilah diri sendiri dan jangan menjadi orang lain, walaupun dia terlihat lebih

baik dari kita.

Kita akan sukses jika belajar dari kesalahan.

Tidak ada manusia yang terlahir sempurna tapi kerja keras dan doa lah yang akan

membuat manusia terlihat sempurna.

Persembahan:

Bapak, Ibu dan Kakak yang tak henti-hentinya

memberikan doa, semangat, dan dukungan.

Untuk keluarga Matematika 2011.

Almamaterku.

v

PRAKATA

Puji syukur ke hadirat illahi robbi Allah SWT atas segala limpahan rahmat

dan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini. Selama

menyusun skripsi ini, penulis telah banyak menerima bantuan, bimbingan, dan

dukungan dari berbagai pihak. Oleh karena itu, dalam kesempatan ini penulis

sampaikan ucapan terima kasih kepada:

1. Prof. Dr. Fathur Rohman, M.Hum, Rektor Universitas Negeri Semarang.

2. Prof. Dr. Wiyanto, M.Si, Dekan Fakultas Matematika dan Ilmu Pengetahuan

Alam (FMIPA) Universitas Negeri Semarang.

3. Drs. Arief Agoestanto, M.Si, Ketua Jurusan Matematika Universitas Negeri

Semarang.

4. Dra. Kristina Wijayanti, M.Si, Ketua prodi Matematika FMIPA Universitas

Negeri Semarang.

5. Dr. Mulyono, M.Si, Pembimbing I yang telah memberikan bimbingan dan

arahan dalam penyusunan skripsi ini.

6. Drs Amin Suyitno, M.Pd, Pembimbing II yang telah memberikan bimbingan

dan arahan dalam penyusunan skripsi ini.

7. Bapak dan Ibu Dosen Jurusan Matematika yang telah memberikan bekal ilmu

dalam penyusunan skripsi ini.

8. Teman-teman ”Matematika angkatan 2011” yang saya sayangi.

9. Bapak, Ibu, dan Kakak yang selalu memberi doa, bantuan, dan dukungan

sebagai semangat dalam hidupku.

vi

10. Semua pihak yang telah membantu terselesaikannya skripsi ini yang tidak

dapat penulis sebutkan satu per satu.

Semoga Allah SWT senantiasa memberikan balasan atas bantuan dan amal

baiknya. Akhirnya penulis berharap semoga skripsi ini bermanfaat bagi pembaca

demi kebaikan di masa yang akan datang.

Semarang, 17 September 2015

Penulis

vii

ABSTRAK

Harsono. 2015. Simulasi Jaringan Jalan di Kota Semarang Berbasis Algoritma

Floyd-Warshall untuk Menangani Masalah Lintasan Terpendek. Skripsi, jurusan

Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas

Negeri Semarang. Pembimbing Utama Dr. Mulyono, M.Si dan Pembimbing

Pendamping Drs. Amin Suyitno, M.Pd.

Kata kunci: Simulasi, algoritma Floyd-Warshall, lintasan terpendek

Jaringan transportasi di kota-kota besar seperti halnya kota Semarang pada

umumnya masih mempunyai jaringan yang rumit. Orang akan kebingungan untuk

menentukan jalan yang harus dilewati agar sampai tempat tujuan yang belum

pernah dikunjunginya dan jalan yang akan dilalui menjadi lebih panjang, sehingga

dibutuhkan jalan terpendek untuk sampai ke tempat tujuan. Algoritma Floyd-

Warshall merupakan algoritma yang digunakan untuk mencari semua lintasan

terpendek antara setiap kemungkinan dua titik yang berbeda. Penelitian ini

bertujuan untuk Mengetahui hasil program simulasi jaringan jalan di kota

Semarang dengan menggunakan algoritma Floyd-Warshall dengan bahasa

pemrograman Visual Basic dan membuktikan bahwa penghitungan manual

mempunyai hasil yang sama dengan penghitungan dengan simulasi jaringan jalan

di kota Semarang dalam mencari lintasan terpendek pada graf.

Penentuan lintasan terpendek pada graf yang direpresentasikan dengan

mengambil data jalan di kota Semarang yang dilakukan dari tempat-tempat yang

telah ditentukan dengan menggunakan algoritma Floyd-Warshall. Jalan yang akan

dilalui jalan yag dapat digunakan kedua arah sehingga dapat digambarkan sebagai

graf tidak berarah dan berbobot, bobot yang digunakan adalah panjang jalan

antara dua tempat, titik merepresentasikan sebuah tempat yang telah ditentukan

sebelumnya, dan sisi sebagai jalan yang dilalui. Simulasi algoritma Floyd-

Warshall untuk menangani masalah pencarian lintasan terpendek pada suatu graf

merupakan hasil dari perancangan dan pembuatan dengan bahasa pemrograman

Visual Basic. Simulasi ini dapat menghasilkan lintasan terpendek dan panjang

minimum dari titik awal ke titik tujuan pada graf yang telah direpresentasikan ke

dalam program simulasi. Dari data jaringan jalan di kota Semarang yang

direpresentasikan, ke dalam bentuk graf setelah diuji coba menggunakan simulasi

ternyata mempunyai solusi hasil lintasan dan jarak yang sama dengan perhitungan

manual. Dengan demikian, simulasi algoritma Floyd-Warshall dalam menangani

masalah lintasan terpendek pada suatu graf menggunakan Visual Basic selesai

direalisasikan dan dapat diimplementasikan pada permasalahan sehari-hari yang

dapat direpresentasikan dalam bentuk graf dan dicari lintasan terpendeknya.

viii

DAFTAR ISI

Halaman

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

PERNYATAAN .................................................................................................. ii

HALAMAN PENGESAHAN ............................................................................ iii

MOTTO DAN PERSEMBAHAN ..................................................................... iv

PRAKATA .......................................................................................................... v

ABSTRAK ......................................................................................................... vii

DAFTAR ISI ..................................................................................................... viii

DAFTAR TABEL ............................................................................................... xi

DAFTAR GAMBAR .......................................................................................... xii

DAFTAR LAMPIRAN ...................................................................................... xiii

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

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

1.2 Rumusan Masalah ............................................................................ 5

1.3 Batasan Masalah .. ............................................................................ 6

1.4 Tujuan Penelitian ............................................................................. 7

1.5 Manfaat Penelitian ............................................................................ 7

1.6 Sistematika Penulisan ....................................................................... 8

BAB II TINJAUAN PUSTAKA ................................................................... 10

2.1 Teori Graf .................................................................................... 10

2.1.1 Definisi Teori Graf .......................................................... 10

2.1.2 Terminologi Graf. ............................................................. 11

2.1.3 Jenis-jenis Graf ................................................................ 11

2.1.4 Representasi Graf ............................................................. 14

2.1.5 Keterhubungan pada Graf ................................................. 17

2.2 Lintasan Terpendek .................................................................... 19

2.3 Algoritma Floyd-Warshall .......................................................... 26

2.3.1 Algoritma Floyd-Warshall untuk graf berarah .................. 26

2.3.2 Algoritma Floyd-Warshall untuk graf tidak berarah ......... 27

2.4 Simulasi ....................................................................................... 29

ix

2.4.1 Definisi Simulasi ................................................................ 29

2.4.2 Kelebihan dari simulasi ...................................................... 29

2.5 Visual Basic ................................................................................ 30

BAB III METODE PENELITIAN .................................................................. 33

BAB IV HASIL DAN PEMBAHASAN ......................................................... 38

4.1 Proses Manual Pencarian Lintasan Terpendek Menggunakan

Algoritma Floyd-Warshall ......................................................... 43

4.1.1 Ubah graf ke dalam bentuk matriks .................................. 44

4.1.2 Lakukan iterasi untuk k=1 sampai n ................................. 44

4.1.2.1 Iterasi untuk k=1 ..................................................... 44

4.1.2.2 Iterasi untuk k=2 ..................................................... 46

4.1.2.3 Iterasi untuk k=3 ..................................................... 47

4.1.2.4 Iterasi untuk k=4 ..................................................... 49

4.1.2.5 Iterasi untuk k=5 ..................................................... 50

4.1.2.6 Iterasi untuk k=6 ..................................................... 51

4.1.2.7 Iterasi untuk k=7 ..................................................... 52

4.1.2.8 Iterasi untuk k=8 ..................................................... 53

4.1.2.9 Iterasi untuk k=9 ..................................................... 54

4.1.2.10 Iterasi untuk k=10 ................................................. 55

4.1.2.11 Iterasi untuk k=11 ................................................. 56

4.1.2.12 Iterasi untuk k=12 ................................................. 57

4.1.2.13 Iterasi untuk k=13 ................................................. 58

4.1.2.14 Iterasi untuk k=14 ................................................. 59

4.1.2.15 Iterasi untuk k=15 ................................................. 60

4.1.2.16 Iterasi untuk k=16 ................................................. 61

4.1.2.17 Iterasi untuk k=17 ................................................ 62

4.2 Tahap Perancangan Simulasi dan Pembuatan Simulasi .............. 63

4.2.1 Tahap Perancangan Simulasi .............................................. 63

4.2.1.1 Analisis ...................................................................... 63

4.2.1.2 Rancangan Simulasi .................................................. 63

4.2.1.3 Flowchart Algoritma Floyd-Warshall ....................... 65

x

4.2.1.4 Data Flow Diagram (DFD) ...................................... 67

4.2.1.5 Desain tampilan ......................................................... 69

4.2.2 Tahap pembuatan program ................................................. 70

4.3 Tahap Implentasi Simulasi .......................................................... 71

BAB V PENUTUP ......................................................................................... 73

5.1 Simpulan ..................................................................................... 74

5.2 Saran ........................................................................................... 75

DAFTAR PUSTAKA ......................................................................................... 76

LAMPIRAN

xi

DAFTAR TABEL

Halaman'

Gambar 4.1 Data tempat dan jarak wilayah kota Semarang ............................... 38

xii

DAFTAR GAMBAR

Halaman'

Gambar 2.1 Graf berarah dan berbobot............................................................... 12

Gambar 2.2 Graf tidak berarah dan berbobot...................................................... 13

Gambar 2.3 Graf berarah dan tidak berbobot...................................................... 13

Gambar 2.4 Graf tidak berarah dan tidak berbobot............................................. 14

Gambar 2.5 Representasi Graf ............................................................................ 15

Gambar 2.6 Contoh Graf ..................................................................................... 19

Gambar 2.7 Graf Berbobot .................................................................................. 24

Gambar 2.8 Interface Visual Basic 6.0 ............................................................... 32

Gambar 2.9 Bagian-bagian New Project ............................................................. 32

Gambar 4.1 Representasi Graf W ....................................................................... 42

Gambar 4.2 Rancangan simulasi ......................................................................... 65

Gambar 4.3 Flowchart Algoritma Floyd-Warshall ............................................. 66

Gambar 4.4 Data Flow Diagram (DFD) Level 0 ............................................... 67

Gambar 4.5 Data Flow Diagram (DFD) Level 1 ............................................... 68

Gambar 4.6 Desain Tampilan ............................................................................. 70

Gambar 4.7 Tampilan program ........................................................................... 71

Gambar 4.8 Representasi graf pada simulasi ...................................................... 71

Gambar 4.9 Hasil pencarian lintasan terpendek .................................................. 72

xiii

DAFTAR LAMPIRAN

Halaman

Lampiran 1 Analisis Manual………………………………………………... 79

Lampiran 2 Listing Program……………………………………………… 116

1

BAB I

PENDAHULUAN

1.1 Latar Belakang

Teori graf merupakan salah satu cabang matematika yang menarik

untuk dibahas karena berkaitan dengan permasalahan yang banyak

ditemui dalam kehidupan sehari-hari. Teori graf banyak digunakan untuk

mempermudah menyelesaikan suatu masalah. Dengan merepresentasikan

persoalan ke dalam bentuk graf, maka persoalan dapat dijelaskan secara

lebih sederhana. Graf merupakan model matematika yang sangat

kompleks dan rumit, tapi biasa juga menjadi solusi yang sangat baik

terhadap beberapa kasus tertentu. Banyak sekali aplikasi menggunakan

graf sebagai alat untuk mempresentasikan atau memodelkan persoalan

sehingga persoalan itu dapat diselesaikan dengan baik. Aplikasi-aplikasi

tersebut misalnya menentukan lintasan terpendek (the shortest path

problem), persoalan tukang pos, penjadwalan ujian, penentuan frekuensi

radio mobile, dan masih banyak lagi (Budayasa, 2007:47).

Pencarian lintasan terpendek merupakan suatu masalah yang paling

banyak dibahas dan dipelajari sejak akhir tahun 1950. Pencarian lintasan

terpendek ini telah diterapkan diberbagai bidang untuk mengoptimasi

kinerja suatu sistem, baik untuk meminimalkan biaya atau mempercepat

jalannya suatu proses (Purwananto et al., 2005:94). Masalah lintasan

terpendek secara umum dijelaskan menggunakan konsep graf dapat

2

berupa graf berarah atau graf tidak berarah. Sisi dalam sebuah graf tidak

berarah dapat dianggap memungkinkan perjalanan kedua arah.

Sebaliknya, sisi dalam graf berarah hanya dapat digunakan untuk satu

arah perjalanan. Biasanya dalam menentukan lintasan terpendek dengan

menggunakan graf berbobot. Setiap sisi dalam graf berbobot terdapat

suatu nilai atau bobot (Sushma, 2013:8).

Sebuah struktur graf dikembangkan dengan memberi bobot pada

tiap sisi. Graf berbobot dapat digunakan untuk melambangkan berbagai

konsep. Sebagai contoh jika suatu graf melambangkan jaringan jalan

maka bobotnya bisa berarti panjang jalan, waktu tempuh maupun batas

kecepatan tertinggi jalan tertentu, sehingga untuk menentukan lintasan

terpendek diperlukan graf berbobot.

Kesulitan menentukan lintasan terpendek timbul karena terdapat

banyak jalan yang ada dari suatu daerah ke daerah lain sehingga

memungkinkan memilih jalan alternatif apabila terdapat suatu hambatan

pada jalan terpendek utama. Kebutuhan untuk menemukan lintasan

terpendek dan waktu tempuh tercepat tentunya juga diperhitungkan untuk

menghindari kerugian seperti contoh bagi sebuah industri. Kebutuhan

untuk segera sampai tempat tujuan tepat waktu bahkan diharapkan bisa

lebih cepat sangatlah dibutuhkan mengingat persaingan industri saat ini

yang mementingkan kepuasan pelanggan dan menghindari kerugian

karena kerusakan barang. Hal itu dapat saja terjadi bila terjadi

pemblokiran jalan secara tiba-tiba pada jalan yang seharusnya dilalui,

3

selain untuk industri lintasan terpendek juga dibutuhkan untuk

menghemat waktu tempuh bagi wisatawan yang ingin bepergian ke

tempat wisata (Ratnasari et al., 2013:29). Dalam mencari lintasan

terpendek, semakin banyak titik dan garis pada graf akan semakin rumit

(Mardlootillah et al., 2014:57). Salah satu aplikasi pencarian lintasan

terpendek yang paling menarik untuk dibahas adalah pada masalah

transportasi (Purwananto et al., 2005:94).

Transportasi merupakan salah satu bagian penting manusia dalam

kehidupan sehari-hari. Dengan transportasi manusia bisa berpindah dari

satu tempat ke tempat lainya dengan lebih mudah. Salah satu sistem

transportasi yang paling menarik tersebut adalah transportasi kota,

misalkan penentuan lintasan perjalanan dari suatu tempat ke tempat

tujuan dalam satu kota. Sistem transportasi perjalanan ini merupakan

model jaringan. Hal ini dapat digambarkan dengan tempat-tempat tertentu

sebagai titik dan jalan yang menghubungkan tempat-tempat tersebut

sebagai garis/sisi.

Jaringan transportasi pada kota besar seperti halnya kota Semarang

pada umumnya masih mempunyai jaringan yang rumit. Orang akan

mengetahui jalan yang harus dilewati untuk sampai ke tempat tujuan yang

biasa dikunjunginya, akan tetapi jika tempat tujuan tersebut belum pernah

dikunjungi rata-rata mereka sering kesulitan untuk menentukan jalan

yang harus dilewati untuk mencapai tempat tersebut. Selama ini orang

akan bertanya kepada orang lain yang mengetahui betul jaringan

4

transportasi di kota tersebut. Sehingga jalan yang mereka lalui menjadi

lebih jauh dan dapat membutuhkan lebih banyak waktu serta tenaga yang

mereka keluarkan lebih banyak.

Menurut Li, sebagaimana dikutip oleh Xiao-Yan & Yan-Li

(2010:48), bahwa biaya transportasi merupakan komponen yang sangat

signifikan. Biaya yang dikeluarkan oleh negara berkembang untuk

transportasi sebesar 30% dari total biaya ekonomi nasional, sedangkan

negara maju hanya 10%. Artinya, hanya dari biaya transportasi, negara

berkembang memiliki selisih 20% dari negara maju. Selama dapat

menghemat biaya transportasi maka negara berkembang dapat

menghemat 10% dari biaya yang ada. Setiap orang dalam melakukan

perjalanan pasti memilih lintasan terpendek untuk mencapai tempat

tujuannya, karena dapat menghemat waktu, tenaga serta biaya. Ada

banyak algoritma yang dapat digunakan untuk menentukan lintasan

terpendek pada sebuah graf diantaranya algoritma Djikstra, algoritma

Bellman Ford dan algoritma Floyd-Warshall. Dalam penelitian ini

peneliti menggunakan algoritma Floyd-Warshall untuk pencarian lintasan

terpendek.

Masalah pencarian lintasan terpendek pada teori graf berkaitan

dengan masalah pengoptimuman, antara lain meminimumkan biaya dan

efisiensi waktu yang diselesaikan dalam algoritma Floyd Warshall atau

algoritma Djikstra (Syukria et al., 2013:74). Algoritma Floyd-Warshall

merupakan bagian dari program dinamik yang dapat mencari semua

5

lintasan terpendek masing-masing antara tiap kemungkinan pasang

tempat yang berbeda (All-pairs Shortest Path Problems) dan sangat

efektif digunakan dalam menangani masalah lintasan optimum (Saputra,

2011:19). Menurut Bahri, sebagaimana dikutip oleh Syukria et al.

(2013:74), algoritma Floyd-Warshall lebih efisien dibandingkan dengan

algoritma Djikstra untuk menentukan masalah lintasan terpendek karena

dengan melakukan sekali analisis akan didapatkan hasil lintasan

terpendek setiap pasangan sisi.

Berdasarkan uraian tersebut peneliti memutuskan untuk melakukan

penelitian tentang Simulasi jaringan jalan di Kota Semarang berbasis

algoritma Floyd-Warshall untuk menangani masalah lintasan terpendek.

1.2 Rumusan Masalah

Berdasarkan latar belakang masalah yang telah dijelaskan, maka

rumusan masalah yang akan dikaji dalam penelitian ini adalah sebagai

berikut.

1. Apakah penghitungan manual mempunyai hasil yang sama dengan

penghitungan dengan simulasi jaringan jalan kota Semarang dalam

mencari lintasan terpendek pada graf?

2. Bagaimana hasil program simulasi jaringan jalan kota Semarang

dengan menggunakan algoritma Floyd-Warshall dengan bahasa

pemrograman Visual Basic?

6

1.3 Batasan Masalah

Batasan masalah yang dilakukan dalam penelitian ini adalah sebagai

berikut.

1. Tempat-tempat yang akan menjadi titik dalam penelitian ini dibagi

berdasarkan kecamatan yang ada di kota Semarang. Tempat-

tempat tersebut tidak semua kecamatan yang ada di kota Semarang

hanya diambil tempat-tempat yang mewakili kota Semarang. Titik-

titik tersebut adalah sebagai berikut.

a. Genuk : Terminal Terboyo

RSI Sultan Agung

b. Pedurungan : Terminal Penggaron

RSJ Dr. Amino Gondohutomo

RS Bhayangkara TK III Semarang

c. Tembalang : RSUD Kota Semarang

d. Banyumanik : Terminal Banyumanik

e. Semarang Tengah : RS Telogorejo

f. Semarang Selatan : RS Kariadi

RS Roemani Muhammadiyah

g. Candisari : RS St Elizabeth

h. Semarang Barat : Bandara Ahmad Yani

i. Semarang Utara : Stasiun Tawang

Stasiun Poncol

j. Tugu : Terminal Mangkang

7

RSUD Tugurejo Semarang

k. Ngaliyan : RS Permata Medika

2. Simulasi ini menggunakan bahasa pemrograman Visual Basic dan

tidak sampai pada tahap online.

3. Jalan yang digunakan penelitian ini adalah jalan yang bisa kedua

arah dan program simulasi yang dibuat adalah program simulasi

pencarian lintasan terpendek pada graf tidak berarah.

1.4 Tujuan Penelitian

Tujuan dilakukannya penelitian ini adalah sebagai berikut.

1. Membuktikan bahwa penghitungan manual mempunyai hasil yang

sama dengan penghitungan dengan simulasi jaringan jalan kota

Semarang dalam mencari lintasan terpendek pada graf.

2. Mengetahui hasil program simulasi jaringan jalan kota Semarang

dengan menggunakan algoritma Floyd-Warshall dengan bahasa

pemrograman Visual Basic.

1.5 Manfaat Penelitian

Manfaat dari penelitian ini adalah sebagai berikut.

1) Bagi Penulis

Mengetahui dan memahami aplikasi teori graf terutama

Algoritma Floyd-Warshall terhadap jaringan jalan di kota

Semarang.

8

2) Bagi Universitas

Dari hasil penelitian ini dapat menjadi referensi yang

berkaitan dengan teori graf dalam menyelesaikan masalah

menghitung lintasan terpendek.

3) Bagi Masyarakat Umum

Memberikan informasi jalan yang harus dilewati agar

sampai ke tempat tujuan dengan jarak dan biaya yang efisien serta

dapat menghemat waktu perjalanan.

1.6 Sistematika Penulisan

Secara garis besar sistematika penulisan skripsi ini dibagi menjadi 3

bagian, yaitu: bagian awal, bagian isi, dan bagian akhir skripsi. Untuk

memberikan gambaran yang jelas tentang skripsi ini dan memudahkan

pembaca dalam menelaah isi skripsi ini maka skripsi ini disusun secara

sistematis yaitu sebagai berikut.

1. Bagian Awal skripsi

Berisi halaman judul, halaman pengesahan, halaman motto dan

persembahan, kata pengantar, daftar isi, daftar tabel, daftar lampiran dan

abstrak.

2. Bagian inti yang terdiri atas lima bab. Kelima bab tersebut adalah

sebagai berikut:

a. Bab I : Pendahuluan

9

Pada bab pendahuluan ini dikemukakan latar belakang masalah,

rumusan masalah, batasan masalah, tujuan dan manfaat penelitian

dan sistematika penulisan skripsi.

b. Bab II: Tinjauan Pustaka

Tinjauan pustaka merupakan teori-teori yang mendasari pemecahan

dari permasalahan yang disajikan. Tinjauan pustaka ini terdiri dari:

Teori Graf, Lintasan Terpendek, Algoritma Floyd Warshall, Simulasi

dan Visual Basic.

c. Bab III : Metode Penelitian.

Memaparkan tentang prosedur dan langkah-langkah yang dilakukan

dalam penelitian ini meliputi identifikasi dan perumusan masalah,

studi pustaka, pengumpulan data, perancangan dan pembuatan

simulasi, implementasi simulasi, evaluasi program simulasi dan

penarikan kesimpulan.

d. Bab IV : Hasil Penelitian dan Pembahasan

Dalam bab ini berisikan pembahasan dan analisis dari penelitian.

e. Bab V : Penutup

Berisi tentang kesimpulan dari hasil pembahasan dan saran yang

ditujukan untuk pembaca umumnya dan bagi penulis sendiri

khususnya.

3. Bagian Akhir Skripsi

Bagian akhir berisikan daftar pustaka sebagai acuan penulis dan

lampiran-lampiran yang mendukung kelengkapan skripsi.

10

BAB II

TINJAUAN PUSTAKA

2.1 Teori Graf

2.1.1 Definisi Teori Graf

Sebuah graf G berisikan dua himpunan yaitu himpunan berhingga tak

kosong V(G) dari objek-objek yang disebut titik dan himpunan berhingga

(mungkin kosong) E(G) yang elemen-elemennya disebut dengan sisi

sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak

berurutan dari titik-titik di V(G). Himpunan V(G) disebut himpunan titik G

dan himpunan E(G) disebut himpunan sisi G (Budayasa, 2007:1).

Banyaknya titik pada graf G dapat dinyatakan dengan n = |V(G)|. Sedangkan

Banyaknya sisi pada graf G dapat dinyatakan dengan m = |E(G)|.

Titik pada graf dapat dilabeli dengan huruf, misalkan v, w, ..., atau

dengan menggunakan bilangan asli 1, 2, 3, ..., atau gabungan keduanya

( . Sedangkan sisi yang menghubungkan titik dengan titik

dinyatakan dengan pasangan ( , ), atau dengan lambang , , ... Dengan

kata lain, jika e adalah sisi yang menghubungkan titik dengan titik ,

maka e dapat dituliskan sebagai e = ( , ), di mana i,j adalah indeks angka

bilangan asli 1, 2, 3, ...

11

2.1.2 Terminologi Graf

Ada beberapa terminologi dari teori graf yang digunakan untuk

menjelaskan yang dilihat ketika melihat suatu graf. Graf dapat dilihat dari

komponen-komponen penyusunnya.

1. Derajat (Degree)

Derajat (Degree) suatu titik yang disimbolkan dengan d(v) adalah

jumlah sisi yang berada pada titik tersebut.

2. Gelung (loop)

Gelung (loop) adalah sebuah sisi graf yang menghubungkan sebuah titik

dengan dirinya sendiri.

3. Sisi ganda/sisi rangkap

Jika terdapat lebih dari satu sisi yang menghubungkan dua titik dan

pada suatu graf maka sisi-sisinya disebut sisi ganda/sisi rangkap

2.1.3 Jenis-jenis Graf

Berdasarkan keberadaan loop dan sisi ganda, graf digolongkan menjadi

dua jenis:

1. Graf sederhana (simple graph) adalah graf yang tidak mengandung

loop dan sisi ganda.

2. Graf rangkap (multi graph) adalah graf yang mengandung sisi ganda

tetapi tidak mengandung loop.

12

Menurut arah dan bobotnya, graf dibagi menjadi empat bagian, yaitu:

1. Graf berarah dan berbobot adalah graf yang setiap sisinya mempunyai

anak panah yang menunjukkan arah dan berbobot. Gambar 2.1

menunjukkan graf berarah dan berbobot yang terdiri atas tujuh titik

yaitu titik dan . Titik menunjukkan arah ke

titik dan titik . titik menunjukkan kearah titik , dan titik

, dan seterusnya. Bobot antara titik ke adalah 2, titik ke

adalah 4 dan seterusnya.

Gambar 2.1 Graf berarah dan berbobot

2. Graf tidak berarah dan berbobot adalah graf yang setiap sisinya tidak

mempunyai anak panah yang menunjukkan arah tetapi mempunyai

bobot. Gambar 2.2 menunjukkan graf tidak berarah dan berbobot. Graf

terdiri dari tujuh titik yaitu titik dan . Titik

tidak menunjukkan arah ke titik atau , namun bobot antara titik

dan titik telah diketahui. Begitu juga dengan titik yang lain.

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

2

4

6

3

2

3

2

7 5

6

6 3

13

Gambar 2.2 Graf tidak berarah dan berbobot

3. Graf berarah dan tidak berbobot adalah graf yang setiap sisinya

mempunyai anak panah yang tidak berbobot. Gambar 2.3

menunjukkan graf berarah dan tidak berbobot. Graf terdiri dari tujuh

titik yaitu titik dan . Titik menunjukkan arah

ke titik atau . Titik menunjukkan kearah titik , dan titik

, dan seterusnya.

Gambar 2.3 Graf berarah dan tidak berbobot

4. Graf tidak berarah dan tidak berbobot adalah graf yang setiap sisinya

tidak mempunyai anak panah dan tidak berbobot. Gambar 2.4

menunjukkan graf tidak berarah dan tidak berbobot. Graf terdiri dari

tujuh titik yaitu titik dan .

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

2

4

6

3

2

3

2

7 5

6

6 3

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

14

Gambar 2.4 Graf tidak berarah dan tidak berbobot

Sebuah struktur graf bisa dikembangkan dengan memberi

bobot atau nilai pada tiap sisi di mana merupakan suatu nilai yang

dapat berupa biaya, jarak atau waktu, graf semacam ini disebut graf

berbobot (weighted graph).

2.1.4 Representasi Graf

Suatu graf dapat direpresentasikan ke beberapa bentuk. Reprentasi

graf dapat digunakan untuk mengimplementasikan graf tersebut ke dalam

bentuk tertentu, sehingga dapat digunakan pada berbagai kasus berbeda.

Gambar 2.5 merupakan contoh representasi graf.

Gambar 2.5 Representasi Graf

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣8

𝑣

𝑒

𝑒

𝑒

𝑒

𝑒

𝑒

𝑒

𝑒 𝑒8

𝑒 0

𝑒9 𝑒

15

Reprentasi graf yang sering digunakan adalah sebagai berikut.

1. Matriks ketetanggaan (Adjacency Matrix)

Suatu matriks digunakan untuk menyatakan hubungan

ketetanggaan setiap titik dalam baris-barisnya. Nomor baris menyatakan

nomor titik ketetanggaan berasal dan nomor kolom menunjukkan nomor

titik ke mana arah ketetanggaan. Elemen matriks [ , ] berharga 1 bila

terdapat sisi dari ke dan berharga 0 bila tidak ada. Keuntungan

representasi dengan matriks ketetanggaan adalah dapat mengakses

elemen matriksnya langsung apakah titik dan bertetangga. Jumlah

baris dan kolom matriks ketetanggaan sama dengan jumlah titik dalam

graf.

Misalkan G adalah sebuah graf dengan n titik. Matriks ketetanggan

dari graf G adalah matriks bujur sangkar (persegi) berordo n, X(G) = ,

dengan elemen menyatakan banyaknya sisi yang menghubungkan

titik ke-i ke titik ke-j. Dengan definisi ini memungkinkan untuk

menyatakan sebuah graf yang memiliki sisi paralel atau loop dengan

matriks ketetanggaan (Sutarno, et al., 2005:83).

[ ] {

16

(

)

2. Matriks bersisian (Incidenty matrix)

Matriks bersisian menyatakan kebersisian titik dengan sisi.

Misalkan G(V, E) adalah graf dengan n titik dan m buah sisi. Matriks

bersisian G adalah matriks yang berukuran n x m. baris menunjukkan

label titik, sedangkan kolom menunjukkan label sisinya. Bila matriks

tersebut dinamakan A = [ ] maka

[ ] {

8 9 0

(

)

A =

A =

17

2.1.5 Keterhubungan pada Graf

1) Jalan (Walk)

Jalan atau walk pada suatu Graf G adalah barisan titik dan sisi

berganti-ganti. , , , , …, ; ,

sisi

menghubungkan

dan :

dapat hanya ditulis barisan sisi atau barisan titik saja.

,…, ; atau , ,…, ; , .

Dalam hal ini,

disebut titik

awal, dan disebut titik akhir, sedangkan titik-titik yang berada

diantara dan adalah titik-titik internalnya.

2) Jalan tertutup

Menurut Budayasa (2007:6), misalkan G adalah sebuah graf. Sebuah

jalan W dengan panjang positif disebut tertutup, jika titik awal dan titik

akhir dari W identik (sama). Sebuah titik G mungkin saja muncul lebih

dari satu kali dalam jalan W, begitu juga dengan sebuah sisi G, boleh

muncul lebih dari satu kali pada jalan W.

3) Jejak (Trail)

Jejak adalah jalan (Walk) yang semua sisi dalam barisan adalah

berbeda atau tanpa sisi berulang.

4) Lintasan (Path)

Lintasan adalah jalan (Walk) dengan semua titik dan sisi dalam barisan

yang berbeda atau jejak dengan titik yang berbeda.

5) Sirkuit

18

Sirkuit adalah jejak tertutup. Jejak tertutup adalah jejak dengan titik

awal dan titik akhir sama.

6) Sikel (Cycle)

Menurut Budayasa (2007:6), sebuah Cycle adalah adalah jejak tertutup

(closed trail) yang titik awal dan semua titik internalnya berbeda.

Banyaknya sisi dalam suatu sikel disebut panjang dari sikel tersebut.

Sikel dengan panjang k disebut sikel-k, disimbolkan dengan .

2.2 Lintasan Terpendek

Lintasan terpendek merupakan salah satu dari masalah yang dapat

diselesaikan dengan graf. Jika diberikan sebuah graf berbobot, masalah

lintasan terpendek adalah bagaimana cara mencari sebuah lintasan pada graf

yang dapat meminimalkan jumlah bobot sisi pembentuk lintasan tersebut.

Misalkan u dan v dua titik di graf G, lintasan (u,v) di G dengan panjang

minimum disebut lintasan terpendek (Budayasa, 2007:47). Ada beberapa

macam persoalan lintasan terpendek antara lain:

a. Lintasan terpendek antara dua buah titik tertentu (a pair shortest path)

b. Lintasan terpendek antara semua pasangan titik (all pairs shortest path)

c. Lintasan terpendek dari titik tertentu ke semua titik yang lain.

d. Lintasan terpendek antara dua buah titik yang melalui beberapa titik

tertentu (intermediate shortest path)

Beberapa algoritma yang digunakan untuk menyelesaikan persoalan ini

adalah algoritma Dijkstra, algoritma Bellman-Ford, dan algoritma Floyd-

19

Warshall. Setiap algoritma penyelesaian persoalan lintasan terpendek memiliki

kriteria masing-masing. Dalam penelitian ini peneliti menggunakan Algoritma

Floyd-Warshall untuk pencarian lintasan terpendek.

Gambar 2.6 Contoh Graf

Pada Gambar 2.6 misalkan kota merupakan kota awal dan kota

merupakan kota tujuan. Dari kota awal sampai kota tujuan dapat dipilih

beberapa lintasan sebagai berikut.

→ → → → → = 2 + 6 + 3 + 5 + 7 = 23

→ → → → → = 2 + 6 + 3 + 6 + 3 = 20

→ → → → = 2 + 6 + 3 + 6 = 17

→ → → → = 2 + 6 + 2 + 3 = 13

→ → → → = 2 + 2 + 6 + 3 = 13

→ → → → = 2 + 2 + 5 + 7 = 16

→ → → = 2 + 2 + 6 = 10

→ → → = 2 + 3 + 7 = 12

→ → → → = 4 + 3 + 5 + 7 = 19

→ → → → = 4 + 3 + 6 + 3 = 16

𝑣

𝑣

𝑣

𝑣

𝑣

𝑣 𝑣

2

4

6

3

2

3

2

7 5

6

6 3

20

→ → → = 4 + 3 + 6 = 13

→ → → = 4 + 2 + 3 = 9

Berdasarkan data di atas, lintasan terpendek dari ke adalah 9 dengan

melewati dan .

2.3 Algoritma Floyd Warshall

2.3.1 Algoritma Floyd Warshall untuk Graf Berarah

Algoritma yang ditemukan oleh Warshall untuk mencari lintasan

terpendek merupakan algoritma algoritma yang sederhana dan mudah

implementasinya. Masukan Algoritma Warshall adalah matriks hubung graf

berarah berlabel dan keluarannya adalah lintasan terpendek dari semua titik

ke semua titik (Siang, 2004). Dalam usaha untuk mencari lintasan terpendek,

algoritma Floyd-Warshall memulai iterasi dari titik awalnya kemudian

memperpanjang lintasan dengan mengevaluasi titik demi titik hingga

mencapai titik tujuan dengan bobot yang seminimum mungkin.

Menurut Novandi, sebagaimana dikutip oleh Nur & Setiawan,

(2013:21), Algoritma Floyd-Warshall adalah sebuah algoritma analisis graf

untuk mencari bobot minimum dari graf berarah. Dalam pengertian lain

Algoritma Floyd-Warshall adalah suatu metode yang melakukan pemecahan

masalah dengan memandang solusi yang akan diperoleh sebagai suatu

keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari

solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih

21

dari satu. Algoritma Floyd-Warshall memiliki input graf berbobot (V,E),

yang berupa daftar titik (node/verteks V) dan daftar sisi (edge E). Jumlah

bobot sisi-sisi pada sebuah lintasan adalah bobot sisi tersebut. Sisi pada E

diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi

graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini

menghitung bobot terkecil dari semua sisi yang menghubungkan sebuah

pasangan titik dan melakukannya sekaligus untuk semua pasangan titik.

Prinsip yang dipegang oleh algoritma Floyd-Warshall adalah prinsip

optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu

tahap (misalnya tahap ke-i) juga optimal.

Menurut Siang, sebagaimana dikutip oleh Sani et al. (2013:3),

algoritma Floyd-Warshall untuk mencari lintasan terpendek, Dimisalkan

adalah matriks ketetanggaan awal graf berarah berbobot. adalah matriks

ketetanggaan berbobot terkecil dengan sama dengan lintasan terpendek

dari titik ke .

1) 0

2) Untuk =1 hingga , lakukan:

Untuk =1 hingga , lakukan:

Untuk =1 hingga lakukan:

3) Jika W[ ,j] > W[ , ] + [ , ] maka

Tukar [ ,j] dengan [ , ] + [ , ]

4) =

22

Algoritma Floyd-Warshall adalah salah satu algoritma dari

pemrograman dinamis, yaitu suatu metode yang melakukan pemecahan

masalah dengan memandang solusi yang akan diperoleh sebagai suatu

keputusan yang saling terkait, artinya solusi-solusi tersebut dibentuk dari

solusi yang berasal dari tahap sebelumnya dan ada kemungkinan lebih dari

satu solusi. Algoritma Floyd-Warshall juga membandingkan semua

kemungkinan lintasan pada graf untuk setiap sisi dari semua titik. Algoritma

Floyd-Warshall menerapkan pemrograman dinamis sehingga lebih menjamin

keberhasilan penemuan solusi optimum untuk kasus penemuan lintasan

terpendek.

Peran pemrograman dinamis yang mencoba untuk memberikan solusi

yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari

pengambilan keputusan dari suatu tahap. Prinsip yang dipegang oleh

pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total

optimal, maka bagian solusi sampai suatu tahap juga optimal.

Algoritma Floyd-Warshall merupakan salah satu jenis algoritma all pair

shortest, yaitu mencari lintasan terpendek untuk semua pasangan titik yang

ada pada sebuah graf. Input dari algoritma ini berupa graf berbobot dan

berarah. Seperti algoritma bellman Ford, algoritma ini juga dapat menghitung

sisi yang berbobot negatif. Cara kerja algoritma ini dapat digambarkan

dengan menggunakan matriks.

23

2.3.2 Algoritma Floyd Warshall Untuk Graf Tidak Berarah

Algoritma Floyd-Warshall dikembangkan oleh R. W. Floyd sehingga

matriksnya merupakan graf berbobot dan bukan lagi matriks Boolean.

Algoritma Floyd-Warshall dapat digunakan untuk mencari jarak antara

semua titik dalam graf. Algoritma ini sangat efisien dari sudut pandang

penyimpanan data karena dapat diimplementasikan dengan hanya

pengubahan sebuah matriks jarak.

Algoritma Floyd-Warshall memiliki input graf tak berarah dan

berbobot (V,E), yang berupa himpunan titik (titik V) dan himpunan sisi (sisi

E). Bobot sisi e dapat diberi symbol d(i,j).

Diketahui n titik dalam graf tidak berarah adalah v1, v2, v3, ……., vn

untuk menentukan lintasan terpendek di antara semua pasangan titik, dengan

langkah sebagai berikut:

Langkah 1: untuk i≠j, jika adalah sisi, ambil d(i,j) sebagai bobot dari

sisi tersebut. Jika tidak ada sisi yang menghubungkan langsung

antara i dan j ditulis d(i,j) = ∞. Untuk i=j, maka ditulis d(i,j) =0.

Langkah 2: untuk k=1 sampai n

Untuk i, j =1 sampai n

Ditulis d(i,j) = min{ + d(k,j) }

Nilai akhir dari d(i,j) adalah jarak dari ke .(Goodaire &

Parmeter, 1998:382)

Dari prosedur di atas dapat dilihat bahwa pada iterasi ke-k (1≤k≤n)

24

Mula-mula algoritma untuk jarak dari ke adalah panjang dari sisi

ke adalah panjang sisi . Setelah iterasi pertama pada langkah 2 (k=1),

jarak yang diperoleh digantikan dengan panjang dari lintasan . Setelah

iterasi k pada algoritma ini dapat ditentukan jarak terpendek dari ke

pada titik-titik , , ….., . jarak adalah setelah iterasi ke k=n dengan

mengambil d(i,j) sebagai lintasan terpendek dari i ke j

Gambar 2.7 merupakan contoh graf berbobot yang akan digunakan dalam

penerapan dari algoritma Floyd-Warshall

Gambar 2.7 : Graf Berbobot

Bentuk matriksnya adalah sebagai berikut.

(

)

1

3 9

5

1

𝑽𝟏

𝑽𝟒 𝑽𝟑

𝑽𝟐

25

K=1

d(1,1) {d(1,1), d(1,1) + d(1,1)}= min{0, 0 + 0} = 0

d(1,2) {d(1,2), d(1,1) + d(1,2)} = min{5, 0 + 5} = 5

d(1,3) {d(1,3), d(1,1) + d(1,3)} = min{9, 0 + 9} = 9

d(1,4) {d(1,4), d(1,1) + d(1,4)} = min{∞, 0 + ∞} = ∞

d(2,1) {d(2,1),d(2,1) + d(1,1)} = min{5, 5 + 0} = 5

d(2,2) {d(2,2), d(2,1) + d(1,2)} = min{0, 5 + 5} = 0

d(2,3) {d(2,3), d(2,1) + d(1,3)} = min{3, 5 + 9} = 3

d(2,4) {d(2,4), d(2,1) + d(1,4)} = min{1, 5 + ∞} = 1

d(3,1) {d(3,1), d(3,1) + d(1,3)} = min{9, 9 + 0} = 9

d(3,2) {d(3,2), d(3,1) + d(1,2)} = min{3, 9 + 5} = 3

d(3,3) {d(3,3), d(3,1) + d(1,3)} = min{0, 9 + 9} = 0

d(3,4) {d(3,4), d(3,1) + d(1,4)} = min{1, 9 + ∞} = 1

d(4,1) {d(4,1), d(4,1) + d(1,1)} = min{∞, ∞ + 0} = ∞

d(4,2) {d(4,2), d(4,1) + d(1,2)} = min{1, ∞ + 5} = 1

d(4,3) {d(4,3), d(4,1) + d(1,3)} = min{1, ∞ + 9} = 1

d(4,4) {d(4,4), d(4,1) + d(1,4)} = min{0, ∞ + ∞} = 0

Sehingga diperoleh matriksnya sebagai berikut.

(

)

K = 2

d(1,1) {d(1,1), d(1,2) + d(2,1)} = min{0, 5 + 5} = 0

26

d(1,2) {d(1,2), d(1,2) + d(2,2)} = min{5, 5 + 0} = 5

d(1,3) {d(1,3), d(1,2) + d(2,3)} = min{9, 5 + 3} = 8

d(1,4) {d(1,4), d(1,2) + d(2,4)} = min{∞, 5 + 1} = 6

d(2,1) {d(2,1), d(2,2) + d(2,1)} = min{5, 0 + 5} = 5

d(2,2) {d(2,2), d(2,2) + d(2,2)} = min{0, 0 + 0} = 0

d(2,3) {d(2,3), d(2,2) + d(2,3)} = min{3, 0 + 3} = 3

d(2,4) {d(2,4), d(2,2) + d(2,4)} = min{1, 0 + 1} = 1

d(3,1) {d(3,1), d(3,2) + d(2,3)} = min{9, 3 + 5} = 8

d(3,2) {d(3,2), d(3,2) + d(2,2)} = min{3, 3 + 0} = 3

d(3,3) {d(3,3), d(3,2) + d(2,3)} = min{0, 3 + 3} = 0

d(3,4) {d(3,4), d(3,2) + d(2,4)} = min{1, 3 + 1} = 1

d(4,1) {d(4,1), d(4,2) + d(2,1)} = min{∞, 1 + 5} = 6

d(4,2) {d(4,2), d(4,2) + d(2,2)} = min{1, 1 + 0} = 1

d(4,3) {d(4,3), d(4,2) + d(2,3)} = min{1, 1 + 3} = 1

d(4,4) {d(4,4), d(4,2) + d(2,4)} = min{0, 1 + 1} = 0

Sehingga diperoleh matriksnya sebagai berikut

(

)

K = 3

d(1,1) {d(1,1), d(1,3) + d(3,1)} = min{0, 8 + 8}= 0

d(1,2) {d(1,2), d(1,3) + d(3,2)} = min{5, 8 + 3} = 5

d(1,3) {d(1,3), d(1,3) + d(3,3)} = min{8, 8 + 0} = 8

27

d(1,4) {d(1,4), d(1,3) + d(3,4)} = min{9, 8 + 1} = 9

d(2,1) {d(2,1), d(2,3) + d(3,1)} = min{5, 3 + 8} = 5

d(2,2) {d(2,2), d(2,3) + d(3,2)} = min{0, 3 + 3}= 0

d(2,3) {d(2,3), d(2,3) + d(3,3)} = min{3, 3 + 0} = 3

d(2,4) {d(2,4), d(2,3) + d(3,4)} = min{1, 3 + 1} = 1

d(3,1) {d(3,1), d(3,3) + d(3,1)} = min{8, 0 +8} = 8

d(3,2) {d(3,2), d(3,3) + d(3,2)} = min{3, 0 + 3} = 3

d(3,3) {d(3,3), d(3,3) + d(3,3)} = min{0, 0 + 0} = 0

d(3,4) {d(3,4), d(3,3) + d(3,4)} = min{1, 0 + 1} = 1

d(4,1) {d(4,1), d(4,3) + d(3,1)} = min{6, 1 + 8} = 6

d(4,2) {d(4,2), d(4,3) + d(3,2)} = min{1, 1 +3} = 1

d(4,3) {d(4,3), d(4,3) + d(3,3)} = min{1, 1 + 0} = 1

d(4,4) {d(4,4), d(4,3) + d(3,4)}= min{0, 1 + 1} = 0

Sehingga diperoleh matriksnya sebagai berikut

(

)

K = 4

d(1,1) {d(1,1), d(1,4) + W(4,1)} = min{0, 6 + 5} = 0

d(1,2) {d(1,2), d(1,4) + W(4,2)} = min{5, 6 + 1} = 5

d(1,3) {d(1,3), d(1,4) + d(4,3)} = min{8, 6 + 1} = 7

d(1,4) {d(1,4), d(1,4) + d(4,4)} = min{6, 6 + 0} = 6

28

d(2,1) {d(2,1), d(2,4) + d(4,1)} = min{5, 1 + 6} = 5

d(2,2) {d(2,2), d(2,4) + d(4,2)} = min{0, 1 + 1} = 0

d(2,3) {d(2,3), d(2,4) + d(4,3)} = min{3, 1 + 1} = 2

d(2,4) {d(2,4) , d(2,4) +d(4,4)} = min{1, 1 + 0} = 1

d(3,1) {d(3,1), d(3,4) + d(4,1)} = min{8, 1 + 6} = 7

d(3,2) {d(3,2), d(3,4) + d(4,2)} = min{3, 1 + 1} = 2

d(3,3) {d(3,3), d(3,4) + d(4,3)} = min{0, 1 + 1} = 0

d(3,4) {d(3,4), d(3,4) + d(4,4)} = min{1, 1 + 0} = 1

d(4,1) {d(4,1), d(4,4) + d(4,1)} = min{6, 0 + 6} = 6

d(4,2) {d(4,2), d(4,4) + d(4,2)} = min{1, 0 + 1} = 1

d(4,3) {d(4,3), d(4,4) + d(4,3)} = min{1, 0 + 1} = 1

d(4,4) {d(4,4), d(4,4) + d(4,4)} = min{0, 0 + 0} = 0

Sehingga diperoleh matriksnya sebagai berikut

(

)

Sehingga diperoleh suatu lintasan terpendek pada setiap titiknya. Dari

matriks di atas dapat ditarik sebuah kesimpulan bahwa jarak dari titik ke

adalah 0, jarak dari titik ke adalah 5, ke adalah 7, ke

adalah 6 dan sebagainya.

29

2.4 Simulasi

2.4.1 Definisi Simulasi

Simulasi dapat dipandang sebagai suatu model matematis yang

menerangkan perilaku sistem dari waktu ke waktu. Simulasi merupakan

teknik numerik untuk melakukan percobaan pada suatu komputer digital,

di mana didalamnya mengandung sejumlah hubungan matematis yang

logis dan diperlukan untuk menggambarkan struktur dan tingkah laku

sistem dunia nyata yang kompleks pada periode yang cukup panjang.

2.4.2 Kelebihan dari simulasi

Beberapa Kelebihan dari simulasi adalah:

1. Tidak semua sistem dapat direpresentasikan dalam model

matematis, simulasi merupakan alternatif yang tepat untuk

menyelesaikan permasalahan tersebut.

2. Dapat bereksperimen tanpa adanya resiko pada sistem nyata.

Dengan simulasi memungkinkan untuk melakukan percobaan

terhadap sistem tanpa harus menaggung resiko terhadap sistem

yang berjalan.

3. Simulasi dapat mengestimasi kinerja sistem pada kondisi tertentu

dan memberikan alternative desain terbaik sesuai dengan

spesifikasi yang diinginkan.

4. Simulasi memungkinkan untuk melakukan studi jangka panjang

dalam waktu yan relatif singkat.

30

5. Dapat menggunakan input data bervariasi.

2.5 Visual Basic

VB (Visual Basic) merupakan bahasa pemrograman komputer

yang lengkap dan mudah digunakan untuk membuat suatu aplikasi dalam

Microsoft Windows dengan menggunakan metode Grafical User Interface

(GUI). Visual Basic memudahkan pemrograman untuk berinteraksi

langsung dengan elemen-elemen di dalam setiap bentuk pemrograman.

Microsoft Visual Basic berawal dari bahasa pemrograman BASIC

(Beginners All Purpose Symbolic Instruction Code), yaitu sebuah bahasa

pemrograman.Visual Basic dapat digunakan sebagai alat bantu untuk

membuat berbagai macam program komputer. Aplikasi yang dapat

dihasilkan dengan bahasa pemrograman (LPKBM, 2002:3).

Kepopuleran Visual Basic sebenarnya datang dari lingkungan yang

sering disebut Integrated Development Environment atau IDE. IDE

membantu membangun sebuah aplikasi besar, menulis sebuah program,

menjalankan program, dan menghasilkan sebuah executable file.

Executable file yang dihasilkan oleh Visual Basic bersifat independen, dan

karena itu file tersebut dapat dijalankan pada komputer tanpa harus

menginstal Visual Basic.

Visual Basic selain disebut sebagai bahasa pemrograman juga

sering disebut sarana (tool) untuk menghasilkan program-program aplikasi

31

berbasis windows. Beberapa kemampuan atau manfaat dari visual basic

diantaranya seperti:

1. Untuk membuat program aplikasi berbasis windows

2. Untuk membuat objek-objek pembantu program seperti kontrol

Activex, File, Help, Aplikasi internet dan sebagainya.

3. Menguji program dan menghasilkan program akhir berakhiran EXE

yang bersifat Executable atau dapat langsung dijalankan

Visual Basic 6.0 sebetulnya perkembangan dari versi sebelumnya

dengan beberapa penambahan komponen yang sedang tren saat ini, seperti

kemampuan pemrograman internet dengan Dynamic HyperText Mark

Language (DHTML), dan beberapa penambahan fitur database dan

multimedia yang semakin baik. Sampai saat buku ini ditulis bisa dikatakan

bahwa Visual Basic 6.0 masih merupakan pilih pertama di dalam membuat

program aplikasi yang ada di pasar perangkat lunak nasional. Hal ini

disebabkan oleh kemudahan dalam melakukan proses development dari

aplikasi yang dibuat. Untuk lebih jelasnya tentang interface Visual Basic 6

bisa dilihat di Gambar 2.8

32

Visual Basic dapat dioperasikan melalui tombol Start > Programs >

Microsoft Visual Studio 6.0 > Microsoft Visual Basic 6.0 tunggulah beberapa saat

hingga muncul Gambar 2.9.

Gambar 2.9 Bagian-bagian New Project

Pilih Standard EXE dan klik tombol Open.

Gambar 2.8 Interface Visual Basic 6.0

33

BAB III

METODE PENELITAN

Untuk melakukan penelitian harus memperhatikan prosedur dan langkah-

langkah yang akan dilakukan untuk memulai penelitian sehingga dapat terarah

dan terlaksana dengan baik. Dalam hal pelaporan penelitian ini terbagi

menjadi beberapa tahapan sebagai berikut:

3.1 Identifikasi masalah dan Perumusan masalah

Tahap identifikasi masalah adalah tahap menemukan permasalahan

sebelum dilakukannya penelitian. Dengan menemukan permasalahan yang

ditemukan pada objek yang diteliti guna mencari alternatif solusi yang

terkait dengan permasalahan. Identifikasi masalah dilakukan untuk

memperoleh gambaran yang lengkap tentang ruang lingkup masalah dan

langkah yang tepat dalam mencari pemecahanya. Identifikasi masalah

pada penelitian ini adalah mengamati fakta-fakta yang ada di lapangan

yang terdapat beberapa hal yang ingin dikaji. Fakta yang ada di lapangan

diketahui bahwa terdapat permasalahan yang dapat dibahas mengenai

perjalanan masyarakat yang berada di kota-kota besar sering kesulitan

untuk mencari jalan tercepat untuk mencapai tempat tujuan. Akibatnya

mereka sering membuang-buang waktu, tenaga dan biaya agar dapat

sampai ke tempat tujuan. Dengan banyaknya jalan yang akan dilalui maka

34

untuk memperoleh jalan terpendek harus dilakukan perhitungan yang baik

agar perjalanan yang dilalui dapat dilakukan secara efisien.

Kemudian dibuat perumusan masalah agar permasalahan tersebut

menjadi jelas dan pembahasan tidak terlalu luas. Perumusan masalah ini

dilakukan dengan melihat permasalahan-permasalahan yang ada ketika

melakukan perjalanan. Saat ini kota Semarang memiliki banyak jalan

utama. Dengan adanya banyak jalan yang ada akan dicari lintasan yang

efisien dalam perjalanan.

3.2 Studi pustaka

Dalam studi pustaka ini digunakan sumber pustaka yang relevan

yang digunakan untuk mengumpulkan informasi yang diperlukan dalam

penelitian. Studi pustaka dengan mengumpulkan sumber pustaka yang

dapat berupa dokumen-dokumen, referensi-referensi, buku-buku, sumber

dari internet, atau sumber-sumber lain yang diperlukan untuk merancang

dan mengimplementasikan aplikasi. Studi pustaka yang dilakukan antara

lain memahami teori dasar yang digunakan, cara menyelesaikan

permasalahan penelitian, metode penelitian dan sebagainya. Pada akhirnya

sumber pustaka itu dijadikan landasan untuk menganalisis permasalahan.

Studi pustaka ini penting untuk dilakukan karena menjadi modal dasar

penyelesaian dalam sebuah penelitian. Studi pustaka juga membantu

dalam persiapan memperkirakan data-data yang dibutuhkan dalam proses

penelitian.

35

3.3 Pengumpulan Data

Pengumpulan data pada penelitian ini dilakukan dengan cara

observasi menggunakan google map. Peneliti mengadakan observasi

jaringan jalan yang ada di kota Semarang menggunakan google map

dengan tujuan untuk mengetahui jalan-jalan yang ada di kota Semarang.

Observasi ini dilakukan untuk mendapatkan informasi-informasi yang

dibutuhkan untuk melanjutkan penelitian. Pada observasi ini peneliti

menggunakan google map untuk mengetahui panjang suatu jalan yang

dilalui.

3.4 Perancangan dan Pembuatan Program Simulasi

Langkah awal dari tahap ini adalah mencari lintasan terpendek dari

setiap titik ke semua titik dalam graf. Panjang jalan yang diperoleh dari

pengambilan data yang telah dilakukan sebelumnya. Langkah penelitian

yang paling penting dan paling kompleks dalam metodologi penelitian ini

adalah perancangan model simulasi. Hal ini dikarenakan perancangan

model simulasi harus sesuai dengan data yang telah ada dan

mengimplementasikan model simulasi yang diinginkan. Acuan

perancangan model simulasi ini dari analisis kebutuhan. Pada tahap

perancangan simulasi ini akan digunakan program Visual Basic. Tahap

perancangan simulasi bertujuan untuk menghasilkan sebuah bentuk atau

format sistem simulasi yang optimal dengan memperhatikan kebutuhan-

36

kebutuhan sistem simulasi yang telah ditentukan dalam tahapan

perancangan simulasi. Setelah dilakukan perancangan simulasi, tahap

berikutnya adalah tahap pembuatan simulasi pencarian lintasan terpendek

pada graf menggunakan algoritma Floyd-Warshall. Pembuatan simulasi ini

mengacu pada tahap perancangan simulasi pada tahap sebelumnya.

3.5 Implementasi Simulasi

Tahapan implementasi sistem simulasi merupakan tahap pengujian

program. Dalam pengujian program, sistem simulasi akan diuji apakah

sistem simulasi dapat menyelesaikan pencarian lintasan terpendek dari

graf yang direprentasikan.

3.6 Evaluasi Program Simulasi

Menguji coba seluruh spesifikasi terstruktur dan sistem secara

keseluruhan. Pada tahap ini, dilakukan uji coba sistem yang telah selesai

disusun. Proses uji coba ini diperlukan untuk memastikan bahwa sistem

yang telah dibuat sudah benar, sesuai dengan karakteristik yang ditetapkan

dan tidak ada kesalahan-kesalahan yang terkandung didalamnya.

3.7 Penarikan kesimpulan

Berdasarkan semua penelitian yang telah dilakukan, maka

ditariklah kesimpulan untuk menjawab semua tujuan penelitian yang telah

ditetapkan pada awal penelitian. Pada tahap ini, sejumlah saran juga akan

37

diberikan terhadap masalah-masalah yang ditemukan sehingga penelitian

ini dapat bermanfaat bagi pengguna jalan.

74

BAB V

PENUTUP

5.1 Simpulan

Dari pembahasan dan analisis yang telah dilakukan, maka dapat diambil

beberapa simpulan sebagai berikut.

1. Berdasarkan hasil penghitungan manual dari ke diperoleh panjang

lintasannya adalah 24,5 dan hasil pengujian program simulasi algoritma

Floyd-Warshall dari ke diperoleh panjang lintasannya adalah 24,5.

Berdasarkan hasil penghitungan manual dan hasil pengujian program simulasi

algoritma Floyd-Warshall untuk menangani lintasan terpendek pada suatu

graf ini terbukti mempunyai solusi yang sama.

2. Berdasarkan data jaringan jalan di kota Semarang yang direpresentasikan ke

dalam bentuk graf dan dilakukan simulasi algoritma Floyd-Warshall untuk

menangani masalah pencarian lintasan terpendek. Simulasi ini merupakan

hasil dari perancangan dan pembuatan program dengan bahasa pemrograman

Visual Basic. Simulasi ini dapat menghasilkan lintasan terpendek dan jarak

untuk pencarian dari titik awal ke titik tujuan pada graf yang telah

direpresentasikan ke dalam program simulasi.

75

5.2 Saran

Aplikasi simulasi yang dibuat penulis dapat memudahkan pencarian lintasan

terpendek dan menghindari salah penghitungan khususnya untuk jenis graf yang

memiliki jumlah titik banyak. Penulis mempunyai beberapa saran yang ditujukan

kepada penulis selanjutnya diantaranya:

1. Simulasi ini baru dapat diterapkan pada graf tidak berarah, sehingga perlu

adanya pengembangan lebih lanjut pada graf berarah.

2. Program simulasi ini menggunakan bahasa pemrograman Visual Basic

sehingga tidak sampai pada tahap online. Untuk penulis selanjutnya semoga

menggunakan bahasa pemrograman yang bisa sampai online.

3. Terdapat data base untuk penyimpanan hasil programnya.

4. Dibutuhkan ketelitian dalam penghitungan manual dengan algoritma Floyd-

Warshall.

76

DAFTAR PUSTAKA

Budayasa, I K. 2007. Teori graf dan Aplikasinya. Surabaya: Unesa University

Press.

Goodaire, E. G dan Parmenter, M. M. 1998. Discrete Mathematics with Graf

Theory. Presenticehall, USA

LPKBM MADCOMS Madium . 2002 . Microsoft Visual Basic 6.0. Yogjakarta:

Andi OFFSETS.

Mardlootillah, H. I., Suyitno. A & Arini, F. Y. 2014. Simulasi Algoritma Djikstra

dalam Menangani Masalah Lintasan Terpendek [ada Graf Menggunakan

Visual Basic. UNNES Journal of Mathematics, 3(1): 56-61.

Nur, H.E. & Setiawan, A. 2013. Program Dinamis untuk Penentuan Lintasan

Terpendek dengan Pendekatan Algoritma Floyd-Warshall. Dinamika

Tehnik. VII(1): 17-25.

Purwananto, Y., Purwitasari, A., & Wibowo A. W. 2005. Implementasi dan

Analisis Algoritma Pencarian Rute Terpendek di Kota Surabaya. Jurnal

Penelitian dan Pengembangan TELEKOMUNIKASI, 10(2): 94-101.

Ratnasari, A., Ardiani, F. & Nurvita, F. A. 2013. Penentuan Jarak Terpendek

dan Jarak Terpendek Alternative Menggunakan Algoritma Djikstra Serta

Estimasi Waktu Tempuh. Seminar Nasional Teknologi Informasi &

Komunikasi Terapan 2013. Universitas Islam Indonesia.

Sani, A.F., Trastawati, N. K. T., & Dwipayana I. M. E. 2013. Algoritma Floyd

Warshall untuk Menentukan Jalur Terpendek Evakuasi Tsunami di

Kelurahan Sanur. E-Jurnal Matematika, 2(1): 1-5.

Saputra, R. 2011. Sistem Informasi Geografis Pencarian Rute Optimum Objek

Wisata

Kota Yogjakarta dengan Algoritma Floyd-Warshall. Jurnal Matematika,

14(1): 19-24.

Siang, J. 2004. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer.

Yogjakarta: ANDI.

Sushma, J. P. 2013. Shortest Path Algorithms Techniques. International Journal

of Science and Modern Engineering. 1(10):8-12

Sutarno, H., Priatna, N & Nurjanah. 2005. Matematika Diskrit. Malang: Penerbit

Universitas Negeri Malang.

77

.

Syukria, A., Johar, R., & Marwan. 2013. Kemampuan Komunikasi Matematis dan

Habits of Mind Mahasiswa pada Materi Lintasan Terpendek

Menggunakan Algoritma Floyd-Warshall. Jurnal Peluang, 1(2):71-80.

Xiao-Yan, L. & Yan-Li, C. 2010. Application of Djikstra Algorithm in Logistics

Distribution Lines. Proceedings International Symposium on

Computer Science and Computational Technology. Henan Polytechnic

University.

78

LAMPIRAN

79

Analisis Manual

K = 1

d(1,1) d(1,1), d(1,1) + d(1,1) 0, 0 + 0} = 0

d(1,2) d(1,2), d(1,1) + d(1,2)} + }

d(1,3) d(1,3), d(1,1) + d(1,3)} 0,9, 0 + 0,9} = 0,9

d(1,4) d(1,4), d(1,1) + d(1,4)} + }

d(1,5) , d(1,1) + d(1,5)} + }

d(1,6) d(1,1) + d(1,6)} + }

d(1,7) d(1,1) + d(1,7)} + }

d(1,8) d(1,1) + d(1,8)} + }

d(1,9) d(1,1) + d(1,9)} + }

d(1,10) d(1,1) + d(1,10)} + }

d(1,11) d(1,1) + d(1,11)} + }

d(1,12) d(1,1) + d(1,12)} + }

d(1,13) d(1,1) + d(1,13)} + }

d(1,14) d(1,14) d(1,1) + d(1,14)} + }

d(1,15) d(1,15), d(1,1) + d(1,15)} + }

d(1,16) d(1,16), d(1,1) + d(1,16)} + }

d(1,17) d(1,1) + d(1,17) } + }

d(2,1) d(2,1), d(2,1) + d(1,1)} + }

d(2,2) d(2,1) + d(1,2)} + }

d(2,3) d(2,3), d(2,1) + d(1,3) + }

80

d(2,4) d(2,4), d(2,1) + d(1,4)} 4,1, + }

d(2,5) d(2,5), d(2,1) + d(1,5)} 5,7, + }

d(2,6) d(2,6), d(2,1) + d(1,6)} + }

d(2,7) d(2,7), d(2,1) + d(1,7)} + }

d(2,8) d(2,8), d(2,1) + d(1,8)} + }

d(2,9) d(2,9), d(2,1) + d(1,9)} + }

d(2,10) d(2,10), d(2,1) + d(1,10)} + }

d(2,11) d(2,11), d(2,1) + d(1,11)} + }

d(2,12) d(2,12), d(2,1) + d(1,12)} + }

d(2,13) d(2,13), d(2,1) + d(1,13)} + }

d(2,14) d(2,14), d(2,1) + d(1,14)} + }

d(2,15) d(2,15), d(2,1) + d(1,15)} + }

d(2,16) d(2,16), d(2,1) + d(1,16)} + }

d(2,17) d(2,17), d(2,1) + d(1,17)} + }

d(3,1) d(3,1), d(3,1) + d(1,1)} 0,9, 0,9 + 0} = 0,9

d(3,2) d(3,1) + d(1,2)} 0,9 + } =

d(3,3) d(3,3), d(3,1) + d(1,3) 0,9 + 0,9} = 0

d(3,4) d(3,4), d(3,1) + d(1,4)} . 0,9 + } =

d(3,5) d(3,5), d(3,1) + d(1,5)} , + }

d(3,6) d(3,6), d(3,1) + d(1,6)} + }

d(3,7) d(3,7), d(3,1) + d(1,7)} 4,9, + }

d(3,8) d(3,8), d(3,1) + d(1,8)} + }

d(3,9) d(3,9), d(3,1) + d(1,9)} + }

d(3,10) d(3,10), d(3,1) + d(1,10)} + }

81

d(3,11) d(3,11), d(3,1) + d(1,11)} + }

d(3,12) d(3,12), d(3,1) + d(1,12)} + }

d(3,13) d(3,13), d(3,1) + d(1,13)} + }

d(3,14) d(3,14), d(3,1) + d(1,14)} + }

d(3,15) d(3,15), d(3,1) + d(1,15)} + }

d(3,16) d(3,16), d(3,1) + d(1,16)} + }

d(3,17) d(3,17), d(3,1) + d(1,17)} + }

d(4,1) d(4,1), d(4,1) + d(1,1)} + }

d(4,2) d(4,1) + d(1,2)} + } = 4,1

d(4,3) d(4,3), d(4,1) + d(1,3) + }

d(4,4) d(4,4), d(4,1) + d(1,4)} 0. + }

d(4,5) d(4,5), d(4,1) + d(1,5)} , + }

d(4,6) d(4,6), d(4,1) + d(1,6)} + }

d(4,7) d(4,7), d(4,1) + d(1,7)} , + }

d(4,8) d(4,8), d(4,1) + d(1,8)} + }

d(4,9) d(4,9), d(4,1) + d(1,9)} + }

d(4,10) d(4,10), d(4,1) + d(1,10)} + }

d(4,11) d(4,11), d(4,1) + d(1,11)} + }

d(4,12) d(4,12), d(4,1) + d(1,12)} + }

d(4,13) d(4,13), d(4,1) + d(1,13)} + }

d(4,14) d(4,14), d(4,1) + d(1,14)} + }

d(4,15) d(4,15), d(4,1) + d(1,15)} + }

d(4,16) d(4,16), d(4,1) + d(1,16)} + }

d(4,17) d(4,17), d(4,1) + d(1,17)} + }

82

d(5,1) d(5,1), d(5,1) + d(1,1)} + }

d(5,2) d(5,1) + d(1,2)} + }

d(5,3) d(5,3), d(5,1) + d(1,3) + }

d(5,4) d(5,4), d(5,1) + d(1,4)} 2,4. + } = 2,4

d(5,5) d(5,5), d(5,1) + d(1,5)} , + }

d(5,6) d(5,6), d(5,1) + d(1,6)} + }

d(5,7) d(5,7), d(5,1) + d(1,7)} , + }

d(5,8) d(5,8), d(5,1) + d(1,8)} + }

d(5,9) d(5,9), d(5,1) + d(1,9)} + }

d(5,10) d(5,10), d(5,1) + d(1,10)} 8,1, + }

d(5,11) d(5,11), d(5,1) + d(1,11)} + }

d(5,12) d(5,12), d(5,1) + d(1,12)} + }

d(5,13) d(5,13), d(5,1) + d(1,13)} + }

d(5,14) d(5,14), d(5,1) + d(1,14)} + }

d(5,15) d(5,15), d(5,1) + d(1,15)} + }

d(5,16) d(5,16), d(5,1) + d(1,16)} + }

d(5,17) d(5,17), d(5,1) + d(1,17)} + }

d(6,1) d(6,1), d(6,1) + d(1,1)} + }

d(6,2) d(6,1) + d(1,2)} + }

d(6,3) d(6,3), d(6,1) + d(1,3) + }

d(6,4) d(6,4), d(6,1) + d(1,4)} 2,2. + }

d(6,5) d(6,5), d(6,1) + d(1,5)} , + }

d(6,6) d(6,6), d(6,1) + d(1,6)} + }

83

d(6,7) d(6,7), d(6,1) + d(1,7)} , + }

d(6,8) d(6,8), d(6,1) + d(1,8)} 2,9, + }

d(6,9) d(6,9), d(6,1) + d(1,9)} + }

d(6,10) d(6,10), 6(4,1) + d(1,10)} + }

d(6,11) d(6,11), d(6,1) + d(1,11)} + }

d(6,12) d(6,12), d(6,1) + d(1,12)} + }

d(6,13) d(6,13), d(6,1) + d(1,13)} + }

d(6,14) d(6,14), d(6,1) + d(1,14)} + }

d(6,15) d(6,15), d(6,1) + d(1,15)} + }

d(6,16) d(6,16), d(6,1) + d(1,16)} + }

d(6,17) d(6,17), d(6,1) + d(1,17)} + }

d(7,1) d(7,1), d(7,1) + d(1,1)} + }

d(7,2) d(7,1) + d(1,2)} + }

d(7,3) d(7,3), d(7,1) + d(1,3) + }

d(7,4) d(7,4), d(7,1) + d(1,4)} . + }

d(7,5) d(7,5), d(7,1) + d(1,5)} , + }

d(7,6) d(7,6), d(7,1) + d(1,6)} + }

d(7,7) d(7,7), d(7,1) + d(1,7)} 0, + }

d(7,8) d(7,8), d(7,1) + d(1,8)} 3,6, + }

d(7,9) d(7,9), d(7,1) + d(1,9)} + }

d(7,10) d(7,10), d(7,1) + d(1,10)} + }

d(7,11) d(7,11), d(7,1) + d(1,11)} + }

d(7,12) d(7,12), d(7,1) + d(1,12)} + }

d(7,13) d(7,13), d(7,1) + d(1,13)} + }

84

d(7,14) d(7,14), d(7,1) + d(1,14)} + }

d(7,15) d(7,15), d(7,1) + d(1,15)} + }

d(7,16) d(7,16), d(7,1) + d(1,16)} + }

d(7,17) d(7,17), d(7,1) + d(1,17)} + }

d(8,1) d(8,1), d(8,1) + d(1,1)} + }

d(8,2) d(8,1) + d(1,2)} + }

d(8,3) d(8,3), d(8,1) + d(1,3) + }

d(8,4) d(8,4), d(8,1) + d(1,4)} . + }

d(8,5) d(8,5), d(8,1) + d(1,5)} , + }

d(8,6) d(8,6), d(8,1) + d(1,6)} + }

d(8,7) d(8,7), d(8,1) + d(1,7)} 3,6, + }

d(8,8) d(8,8), d(8,1) + d(1,8)} 0, + }

d(8,9) d(8,9), d(8,1) + d(1,9)} + }

d(8,10) d(8,10), d(8,1) + d(1,10)} + }

d(8,11) d(8,11), d(8,1) + d(1,11)} + }

d(8,12) d(8,12), d(8,1) + d(1,12)} + }

d(8,13) d(8,13), d(8,1) + d(1,13)} 2,7, + }

d(8,14) d(8,14), d(8,1) + d(1,14)} + }

d(8,15) d(8,15), d(8,1) + d(1,15)} + }

d(8,16) d(8,16), d(8,1) + d(1,16)} + }

d(8,17) d(8,17), d(8,1) + d(1,17)} + }

d(9,1) d(9,1), d(9,1) + d(1,1)} + }

d(9,2) d(9,1) + d(1,2)} + }

85

d(9,3) d(9,3), d(9,1) + d(1,3) + }

d(9,4) d(9,4), d(9,1) + d(1,4)} . + }

d(9,5) d(9,5), d(9,1) + d(1,5)} , + }

d(9,6) d(9,6), d(9,1) + d(1,6)} + }

d(9,7) d(9,7), d(9,1) + d(1,7)} , + }

d(9,8) d(9,8), d(9,1) + d(1,8)} 1,6, + }

d(9,9) d(9,9), d(9,1) + d(1,9)} + }

d(9,10) d(9,10), d(9,1) + d(1,10)} 1,9, + }

d(9,11) + } + }

d(9,12) + } + }

d(9,13) + } 2,9, + }

d(9,14) + } + }

d(9,15) + } + }

d(9,16) + } + }

d(9,17) + } + }

d(10,1) d(10,1), d(10,1) + d(1,1)} + }

d(10,2) d(10,1) + d(1,2)} + }

d(10,3) d(10,3), d(10,1) + d(1,3) + }

d(10,4) d(10,4), d(10,1) + d(1,4)} . + }

d(10,5) d(10,5), d(10,1) + d(1,5)} , + }

d(10,6) d(10,6), d(10,1) + d(1,6)} + }

d(10,7) d(10,7), d(10,1) + d(1,7)} , + }

d(10,8) d(10,8), d(10,1) + d(1,8)} + }

d(10,9) d(10,9), d(10,1) + d(1,9)} + }

86

d(10,10) d(10,10), d(10,1) + d(1,10)} 0, + }

d(10,11) d(10,11), d(10,1) + d(1,11)} + }

d(10,12) d(10,12), d(10,1) + d(1,12)} + }

d(10,13) d(10,13), d(10,1) + d(1,13)} 2,9, + }= 2,9

d(10,14) d(10,14), d(10,1) + d(1,14)} + }

d(10,15) d(10,15), d(10,1) + d(1,15)} + }

d(10,16) d(10,16), d(10,1) + d(1,16)} + }

d(10,17) d(10,17), d(10,1) + d(1,17)} + }

d(11,1) d(11,1), d(11,1) + d(1,1)} + }

d(11,2) d(11,1) + d(1,2)} + }

d(11,3) d(11,3), d(11,1) + d(1,3) + }

d(11,4) d(11,4), d(11,1) + d(1,4)} 0. + }

d(11,5) d(11,5), d(11,1) + d(1,5)} , + }

d(11,6) d(11,6), d(11,1) + d(1,6)} + }

d(11,7) d(11,7), d(11,1) + d(1,7)} , + }

d(11,8) d(11,8), d(11,1) + d(1,8)} + }

d(11,9) d(11,9), d(11,1) + d(1,9)} + }

d(11,10) d(11,10), d(11,1) + d(1,10)} 9,0, + }

d(11,11) d(11,11), d(11,1) + d(1,11)} + }

d(11,12) d(11,12), d(11,1) + d(1,12)} + }

d(11,13) d(11,13), d(11,1) + d(1,13)} + }

d(11,14) d(11,14), d(11,1) + d(1,14)} + }

d(11,15) d(11,15), d(11,1) + d(1,15)} + }

d(11,16) d(11,16), d(11,1) + d(1,16)} 19,7, + }

87

d(11,17) d(11,17), d(11,1) + d(1,17)} + }

d(12,1) d(12,1), d(12,1) + d(1,1)} + }

d(12,2) d(12,1) + d(1,2)} + }

d(12,3) d(12,3), d(12,1) + d(1,3) + }

d(12,4) d(12,4), d(12,1) + d(1,4)} . + }

d(12,5) d(12,5), d(12,1) + d(1,5)} , + }

d(12,6) d(12,6), d(12,1) + d(1,6)} + }

d(12,7) d(12,7), d(12,1) + d(1,7)} 1,9, + }

d(12,8) d(12,8), d(12,1) + d(1,8)} 3,0, + }

d(12,9) d(12,9), d(12,1) + d(1,9)} + }

d(12,10) d(12,10), d(12,1) + d(1,10)} + }

d(12,11) d(12,11), d(12,1) + d(1,11)} + }

d(12,12) d(12,12), d(12,1) + d(1,12)} + }

d(12,13) d(12,13), d(12,1) + d(1,13)} 2,6, + }

d(12,14) d(12,14), d(12,1) + d(1,14)} + }

d(12,15) d(12,15), d(12,1) + d(1,15)} + }

d(12,16) d(12,16), d(12,1) + d(1,16)} + }

d(12,17) d(12,17), d(12,1) + d(1,17)} + }

d(13,1) d(13,1), d(13,1) + d(1,1)} + }

d(13,2) d(13,1) + d(1,2)} + }

d(13,3) d(13,3), d(13,1) + d(1,3) + }

d(13,4) d(13,4), d(13,1) + d(1,4)} . + }

d(13,5) d(13,5), d(13,1) + d(1,5)} , + }

88

d(13,6) d(13,6), d(13,1) + d(1,6)} + }

d(13,7) d(13,7), d(13,1) + d(1,7)} , + }

d(13,8) d(13,8), d(13,1) + d(1,8)} 2,7, + }

d(13,9) d(13,9), d(13,1) + d(1,9)} + }

d(13,10) d(13,10), d(13,1) + d(1,10)} 2,9, + }

d(13,11) d(13,11), d(13,1) + d(1,11)} + }

d(13,12) d(13,12), d(13,1) + d(1,12)} + }

d(13,13) d(13,13), d(13,1) + d(1,13)} , + }

d(13,14) d(13,14), d(13,1) + d(1,14)} + }

d(13,15) d(13,15), d(13,1) + d(1,15)} + }

d(13,16) d(13,16), d(13,1) + d(1,16)} + }

d(13,17) d(13,17), d(13,1) + d(1,17)} + }

d(14,1) d(14,1), d(14,1) + d(1,1)} + }

d(14,2) d(14,1) + d(1,2)} + }

d(14,3) d(14,3), d(14,1) + d(1,3) + }

d(14,4) d(14,4), d(14,1) + d(1,4)} . + }

d(14,5) d(14,5), d(14,1) + d(1,5)} , + }

d(14,6) d(14,6), d(14,1) + d(1,6)} + }

d(14,7) d(14,7), d(14,1) + d(1,7)} , + }

d(14,8) d(14,8), d(14,1) + d(1,8)} + }

d(14,9) d(14,9), d(14,1) + d(1,9)} + }

d(14,10) d(14,10), d(14,1) + d(1,10)} + }

d(14,11) d(14,11), d(14,1) + d(1,11)} + }

d(14,12) d(14,12), d(14,1) + d(1,12)} + }

89

d(14,13) d(14,13), d(14,1) + d(1,13)} 4,1, + }

d(14,14) d(14,14), d(14,1) + d(1,14)} + }

d(14,15) d(14,15), d(14,1) + d(1,15)} 3,5, + }

d(14,16) d(14,16), d(14,1) + d(1,16)} + }

d(14,17) d(14,17), d(14,1) + d(1,17)} + }

d(15,1) d(15,1), d(15,1) + d(1,1)} + }

d(15,2) d(15,1) + d(1,2)} + }

d(15,3) d(15,3), d(15,1) + d(1,3) + }

d(15,4) d(15,4), d(15,1) + d(1,4)} . + }

d(15,5) d(15,5), d(15,1) + d(1,5)} , + }

d(15,6) d(15,6), d(15,1) + d(1,6)} + }

d(15,7) d(15,7), d(15,1) + d(1,7)} , + }

d(15,8) d(15,8), d(15,1) + d(1,8)} + }

d(15,9) d(15,9), d(15,1) + d(1,9)} + }

d(15,10) d(15,10), d(15,1) + d(1,10)} + }

d(15,11) d(15,11), d(15,1) + d(1,11)} + }

d(15,12) d(15,12), d(15,1) + d(1,12)} + }

d(15,13) d(15,13), d(15,1) + d(1,13)} + }

d(15,14) d(15,14), d(15,1) + d(1,14)} + }

d(15,15) d(15,15), d(15,1) + d(1,15)} 0, + }

d(15,16) d(15,16), d(15,1) + d(1,16)} 2,9, + }

d(15,17) d(15,17), d(15,1) + d(1,17)} + }

d(16,1) d(16,1), d(16,1) + d(1,1)} + }

90

d(16,2) d(16,1) + d(1,2)} + }

d(16,3) d(16,3), d(16,1) + d(1,3) + }

d(16,4) d(16,4), d(16,1) + d(1,4)} . + }

d(16,5) d(16,5), d(16,1) + d(1,5)} , + }

d(16,6) d(16,6), d(16,1) + d(1,6)} + }

d(16,7) d(16,7), d(16,1) + d(1,7)} , + }

d(16,8) d(16,8), d(16,1) + d(1,8)} + }

d(16,9) d(16,9), d(16,1) + d(1,9)} + }

d(16,10) d(16,10), d(16,1) + d(1,10)} + }

d(16,11) d(16,11), d(16,1) + d(1,11)} + }

d(16,12) d(16,12), d(16,1) + d(1,12)} + }

d(16,13) d(16,13), d(16,1) + d(1,13)} + }

d(16,14) d(16,14), d(16,1) + d(1,14)} + }

d(16,15) d(16,15), d(16,1) + d(1,15)} 2,9, + }

d(16,16) d(16,16), d(16,1) + d(1,16)} 0, + }

d(16,17) d(16,17), d(16,1) + d(1,17)} + }

d(17,1) d(17,1), d(17,1) + d(1,1)} + }

d(17,2) d(17,1) + d(1,2)} + }

d(17,3) d(17,3), d(17,1) + d(1,3) + }

d(17,4) d(17,4), d(17,1) + d(1,4)} . + }

d(17,5) d(17,5), d(17,1) + d(1,5)} , + }

d(17,6) d(17,6), d(17,1) + d(1,6)} + }

d(17,7) d(17,7), d(17,1) + d(1,7)} , + }

d(17,8) d(17,8), d(17,1) + d(1,8)} + }

91

d(17,9) d(17,9), d(17,1) + d(1,9)} + }

d(17,10) d(17,10), d(17,1) + d(1,10)} + }

d(17,11) d(17,11), d(17,1) + d(1,11)} + }

d(17,12) d(17,12), d(17,1) + d(1,12)} + }

d(17,13) d(17,13), d(17,1) + d(1,13)} + }

d(17,14) d(17,14), d(17,1) + d(1,14)} + }

d(17,15) d(17,15), d(17,1) + d(1,15)} 8,5, + }

d(17,16) d(17,16), d(17,1) + d(1,16)} + }

d(17,17) d(17,17), d(17,1) + d(1,17)} + }

K = 2

d(1,1) d(1,1), d(1,2)+d(2,1) + }

d(1,2) d(1,2), d(1,2)+d(2,2)} + }

d(1,3) d(1,3), d(1,2)+d(2,3)} + }

d(1,4) d(1,4), d(1,2)+d(2,4)} + }

d(1,5) , d(1,2)+d(2,5)} + }

d(1,6) d(1,2)+d(2,6)} + }

d(1,7) d(1,2)+d(2,7)} + }

d(1,8) d(1,2)+d(2,8)} + }

d(1,9) d(1,2)+d(2,9)} + }

d(1,10) d(1,2)+d(2,10)} + }

d(1,11) d(1,2)+d(2,11)} + }

d(1,12) d(1,2)+d(2,12)} + }

92

d(1,13) d(1,2)+d(2,13)} + }

d(1,14) d(1,14) d(1,2)+d(2,14)} + }

d(1,15) d(1,15), d(1,2)+d(2,15)} + }

d(1,16) d(1,16), d(1,2)+d(2,16)} + }

d(1,17) d(1,2)+d(2,17) } + }

d(2,1) d(2,1), d(2,2)+d(2,1)} + }

d(2,2) d(2,2)+d(2,2)} 0 + 0} = 0

d(2,3) d(2,3), d(2,2)+d(2,3) + }

d(2,4) d(2,4), d(2,2)+d(2,4)} 4,1, 0 + 4,1} = 4,1

d(2,5) d(2,5), d(2,2)+d(2,5)} 5,7, 0 + 5,7} = 5,7

d(2,6) d(2,6), d(2,2)+d(2,6)} + }

d(2,7) d(2,7), d(2,2)+d(2,7)} + }

d(2,8) d(2,8), d(2,2)+d(2,8)} + }

d(2,9) d(2,9), d(2,2)+d(2,9)} + }

d(2,10) d(2,10), d(2,2)+d(2,10)} + }

d(2,11) d(2,11), d(2,2)+d(2,11)} + }

d(2,12) d(2,12), d(2,2)+d(2,12)} + }

d(2,13) d(2,13), d(2,2)+d(2,13)} + }

d(2,14) d(2,14), d(2,2)+d(2,14)} + }

d(2,15) d(2,15), d(2,2)+d(2,15)} + }

d(2,16) d(2,16), d(2,2)+d(2,16)} + }

d(2,17) d(2,17), d(2,2)+d(2,17)} + }

d(3,1) d(3,1), d(3,2)+d(2,1)} + }

93

d(3,2) d(3,2)+d(2,2)} + } =

d(3,3) d(3,3), d(3,2)+d(2,3) + }

d(3,4) d(3,4), d(3,2)+d(2,4)} . + }

d(3,5) d(3,5), d(3,2)+d(2,5)} , + }

d(3,6) d(3,6), d(3,2)+d(2,6)} + }

d(3,7) d(3,7), d(3,2)+d(2,7)} 4,9, + }

d(3,8) d(3,8), d(3,2)+d(2,8)} + }

d(3,9) d(3,9), d(3,2)+d(2,9)} + }

d(3,10) d(3,10), d(3,2)+d(2,10)} + }

d(3,11) d(3,11), d(3,2)+d(2,11)} + }

d(3,12) d(3,12), d(3,2)+d(2,12)} + }

d(3,13) d(3,13), d(3,2)+d(2,13)} + }

d(3,14) d(3,14), d(3,2)+d(2,14)} + }

d(3,15) d(3,15), d(3,2)+d(2,15)} + }

d(3,16) d(3,16), d(3,2)+d(2,16)} + }

d(3,17) d(3,17), d(3,2)+d(2,17)} + }

d(4,1) d(4,1), d(4,2)+d(2,1)} , + }

d(4,2) d(4,2)+d(2,2)} + 0} = 4,1

d(4,3) d(4,3), d(4,2)+d(2,3) + }

d(4,4) d(4,4), d(4,2)+d(2,4)} 0. + 4,1} = 0

d(4,5) d(4,5), d(4,2)+d(2,5)} , + 5,7} = 2,4

d(4,6) d(4,6), d(4,2)+d(2,6)} + }

d(4,7) d(4,7), d(4,2)+d(2,7)} , + }

d(4,8) d(4,8), d(4,2)+d(2,8)} + }

94

d(4,9) d(4,9), d(4,2)+d(2,9)} + }

d(4,10) d(4,10), d(4,2)+d(2,10)} + }

d(4,11) d(4,11), d(4,2)+d(2,11)} + }

d(4,12) d(4,12), d(4,2)+d(2,12)} + }

d(4,13) d(4,13), d(4,2)+d(2,13)} + }

d(4,14) d(4,14), d(4,2)+d(2,14)} + }

d(4,15) d(4,15), d(4,2)+d(2,15)} + }

d(4,16) d(4,16), d(4,2)+d(2,16)} + }

d(4,17) d(4,17), d(4,2)+d(2,17)} + }

d(5,1) d(5,1), d(5,2)+d(2,1)} + }

d(5,2) d(5,2)+d(2,2)} + }

d(5,3) d(5,3), d(5,2)+d(2,3) + }

d(5,4) d(5,4), d(5,2)+d(2,4)} 2,4. 5,7 + 4,1} = 2,4

d(5,5) d(5,5), d(5,2)+d(2,5)} , 5,7 + 5,7} = 0

d(5,6) d(5,6), d(5,2)+d(2,6)} + }

d(5,7) d(5,7), d(5,2)+d(2,7)} , + }

d(5,8) d(5,8), d(5,2)+d(2,8)} + }

d(5,9) d(5,9), d(5,2)+d(2,9)} + }

d(5,10) d(5,10), d(5,2)+d(2,10)} 8,1, + }

d(5,11) d(5,11), d(5,2)+d(2,11)} + }

d(5,12) d(5,12), d(5,2)+d(2,12)} + }

d(5,13) d(5,13), d(5,2)+d(2,13)} + }

d(5,14) d(5,14), d(5,2)+d(2,14)} + }

d(5,15) d(5,15), d(5,2)+d(2,15)} + }

95

d(5,16) d(5,16), d(5,2)+d(2,16)} + }

d(5,17) d(5,17), d(5,2)+d(2,17)} + }

d(6,1) d(6,1), d(6,2)+d(2,1)} + }

d(6,2) d(6,2)+d(2,2)} + }

d(6,3) d(6,3), d(6,2)+d(2,3) + }

d(6,4) d(6,4), d(6,2)+d(2,4)} 2,2. + }

d(6,5) d(6,5), d(6,2)+d(2,5)} , + }

d(6,6) d(6,6), d(6,2)+d(2,6)} + }

d(6,7) d(6,7), d(6,2)+d(2,7)} , + }

d(6,8) d(6,8), d(6,2)+d(2,8)} 2,9, + }

d(6,9) d(6,9), d(6,2)+d(2,9)} + } ,6

d(6,10) d(6,10), 6(4,2)+d(2,10)} + }

d(6,11) d(6,11), d(6,2)+d(2,11)} + }

d(6,12) d(6,12), d(6,2)+d(2,12)} + }

d(6,13) d(6,13), d(6,2)+d(2,13)} + }

d(6,14) d(6,14), d(6,2)+d(2,14)} + }

d(6,15) d(6,15), d(6,2)+d(2,15)} + }

d(6,16) d(6,16), d(6,2)+d(2,16)} + }

d(6,17) d(6,17), d(6,2)+d(2,17)} + }

d(7,1) d(7,1), d(7,2)+d(2,1)} + }

d(7,2) d(7,2)+d(2,2)} + }

d(7,3) d(7,3), d(7,2)+d(2,3) + }

d(7,4) d(7,4), d(7,2)+d(2,4)} . + }

96

d(7,5) d(7,5), d(7,2)+d(2,5)} , + }

d(7,6) d(7,6), d(7,2)+d(2,6)} + }

d(7,7) d(7,7), d(7,2)+d(2,7)} 0, + }

d(7,8) d(7,8), d(7,2)+d(2,8)} 3,6, + }

d(7,9) d(7,9), d(7,2)+d(2,9)} + }

d(7,10) d(7,10), d(7,2)+d(2,10)} + }

d(7,11) d(7,11), d(7,2)+d(2,11)} + }

d(7,12) d(7,12), d(7,2)+d(2,12)} + }

d(7,13) d(7,13), d(7,2)+d(2,13)} + }

d(7,14) d(7,14), d(7,2)+d(2,14)} + }

d(7,15) d(7,15), d(7,2)+d(2,15)} + }

d(7,16) d(7,16), d(7,2)+d(2,16)} + }

d(7,17) d(7,17), d(7,2)+d(2,17)} + }

d(8,1) d(8,1), d(8,2)+d(2,1)} + }

d(8,2) d(8,2)+d(2,2)} + }

d(8,3) d(8,3), d(8,2)+d(2,3) + }

d(8,4) d(8,4), d(8,2)+d(2,4)} . + }

d(8,5) d(8,5), d(8,2)+d(2,5)} , + }

d(8,6) d(8,6), d(8,2)+d(2,6)} + }

d(8,7) d(8,7), d(8,2)+d(2,7)} 3,6, + }

d(8,8) d(8,8), d(8,2)+d(2,8)} 0, + }

d(8,9) d(8,9), d(8,2)+d(2,9)} + }

d(8,10) d(8,10), d(8,2)+d(2,10)} + }

d(8,11) d(8,11), d(8,2)+d(2,11)} + }

97

d(8,12) d(8,12), d(8,2)+d(2,12)} + }

d(8,13) d(8,13), d(8,2)+d(2,13)} 2,7, + }

d(8,14) d(8,14), d(8,2)+d(2,14)} + }

d(8,15) d(8,15), d(8,2)+d(2,15)} + }

d(8,16) d(8,16), d(8,2)+d(2,16)} + }

d(8,17) d(8,17), d(8,2)+d(2,17)} + }

d(9,1) d(9,1), d(9,2)+d(2,1)} + }

d(9,2) d(9,2)+d(2,2)} + }

d(9,3) d(9,3), d(9,2)+d(2,3) + }

d(9,4) d(9,4), d(9,2)+d(2,4)} . + }

d(9,5) d(9,5), d(9,2)+d(2,5)} , + }

d(9,6) d(9,6), d(9,2)+d(2,6)} + }

d(9,7) d(9,7), d(9,2)+d(2,7)} , + }

d(9,8) d(9,8), d(9,2)+d(2,8)} 1,6, + }

d(9,9) d(9,9), d(9,2)+d(2,9)} + }

d(9,10) d(9,10), d(9,2)+d(2,10)} 1,9, + }

d(9,11) + } + }

d(9,12) + } + }

d(9,13) + } 2,9, + }

d(9,14) + } + }

d(9,15) + } + }

d(9,16) + } + }

d(9,17) + } + }

98

d(10,1) d(10,1), d(10,2)+d(2,1)} + }

d(10,2) d(10,2)+d(2,2)} + }

d(10,3) d(10,3), d(10,2)+d(2,3) + }

d(10,4) d(10,4), d(10,2)+d(2,4)} . + }

d(10,5) d(10,5), d(10,2)+d(2,5)} , + }

d(10,6) d(10,6), d(10,2)+d(2,6)} + }

d(10,7) d(10,7), d(10,2)+d(2,7)} , + }

d(10,8) d(10,8), d(10,2)+d(2,8)} + }

d(10,9) d(10,9), d(10,2)+d(2,9)} + }

d(10,10) d(10,10), d(10,2)+d(2,10)} 0, + }

d(10,11) d(10,11), d(10,2)+d(2,11)} + }

d(10,12) d(10,12), d(10,2)+d(2,12)} + }

d(10,13) d(10,13), d(10,2)+d(2,13)} 2,9, + }

d(10,14) d(10,14), d(10,2)+d(2,14)} + }

d(10,15) d(10,15), d(10,2)+d(2,15)} + }

d(10,16) d(10,16), d(10,2)+d(2,16)} + }

d(10,17) d(10,17), d(10,2)+d(2,17)} + }

d(11,1) d(11,1), d(11,2)+d(2,1)} + }

d(11,2) d(11,2)+d(2,2)} + }

d(11,3) d(11,3), d(11,2)+d(2,3) + }

d(11,4) d(11,4), d(11,2)+d(2,4)} 0. + }

d(11,5) d(11,5), d(11,2)+d(2,5)} , + }

d(11,6) d(11,6), d(11,2)+d(2,6)} + }

d(11,7) d(11,7), d(11,2)+d(2,7)} , + }

99

d(11,8) d(11,8), d(11,2)+d(2,8)} + }

d(11,9) d(11,9), d(11,2)+d(2,9)} + }

d(11,10) d(11,10), d(11,2)+d(2,10)} 9,0, + }

d(11,11) d(11,11), d(11,2)+d(2,11)} + }

d(11,12) d(11,12), d(11,2)+d(2,12)} + }

d(11,13) d(11,13), d(11,2)+d(2,13)} + }

d(11,14) d(11,14), d(11,2)+d(2,14)} + }

d(11,15) d(11,15), d(11,2)+d(2,15)} + }

d(11,16) d(11,16), d(11,2)+d(2,16)} 19,7, + }

d(11,17) d(11,17), d(11,2)+d(2,17)} + }

d(12,1) d(12,1), d(12,2)+d(2,1)} + }

d(12,2) d(12,2)+d(2,2)} + }

d(12,3) d(12,3), d(12,2)+d(2,3) + }

d(12,4) d(12,4), d(12,2)+d(2,4)} . + }

d(12,5) d(12,5), d(12,2)+d(2,5)} , + }

d(12,6) d(12,6), d(12,2)+d(2,6)} + }

d(12,7) d(12,7), d(12,2)+d(2,7)} 1,9, + }

d(12,8) d(12,8), d(12,2)+d(2,8)} 3,0, + }

d(12,9) d(12,9), d(12,2)+d(2,9)} + }

d(12,10) d(12,10), d(12,2)+d(2,10)} + }

d(12,11) d(12,11), d(12,2)+d(2,11)} + }

d(12,12) d(12,12), d(12,2)+d(2,12)} + }

d(12,13) d(12,13), d(12,2)+d(2,13)} 2,6, + }

d(12,14) d(12,14), d(12,2)+d(2,14)} + }

100

d(12,15) d(12,15), d(12,2)+d(2,15)} + }

d(12,16) d(12,16), d(12,2)+d(2,16)} + }

d(12,17) d(12,17), d(12,2)+d(2,17)} + }

d(13,1) d(13,1), d(13,2)+d(2,1)} + }

d(13,2) d(13,2)+d(2,2)} + }

d(13,3) d(13,3), d(13,2)+d(2,3) + }

d(13,4) d(13,4), d(13,2)+d(2,4)} . + }

d(13,5) d(13,5), d(13,2)+d(2,5)} , + }

d(13,6) d(13,6), d(13,2)+d(2,6)} + }

d(13,7) d(13,7), d(13,2)+d(2,7)} , + }

d(13,8) d(13,8), d(13,2)+d(2,8)} 2,7, + }

d(13,9) d(13,9), d(13,2)+d(2,9)} + }

d(13,10) d(13,10), d(13,2)+d(2,10)} 2,9, + }

d(13,11) d(13,11), d(13,2)+d(2,11)} + }

d(13,12) d(13,12), d(13,2)+d(2,12)} + }

d(13,13) d(13,13), d(13,2)+d(2,13)} , + }

d(13,14) d(13,14), d(13,2)+d(2,14)} + }

d(13,15) d(13,15), d(13,2)+d(2,15)} + }

d(13,16) d(13,16), d(13,2)+d(2,16)} + }

d(13,17) d(13,17), d(13,2)+d(2,17)} + }

d(14,1) d(14,1), d(14,2)+d(2,1)} + }

d(14,2) d(14,2)+d(2,2)} + }

d(14,3) d(14,3), d(14,2)+d(2,3) + }

101

d(14,4) d(14,4), d(14,2)+d(2,4)} . + }

d(14,5) d(14,5), d(14,2)+d(2,5)} , + }

d(14,6) d(14,6), d(14,2)+d(2,6)} + }

d(14,7) d(14,7), d(14,2)+d(2,7)} , + }

d(14,8) d(14,8), d(14,2)+d(2,8)} + }

d(14,9) d(14,9), d(14,2)+d(2,9)} + }

d(14,10) d(14,10), d(14,2)+d(2,10)} + }

d(14,11) d(14,11), d(14,2)+d(2,11)} + }

d(14,12) d(14,12), d(14,2)+d(2,12)} + }

d(14,13) d(14,13), d(14,2)+d(2,13)} 4,1, + }

d(14,14) d(14,14), d(14,2)+d(2,14)} + }

d(14,15) d(14,15), d(14,2)+d(2,15)} 3,5, + }

d(14,16) d(14,16), d(14,2)+d(2,16)} , + }

d(14,17) d(14,17), d(14,2)+d(2,17)} + }

d(15,1) d(15,1), d(15,2)+d(2,1)} + }

d(15,2) d(15,2)+d(2,2)} + }

d(15,3) d(15,3), d(15,2)+d(2,3) + }

d(15,4) d(15,4), d(15,2)+d(2,4)} . + }

d(15,5) d(15,5), d(15,2)+d(2,5)} , + }

d(15,6) d(15,6), d(15,2)+d(2,6)} + }

d(15,7) d(15,7), d(15,2)+d(2,7)} , + }

d(15,8) d(15,8), d(15,2)+d(2,8)} + }

d(15,9) d(15,9), d(15,2)+d(2,9)} + }

d(15,10) d(15,10), d(15,2)+d(2,10)} + }

102

d(15,11) d(15,11), d(15,2)+d(2,11)} + }

d(15,12) d(15,12), d(15,2)+d(2,12)} + }

d(15,13) d(15,13), d(15,2)+d(2,13)} + }

d(15,14) d(15,14), d(15,2)+d(2,14)} + }

d(15,15) d(15,15), d(15,2)+d(2,15)} 0, + }

d(15,16) d(15,16), d(15,2)+d(2,16)} 2,9, + }

d(15,17) d(15,17), d(15,2)+d(2,17)} + }

d(16,1) d(16,1), d(16,2)+d(2,1)} + }

d(16,2) d(16,2)+d(2,2)} + }

d(16,3) d(16,3), d(16,2)+d(2,3) + }

d(16,4) d(16,4), d(16,2)+d(2,4)} . + }

d(16,5) d(16,5), d(16,2)+d(2,5)} , + }

d(16,6) d(16,6), d(16,2)+d(2,6)} + }

d(16,7) d(16,7), d(16,2)+d(2,7)} , + }

d(16,8) d(16,8), d(16,2)+d(2,8)} + }

d(16,9) d(16,9), d(16,2)+d(2,9)} + }

d(16,10) d(16,10), d(16,2)+d(2,10)} + }

d(16,11) d(16,11), d(16,2)+d(2,11)} + }

d(16,12) d(16,12), d(16,2)+d(2,12)} + }

d(16,13) d(16,13), d(16,2)+d(2,13)} + }

d(16,14) d(16,14), d(16,2)+d(2,14)} + }

d(16,15) d(16,15), d(16,2)+d(2,15)} 2,9, + }

d(16,16) d(16,16), d(16,2)+d(2,16)} 0, + }

d(16,17) d(16,17), d(16,2)+d(2,17)} + }

103

d(17,1) d(17,1), d(17,2)+d(2,1)} + }

d(17,2) d(17,2)+d(2,2)} + }

d(17,3) d(17,3), d(17,2)+d(2,3) + }

d(17,4) d(17,4), d(17,2)+d(2,4)} . + }

d(17,5) d(17,5), d(17,2)+d(2,5)} , + }

d(17,6) d(17,6), d(17,2)+d(2,6)} + }

d(17,7) d(17,7), d(17,2)+d(2,7)} , + }

d(17,8) d(17,8), d(17,2)+d(2,8)} + }

d(17,9) d(17,9), d(17,2)+d(2,9)} + }

d(17,10) d(17,10), d(17,2)+d(2,10)} + }

d(17,11) d(17,11), d(17,2)+d(2,11)} + }

d(17,12) d(17,12), d(17,2)+d(2,12)} + }

d(17,13) d(17,13), d(17,2)+d(2,13)} + }

d(17,14) d(17,14), d(17,2)+d(2,14)} + }

d(17,15) d(17,15), d(17,2)+d(2,15)} 8,5, + }

d(17,16) d(17,16), d(17,2)+d(2,16)} + }

d(17,17) d(17,17), d(17,2)+d(2,17)} + }

K = 3

d(1,1) d(1,1), d(1,3) + d(3,1) 0, 0,9 + 0} = 0

d(1,2) d(1,2), d(1,3) + d(3,2)} + }

d(1,3) d(1,3), d(1,3) + d(3,3)} 0,9, 0,9 + 0,9} = 0,9

d(1,4) d(1,4), d(1,3) + d(3,4)} + }

d(1,5) , d(1,3) + d(3,5)} + }

104

d(1,6) d(1,3) + d(3,6)} + }

d(1,7) d(1,3) + d(3,7)} + }

d(1,8) d(1,3) + d(3,8)} + }

d(1,9) d(1,3) + d(3,9)} + }

d(1,10) d(1,3) + d(3,10)} + }

d(1,11) d(1,3) + d(3,11)} + }

d(1,12) d(1,3) + d(3,12)} + }

d(1,13) d(1,3) + d(3,13)} + }

d(1,14) d(1,14) d(1,3) + d(3,14)} + }

d(1,15) d(1,15), d(1,3) + d(3,15)} + }

d(1,16) d(1,16), d(1,3) + d(3,16)} + }

d(1,17) d(1,3) + d(3,17) } + }

d(2,1) d(2,1), d(2,3) + d(3,1)} + }

d(2,2) d(2,3) + d(3,2)} + }

d(2,3) d(2,3), d(2,3) + d(3,3) + }

d(2,4) d(2,4), d(2,3) + d(3,4)} 4,1, + }

d(2,5) d(2,5), d(2,3) + d(3,5)} 5,7, + }

d(2,6) d(2,6), d(2,3) + d(3,6)} + }

d(2,7) d(2,7), d(2,3) + d(3,7)} + }

d(2,8) d(2,8), d(2,3) + d(3,8)} + }

d(2,9) d(2,9), d(2,3) + d(3,9)} + }

d(2,10) d(2,10), d(2,3) + d(3,10)} + }

d(2,11) d(2,11), d(2,3) + d(3,11)} + }

d(2,12) d(2,12), d(2,3) + d(3,12)} + }

105

d(2,13) d(2,13), d(2,3) + d(3,13)} + }

d(2,14) d(2,14), d(2,3) + d(3,14)} + }

d(2,15) d(2,15), d(2,3) + d(3,15)} + }

d(2,16) d(2,16), d(2,3) + d(3,16)} + }

d(2,17) d(2,17), d(2,3) + d(3,17)} + }

d(3,1) d(3,1), d(3,3) + d(3,1)} 0,9, 0 + 0} = 0,9

d(3,2) d(3,3) + d(3,2)} 0 + } =

d(3,3) d(3,3), d(3,3) + d(3,3) 0 + 0,9} = 0

d(3,4) d(3,4), d(3,3) + d(3,4)} . 0 + } =

d(3,5) d(3,5), d(3,3) + d(3,5)} , + }

d(3,6) d(3,6), d(3,3) + d(3,6)} + }

d(3,7) d(3,7), d(3,3) + d(3,7)} 4,9, + }

d(3,8) d(3,8), d(3,3) + d(3,8)} + }

d(3,9) d(3,9), d(3,3) + d(3,9)} + }

d(3,10) d(3,10), d(3,3) + d(3,10)} + }

d(3,11) d(3,11), d(3,3) + d(3,11)} + }

d(3,12) d(3,12), d(3,3) + d(3,12)} + }

d(3,13) d(3,13), d(3,3) + d(3,13)} + }

d(3,14) d(3,14), d(3,3) + d(3,14)} + }

d(3,15) d(3,15), d(3,3) + d(3,15)} + }

d(3,16) d(3,16), d(3,3) + d(3,16)} + }

d(3,17) d(3,17), d(3,3) + d(3,17)} + }

d(4,1) d(4,1), d(4,3) + d(3,1)} + }

106

d(4,2) d(4,3) + d(3,2)} + }

d(4,3) d(4,3), d(4,3) + d(3,3) + 0,9} =

d(4,4) d(4,4), d(4,3) + d(3,4)} 0. + }

d(4,5) d(4,5), d(4,3) + d(3,5)} , + }

d(4,6) d(4,6), d(4,3) + d(3,6)} + }

d(4,7) d(4,7), d(4,3) + d(3,7)} , + }

d(4,8) d(4,8), d(4,3) + d(3,8)} + }

d(4,9) d(4,9), d(4,3) + d(3,9)} + }

d(4,10) d(4,10), d(4,3) + d(3,10)} + }

d(4,11) d(4,11), d(4,3) + d(3,11)} + }

d(4,12) d(4,12), d(4,3) + d(3,12)} + }

d(4,13) d(4,13), d(4,3) + d(3,13)} + }

d(4,14) d(4,14), d(4,3) + d(3,14)} + }

d(4,15) d(4,15), d(4,3) + d(3,15)} + }

d(4,16) d(4,16), d(4,3) + d(3,16)} + }

d(4,17) d(4,17), d(4,3) + d(3,17)} + }

d(5,1) d(5,1), d(5,3) + d(3,1)} + }

d(5,2) d(5,3) + d(3,2)} + }

d(5,3) d(5,3), d(5,3) + d(3,3) + }

d(5,4) d(5,4), d(5,3) + d(3,4)} 2,4. + } = 2,4

d(5,5) d(5,5), d(5,3) + d(3,5)} , + }

d(5,6) d(5,6), d(5,3) + d(3,6)} + }

d(5,7) d(5,7), d(5,3) + d(3,7)} , + }

d(5,8) d(5,8), d(5,3) + d(3,8)} + }

107

d(5,9) d(5,9), d(5,3) + d(3,9)} + }

d(5,10) d(5,10), d(5,3) + d(3,10)} 8,1, + }

d(5,11) d(5,11), d(5,3) + d(3,11)} + }

d(5,12) d(5,12), d(5,3) + d(3,12)} + }

d(5,13) d(5,13), d(5,3) + d(3,13)} + }

d(5,14) d(5,14), d(5,3) + d(3,14)} + }

d(5,15) d(5,15), d(5,3) + d(3,15)} + }

d(5,16) d(5,16), d(5,3) + d(3,16)} + }

d(5,17) d(5,17), d(5,3) + d(3,17)} + }

d(6,1) d(6,1), d(6,3) + d(3,1)} + }

d(6,2) d(6,3) + d(3,2)} 8,7 + }

d(6,3) d(6,3), d(6,3) + d(3,3) 8,7 + 0,9} = 8,7

d(6,4) d(6,4), d(6,3) + d(3,4)} 2,2. 8,7 + 9,1} = 2,2

d(6,5) d(6,5), d(6,3) + d(3,5)} , + }

d(6,6) d(6,6), d(6,3) + d(3,6)} + }

d(6,7) d(6,7), d(6,3) + d(3,7)} , + }

d(6,8) d(6,8), d(6,3) + d(3,8)} 2,9, + }

d(6,9) d(6,9), d(6,3) + d(3,9)} + }

d(6,10) d(6,10), 6(4,3) + d(3,10)} + }

d(6,11) d(6,11), d(6,3) + d(3,11)} + }

d(6,12) d(6,12), d(6,3) + d(3,12)} + }

d(6,13) d(6,13), d(6,3) + d(3,13)} + }

d(6,14) d(6,14), d(6,3) + d(3,14)} + }

d(6,15) d(6,15), d(6,3) + d(3,15)} + }

108

d(6,16) d(6,16), d(6,3) + d(3,16)} + }

d(6,17) d(6,17), d(6,3) + d(3,17)} + }

d(7,1) d(7,1), d(7,3) + d(3,1)} + }

d(7,2) d(7,3) + d(3,2)} 4,9 + }

d(7,3) d(7,3), d(7,3) + d(3,3) 4,9 + 0,9} = 4,9

d(7,4) d(7,4), d(7,3) + d(3,4)} . 4,9 + }

d(7,5) d(7,5), d(7,3) + d(3,5)} , + }

d(7,6) d(7,6), d(7,3) + d(3,6)} + }

d(7,7) d(7,7), d(7,3) + d(3,7)} 0, + }

d(7,8) d(7,8), d(7,3) + d(3,8)} 3,6, + }

d(7,9) d(7,9), d(7,3) + d(3,9)} + }

d(7,10) d(7,10), d(7,3) + d(3,10)} + }

d(7,11) d(7,11), d(7,3) + d(3,11)} + }

d(7,12) d(7,12), d(7,3) + d(3,12)} + }

d(7,13) d(7,13), d(7,3) + d(3,13)} + }

d(7,14) d(7,14), d(7,3) + d(3,14)} + }

d(7,15) d(7,15), d(7,3) + d(3,15)} + }

d(7,16) d(7,16), d(7,3) + d(3,16)} + }

d(7,17) d(7,17), d(7,3) + d(3,17)} 4, + }

d(8,1) d(8,1), d(8,3) + d(3,1)} + }

d(8,2) d(8,3) + d(3,2)} + }

d(8,3) d(8,3), d(8,3) + d(3,3) + }

d(8,4) d(8,4), d(8,3) + d(3,4)} . + }

109

d(8,5) d(8,5), d(8,3) + d(3,5)} , + }

d(8,6) d(8,6), d(8,3) + d(3,6)} + }

d(8,7) d(8,7), d(8,3) + d(3,7)} 3,6, + }

d(8,8) d(8,8), d(8,3) + d(3,8)} 0, + }

d(8,9) d(8,9), d(8,3) + d(3,9)} + }

d(8,10) d(8,10), d(8,3) + d(3,10)} + }

d(8,11) d(8,11), d(8,3) + d(3,11)} + }

d(8,12) d(8,12), d(8,3) + d(3,12)} + }

d(8,13) d(8,13), d(8,3) + d(3,13)} 2,7, + }

d(8,14) d(8,14), d(8,3) + d(3,14)} + }

d(8,15) d(8,15), d(8,3) + d(3,15)} + }

d(8,16) d(8,16), d(8,3) + d(3,16)} + }

d(8,17) d(8,17), d(8,3) + d(3,17)} + }

d(9,1) d(9,1), d(9,3) + d(3,1)} + }

d(9,2) d(9,3) + d(3,2)} + }

d(9,3) d(9,3), d(9,3) + d(3,3) + }

d(9,4) d(9,4), d(9,3) + d(3,4)} . + }

d(9,5) d(9,5), d(9,3) + d(3,5)} , + }

d(9,6) d(9,6), d(9,3) + d(3,6)} + }

d(9,7) d(9,7), d(9,3) + d(3,7)} , + }

d(9,8) d(9,8), d(9,3) + d(3,8)} 1,6, + }

d(9,9) d(9,9), d(9,3) + d(3,9)} + }

d(9,10) d(9,10), d(9,3) + d(3,10)} 1,9, + }

d(9,11) + } + }

110

d(9,12) + } + }

d(9,13) + } 2,9, + }

d(9,14) + } + }

d(9,15) + } + }

d(9,16) + } + }

d(9,17) + } + }

d(10,1) d(10,1), d(10,3) + d(3,1)} + }

d(10,2) d(10,3) + d(3,2)} + }

d(10,3) d(10,3), d(10,3) + d(3,3) + }

d(10,4) d(10,4), d(10,3) + d(3,4)} . + }

d(10,5) d(10,5), d(10,3) + d(3,5)} , + }

d(10,6) d(10,6), d(10,3) + d(3,6)} + }

d(10,7) d(10,7), d(10,3) + d(3,7)} , + }

d(10,8) d(10,8), d(10,3) + d(3,8)} + }

d(10,9) d(10,9), d(10,3) + d(3,9)} + }

d(10,10) d(10,10), d(10,3) + d(3,10)} 0, + }

d(10,11) d(10,11), d(10,3) + d(3,11)} + }

d(10,12) d(10,12), d(10,3) + d(3,12)} + }

d(10,13) d(10,13), d(10,3) + d(3,13)} 2,9, + }= 2,9

d(10,14) d(10,14), d(10,3) + d(3,14)} + }

d(10,15) d(10,15), d(10,3) + d(3,15)} + }

d(10,16) d(10,16), d(10,3) + d(3,16)} + }

d(10,17) d(10,17), d(10,3) + d(3,17)} + }

111

d(11,1) d(11,1), d(11,3) + d(3,1)} + }

d(11,2) d(11,3) + d(3,2)} + }

d(11,3) d(11,3), d(11,3) + d(3,3) + }

d(11,4) d(11,4), d(11,3) + d(3,4)} 0. + }

d(11,5) d(11,5), d(11,3) + d(3,5)} , + }

d(11,6) d(11,6), d(11,3) + d(3,6)} + }

d(11,7) d(11,7), d(11,3) + d(3,7)} , + }

d(11,8) d(11,8), d(11,3) + d(3,8)} + }

d(11,9) d(11,9), d(11,3) + d(3,9)} + }

d(11,10) d(11,10), d(11,3) + d(3,10)} 9,0, + }

d(11,11) d(11,11), d(11,3) + d(3,11)} + }

d(11,12) d(11,12), d(11,3) + d(3,12)} + }

d(11,13) d(11,13), d(11,3) + d(3,13)} + }

d(11,14) d(11,14), d(11,3) + d(3,14)} + }

d(11,15) d(11,15), d(11,3) + d(3,15)} + }

d(11,16) d(11,16), d(11,3) + d(3,16)} 19,7, + }

d(11,17) d(11,17), d(11,3) + d(3,17)} + }

d(12,1) d(12,1), d(12,3) + d(3,1)} + }

d(12,2) d(12,3) + d(3,2)} + }

d(12,3) d(12,3), d(12,3) + d(3,3) + }

d(12,4) d(12,4), d(12,3) + d(3,4)} . + }

d(12,5) d(12,5), d(12,3) + d(3,5)} , + }

d(12,6) d(12,6), d(12,3) + d(3,6)} + }

d(12,7) d(12,7), d(12,3) + d(3,7)} 1,9, + }

112

d(12,8) d(12,8), d(12,3) + d(3,8)} 3,0, + }

d(12,9) d(12,9), d(12,3) + d(3,9)} + }

d(12,10) d(12,10), d(12,3) + d(3,10)} + }

d(12,11) d(12,11), d(12,3) + d(3,11)} + }

d(12,12) d(12,12), d(12,3) + d(3,12)} + }

d(12,13) d(12,13), d(12,3) + d(3,13)} 2,6, + }

d(12,14) d(12,14), d(12,3) + d(3,14)} + }

d(12,15) d(12,15), d(12,3) + d(3,15)} + }

d(12,16) d(12,16), d(12,3) + d(3,16)} + }

d(12,17) d(12,17), d(12,3) + d(3,17)} + }

d(13,1) d(13,1), d(13,3) + d(3,1)} + }

d(13,2) d(13,3) + d(3,2)} + }

d(13,3) d(13,3), d(13,3) + d(3,3) + }

d(13,4) d(13,4), d(13,3) + d(3,4)} . + }

d(13,5) d(13,5), d(13,3) + d(3,5)} , + }

d(13,6) d(13,6), d(13,3) + d(3,6)} + }

d(13,7) d(13,7), d(13,3) + d(3,7)} , + }

d(13,8) d(13,8), d(13,3) + d(3,8)} 2,7, + } = 2,7

d(13,9) d(13,9), d(13,3) + d(3,9)} + }

d(13,10) d(13,10), d(13,3) + d(3,10)} 2,9, + }

d(13,11) d(13,11), d(13,3) + d(3,11)} + }

d(13,12) d(13,12), d(13,3) + d(3,12)} + }

d(13,13) d(13,13), d(13,3) + d(3,13)} , + }

d(13,14) d(13,14), d(13,3) + d(3,14)} + }

113

d(13,15) d(13,15), d(13,3) + d(3,15)} + }

d(13,16) d(13,16), d(13,3) + d(3,16)} + }

d(13,17) d(13,17), d(13,3) + d(3,17)} + }

d(14,1) d(14,1), d(14,3) + d(3,1)} + }

d(14,2) d(14,3) + d(3,2)} + }

d(14,3) d(14,3), d(14,3) + d(3,3) + }

d(14,4) d(14,4), d(14,3) + d(3,4)} . + }

d(14,5) d(14,5), d(14,3) + d(3,5)} , + }

d(14,6) d(14,6), d(14,3) + d(3,6)} + }

d(14,7) d(14,7), d(14,3) + d(3,7)} , + }

d(14,8) d(14,8), d(14,3) + d(3,8)} + }

d(14,9) d(14,9), d(14,3) + d(3,9)} + }

d(14,10) d(14,10), d(14,3) + d(3,10)} + }

d(14,11) d(14,11), d(14,3) + d(3,11)} + }

d(14,12) d(14,12), d(14,3) + d(3,12)} + }

d(14,13) d(14,13), d(14,3) + d(3,13)} 4,1, + }

d(14,14) d(14,14), d(14,3) + d(3,14)} + }

d(14,15) d(14,15), d(14,3) + d(3,15)} 3,5, + }

d(14,16) d(14,16), d(14,3) + d(3,16)} + }

d(14,17) d(14,17), d(14,3) + d(3,17)} + }

d(15,1) d(15,1), d(15,3) + d(3,1)} + }

d(15,2) d(15,3) + d(3,2)} + }

d(15,3) d(15,3), d(15,3) + d(3,3) + }

114

d(15,4) d(15,4), d(15,3) + d(3,4)} . + }

d(15,5) d(15,5), d(15,3) + d(3,5)} , + }

d(15,6) d(15,6), d(15,3) + d(3,6)} + }

d(15,7) d(15,7), d(15,3) + d(3,7)} , + }

d(15,8) d(15,8), d(15,3) + d(3,8)} + }

d(15,9) d(15,9), d(15,3) + d(3,9)} + }

d(15,10) d(15,10), d(15,3) + d(3,10)} + }

d(15,11) d(15,11), d(15,3) + d(3,11)} + }

d(15,12) d(15,12), d(15,3) + d(3,12)} + }

d(15,13) d(15,13), d(15,3) + d(3,13)} + }

d(15,14) d(15,14), d(15,3) + d(3,14)} + }

d(15,15) d(15,15), d(15,3) + d(3,15)} 0, + }

d(15,16) d(15,16), d(15,3) + d(3,16)} 2,9, + }

d(15,17) d(15,17), d(15,3) + d(3,17)} + }

d(16,1) d(16,1), d(16,3) + d(3,1)} + }

d(16,2) d(16,3) + d(3,2)} + }

d(16,3) d(16,3), d(16,3) + d(3,3) + }

d(16,4) d(16,4), d(16,3) + d(3,4)} . + }

d(16,5) d(16,5), d(16,3) + d(3,5)} , + }

d(16,6) d(16,6), d(16,3) + d(3,6)} + }

d(16,7) d(16,7), d(16,3) + d(3,7)} , + }

d(16,8) d(16,8), d(16,3) + d(3,8)} + }

d(16,9) d(16,9), d(16,3) + d(3,9)} + }

d(16,10) d(16,10), d(16,3) + d(3,10)} + }

115

d(16,11) d(16,11), d(16,3) + d(3,11)} + }

d(16,12) d(16,12), d(16,3) + d(3,12)} + }

d(16,13) d(16,13), d(16,3) + d(3,13)} + }

d(16,14) d(16,14), d(16,3) + d(3,14)} + }

d(16,15) d(16,15), d(16,3) + d(3,15)} 2,9, + }

d(16,16) d(16,16), d(16,3) + d(3,16)} 0, + }

d(16,17) d(16,17), d(16,3) + d(3,17)} + }

d(17,1) d(17,1), d(17,3) + d(3,1)} + }

d(17,2) d(17,3) + d(3,2)} + }

d(17,3) d(17,3), d(17,3) + d(3,3) + }

d(17,4) d(17,4), d(17,3) + d(3,4)} . + }

d(17,5) d(17,5), d(17,3) + d(3,5)} , + }

d(17,6) d(17,6), d(17,3) + d(3,6)} + }

d(17,7) d(17,7), d(17,3) + d(3,7)} , + }

d(17,8) d(17,8), d(17,3) + d(3,8)} + }

d(17,9) d(17,9), d(17,3) + d(3,9)} + }

d(17,10) d(17,10), d(17,3) + d(3,10)} + }

d(17,11) d(17,11), d(17,3) + d(3,11)} + }

d(17,12) d(17,12), d(17,3) + d(3,12)} + }

d(17,13) d(17,13), d(17,3) + d(3,13)} + }

d(17,14) d(17,14), d(17,3) + d(3,14)} + }

d(17,15) d(17,15), d(17,3) + d(3,15)} 8,5, + }

d(17,16) d(17,16), d(17,3) + d(3,16)} + }

d(17,17) d(17,17), d(17,3) + d(3,17)} + }

116

Listing Program Option Explicit

Dim distX As Single

Dim distY As Single

Dim i As Integer

Private m_NumPoints As Single

Private m_PointX() As Single

Private m_PointY() As Single

Private Const HANDLE_WIDTH = 30

Private Const HANDLE_HALF_WIDTH = HANDLE_WIDTH / 2

Private Const TwoPi = 6.28318530717959

Public WithEvents titik As kumpulantitik

Public WithEvents garis As kumpulangaris

Dim Awal As String

Dim Akhir As String

Dim awl As Integer

Dim ahr As Integer

Const INF = 32767

Dim sRESULT(1 To 100) As String

Dim iRES_SIZE As Integer

Private Sub prepareFSP()

Dim i As Integer

flxS.Rows = 2

flxDist.Rows = flxgraf.Rows

flxLintasan.Rows = 2

flxS.Cols = flxgraf.Cols

flxDist.Cols = flxgraf.Cols

flxLintasan.Cols = flxgraf.Cols

If flxS.Cols > 1 Then

flxS.FixedRows = 1

flxDist.FixedRows = 1

flxLintasan.FixedRows = 1

flxS.FixedCols = 1

flxDist.FixedCols = 1

flxLintasan.FixedCols = 1

End If

For i = 0 To flxS.Cols - 1

flxS.ColWidth(i) = flxgraf.ColWidth(i)

flxDist.ColWidth(i) = flxgraf.ColWidth(i)

flxLintasan.ColWidth(i) = flxgraf.ColWidth(i)

flxS.TextMatrix(0, i) = flxgraf.TextMatrix(0, i)

flxDist.TextMatrix(0, i) = flxgraf.TextMatrix(0, i)

flxLintasan.TextMatrix(0, i) = flxgraf.TextMatrix(0, i)

117

Next i

For i = 1 To flxS.Cols - 1

flxS.TextMatrix(1, i) = "False"

flxS.Row = 1

flxS.Col = i

flxS.CellForeColor = vbBlack

flxS.CellFontBold = False

flxDist.TextMatrix(1, i) = "INF"

flxLintasan.TextMatrix(1, i) = "0"

Next i

End Sub

Private Sub makeAllLines_Black()

Dim xL As cLine

For Each xL In Form1.garis

xL.theObjectLine.BorderColor = vbBlack

xL.theObjectLine.BorderWidth = 2

Next xL

End Sub

Private Function getShapeID_from_cap(sCap As String) As String

Dim xB As cBlock

For Each xB In Form1.titik

If xB.sCaption = sCap Then

getShapeID_from_cap = xB.TagID

End If

Next xB

End Function

Private Function getIndexOfTabName(s As String) As Integer

Dim i As Integer

For i = 1 To flxgraf.Cols - 1

If flxgraf.TextMatrix(0, i) = s Then

getIndexOfTabName = i

Exit Function

End If

Next i

getIndexOfTabName = -1

End Function

Private Sub markLINES()

Dim i As Integer

Dim tagFrom As String

Dim tagTo As String

For i = iRES_SIZE To 2 Step -1

118

tagFrom = getShapeID_from_cap(sRESULT(i))

tagTo = getShapeID_from_cap(sRESULT(i - 1))

redLINE tagFrom, tagTo

Next i

End Sub

Private Sub redLINE(Awal As String, Akhir As String)

Dim xL As cLine

For Each xL In Form1.garis

If (xL.Awal = Awal) And (xL.Akhir = Akhir) Then

xL.theObjectLine.BorderColor = vbRed

xL.theObjectLine.BorderWidth = 5

End If

Next xL

End Sub

Private Sub cmdAnalisis_Click()

prepareFSP

awl = getIndexOfTabName(Awal)

ahr = getIndexOfTabName(Akhir)

If (awl = -1) Or (ahr = -1) Then

MsgBox "Ada yang salah silahkan cek kembali"

Exit Sub

End If

flxS.Row = 1

flxDist.Row = 1

flxLintasan.Row = 1

Dim MAX As Integer

MAX = flxgraf.Cols

Dim alur As Integer

Dim jrk As Integer

Dim i As Integer

Dim min As Integer

Dim pencarian As Boolean

pencarian = True

alur = awl

jrk = 0

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

flxS.Row = 1

flxS.Col = alur

flxS.CellForeColor = vbRed

flxS.CellFontBold = True

flxDist.TextMatrix(1, alur) = 0

Do While pencarian

If (min = INF) Then

pencarian = False

End If

119

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

flxS.Row = 1

flxS.Col = alur

flxS.CellForeColor = vbRed

flxS.CellFontBold = True

Dim a, j, k, l, m As Integer

For l = 1 To MAX - 1

For m = 1 To MAX - 1

flxhasil.TextMatrix(l, m) = flxgraf.TextMatrix(l, m)

Next m

Next l

For k = 1 To MAX - 1

For a = 1 To MAX - 1

For j = 1 To MAX - 1

If Val(flxhasil.TextMatrix(a, j)) >

Val(flxhasil.TextMatrix(a, k)) + Val(flxhasil.TextMatrix(k, j))

Then

flxhasil.TextMatrix(a, j) = Val(flxhasil.TextMatrix(a, k))

+ Val(flxhasil.TextMatrix(k, j))

End If

Next j

Next a

Next k

For i = 1 To MAX - 1

If ((myVl(flxgraf.TextMatrix(alur, i)) <> 0) And _

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

myVl(flxgraf.TextMatrix(alur, i)) + jrk)) Then

flxDist.TextMatrix(1, i) =

myVl(flxgraf.TextMatrix(alur, i) + jrk)

flxLintasan.TextMatrix(1, i) = alur

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))

alur = i

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

End If

Next i

Loop

iRES_SIZE = 0

makeAllLines_Black

lblhasil.Caption = "Lintasan terpendek:"

120

alur = ahr

Do While alur <> awl

If (flxLintasan.TextMatrix(1, alur) = "0") Then

lblhasil.Caption = "Tidak Ada Lintasan " &

flxgraf.TextMatrix(0, awl) & " ke " & flxgraf.TextMatrix(0, ahr) &

"!"

lbljarak.Caption = ""

Exit Sub

End If

lblhasil.Caption = lblhasil.Caption &

flxgraf.TextMatrix(0, alur)

addTO_RESULT (alur)

lblhasil.Caption = lblhasil.Caption & " <- "

alur = myVl(flxLintasan.TextMatrix(1, alur))

Loop

lblhasil.Caption = lblhasil.Caption & flxgraf.TextMatrix(0,

awl)

addTO_RESULT (awl)

lbljarak.Caption = "Jarak minimum: " & flxDist.TextMatrix(1,

ahr)

markLINES

End Sub

Private Sub cmdbnyktitik_Click()

If txttitik = "" Then

MsgBox "jumlah titik belum dimasukan", vbInformation, "warning"

ElseIf txttitik = 0 Then

MsgBox "jumlah titik belum dimasukan", vbInformation, "warning"

End If

txttitik = Val(txttitik)

mnuAddCircle_Change (Val(txttitik))

Combo1.Clear

For i = 1 To txttitik

Combo1.AddItem i

Next i

Combo2.Clear

For i = 1 To txttitik

Combo2.AddItem i

Next i

End Sub

Private Sub Command1_Click()

121

If Combo1 = "" And Combo2 = "" Then

MsgBox "Dua Titik belum diseleksi", vbInformation, "warning"

ElseIf Combo1 = "" Then

MsgBox "Titik awal belum dipilih", vbInformation, "warning"

ElseIf Combo1 = 0 Then

MsgBox "Titik awal belum dipilih", vbInformation, "warning"

End If

If Text1 = "" Then

MsgBox "Bobot belum dimasukan", vbInformation, "warning"

End If

Combo1 = Val(Combo1)

Combo2 = Val(Combo2)

Text1 = Val(Text1)

If Combo1 Then

garis.AddLine Form1.shp(Combo1).Tag,

Form1.shp(Combo2).Tag, True

garis.AddLine Form1.shp(Combo2).Tag,

Form1.shp(Combo1).Tag, True

If vbInformation Then

garis.deleteLine Combo2, Combo2

If Text1.Text = "0" Then

garis.deleteLine Combo1, Combo2

Else

Dim s As String

s = Text1.Text

garis.AddCaptionToLine Form1.shp(Combo1).Tag,

Form1.shp(Combo2).Tag, s

End If

End If

End If

Dim i As Integer

Dim j As Integer

Dim toIndex As Integer

flxgraf.Rows = Form1.titik.Count + 1

flxgraf.Cols = Form1.titik.Count + 1

flxhasil.Rows = Form1.titik.Count + 1

flxhasil.Cols = Form1.titik.Count + 1

If Form1.titik.Count > 0 Then

flxgraf.FixedRows = 1

flxgraf.FixedCols = 1

flxhasil.FixedRows = 1

122

flxhasil.FixedCols = 1

End If

For i = 0 To flxgraf.Cols - 1

flxgraf.ColWidth(i) = 530

Next i

For i = 0 To flxhasil.Cols - 1

flxhasil.ColWidth(i) = 530

Next i

For i = 1 To Form1.titik.Count

flxgraf.Row = i

flxgraf.Col = 0

flxgraf.Text = Form1.titik(i).sCaption

flxgraf.Row = 0

flxgraf.Col = i

flxgraf.Text = Form1.titik(i).sCaption

flxgraf.Row = i

flxhasil.Row = i

flxhasil.Col = 0

flxhasil.Text = Form1.titik(i).sCaption

flxhasil.Row = 0

flxhasil.Col = i

flxhasil.Text = Form1.titik(i).sCaption

flxhasil.Row = i

For j = 1 To flxgraf.Cols - 1

flxgraf.TextMatrix(i, j) = "1000"

flxgraf.Col = j

flxgraf.CellForeColor = vbBlack

flxgraf.CellFontBold = False

If i = j Then

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

End If

Next j

For j = 1 To Form1.garis.Count

If Form1.garis(j).Awal = Form1.titik(i).TagID Then

toIndex =

Form1.titik.getIndexFromTag(Form1.garis(j).Akhir)

flxgraf.Col = toIndex

flxgraf.Text = Form1.garis(j).sCaption

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

flxgraf.CellForeColor = vbRed

123

flxgraf.CellFontBold = True

End If

Next j

Next i

End Sub

Private Sub garismerah(Awal As String, Akhir As String)

Dim xL As cLine

For Each xL In Form1.garis

If (xL.Awal = Awal) And (xL.Akhir = Akhir) Then

xL.theObjectLine.BorderWidth = 2

xL.theObjectLine.BorderColor = vbBlack

End If

Next xL

End Sub

Private Sub Form_Click()

If PREV_SELECTED_SHAPE = -1 Or SELECTED_SHAPE = -1 Then

lblasal.Caption = "nothing selected"

cmdAnalisis.Enabled = False

Else

cmdAnalisis.Enabled = True

Awal =

Form1.titik(Form1.shp(PREV_SELECTED_SHAPE).Tag).sCaption

Akhir =

Form1.titik(Form1.shp(SELECTED_SHAPE).Tag).sCaption

lblasal.Caption = "Dari: " & Awal & " Ke: " & Akhir

End If

End Sub

Private Function myVl(s As String) As Double

If s = "INF" Then

myVl = INF

Else

myVl = Val(s)

End If

End Function

Private Sub addTO_RESULT(Index As Integer)

iRES_SIZE = iRES_SIZE + 1

sRESULT(iRES_SIZE) = flxgraf.TextMatrix(0, Index)

End Sub

124

Private Sub Form_Load()

MAX_SHAPE = 0

DRAGGED_SHAPE = -1

SELECTED_SHAPE = -1

PREV_SELECTED_SHAPE = -1

Set titik = New kumpulantitik

Set garis = New kumpulangaris

MAX_LINE = 0

End Sub

Private Sub Form_MouseUp(Button As Integer, Shift As Integer, X As

Single, Y As Single)

DRAGGED_SHAPE = -1

update_from_to

End Sub

Private Sub Form_Unload(Cancel As Integer)

End

End Sub

Private Sub hapus_Click()

Dim s As String

If SELECTED_SHAPE <> -1 Then

titik(Form1.shp(SELECTED_SHAPE).Tag).sCaption = " "

titik(Form1.shp(SELECTED_SHAPE).Tag).titikatas = s

titik(Form1.shp(SELECTED_SHAPE).Tag).bSetUpperCaptionDown

= False

titik(Form1.shp(SELECTED_SHAPE).Tag).updateShapeCaptionPos

titik.removeShape SELECTED_SHAPE

SELECTED_SHAPE = -1

Else

MsgBox "Buat Titik Terlebih Dahulu", vbInformation, "warning"

End If

End Sub

Private Sub keluar_Click()

End

End Sub

Private Sub lblgaris_MouseDown(Index As Integer, Button As

Integer, Shift As Integer, X As Single, Y As Single)

Form_MouseDown Button, Shift, X / Screen.TwipsPerPixelX +

lblgaris(Index).Left, Y / Screen.TwipsPerPixelY +

lblgaris(Index).Top

End Sub

Private Sub lblgaris_MouseMove(Index As Integer, Button As

Integer, Shift As Integer, X As Single, Y As Single)

125

Form_MouseMove Button, Shift, X / Screen.TwipsPerPixelX +

lblgaris(Index).Left, Y / Screen.TwipsPerPixelY +

lblgaris(Index).Top

End Sub

Private Sub lblgaris_MouseUp(Index As Integer, Button As Integer,

Shift As Integer, X As Single, Y As Single)

Form_MouseUp Button, Shift, X / Screen.TwipsPerPixelX +

lblgaris(Index).Left, Y / Screen.TwipsPerPixelY +

lblgaris(Index).Top

End Sub

Private Sub lbltengah_MouseDown(Index As Integer, Button As

Integer, Shift As Integer, X As Single, Y As Single)

Form_MouseDown Button, Shift, X / Screen.TwipsPerPixelX +

lbltengah(Index).Left, Y / Screen.TwipsPerPixelY +

lbltengah(Index).Top

End Sub

Private Sub lbltengah_MouseMove(Index As Integer, Button As

Integer, Shift As Integer, X As Single, Y As Single)

Form_MouseMove Button, Shift, X / Screen.TwipsPerPixelX +

lbltengah(Index).Left, Y / Screen.TwipsPerPixelY +

lbltengah(Index).Top

End Sub

Private Sub lbltengah_MouseUp(Index As Integer, Button As Integer,

Shift As Integer, X As Single, Y As Single)

Form_MouseUp Button, Shift, X / Screen.TwipsPerPixelX +

lbltengah(Index).Left, Y / Screen.TwipsPerPixelY +

lbltengah(Index).Top

End Sub

Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X

As Single, Y As Single)

Dim i As Integer

For i = MAX_SHAPE To 1 Step -1

If (shp(i).Visible = True) And _

(X > shp(i).Left) And (X < shp(i).Left + shp(i).Width)

_

And (Y > shp(i).Top) And (Y < shp(i).Top +

shp(i).Height) Then

DRAGGED_SHAPE = i

If SELECTED_SHAPE <> i Then

PREV_SELECTED_SHAPE = SELECTED_SHAPE

126

SELECTED_SHAPE = i

End If

distX = X - shp(i).Left

distY = Y - shp(i).Top

lblID(0).Caption = shp(i).Tag

Exit For

End If

Next i

End Sub

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X

As Single, Y As Single)

If DRAGGED_SHAPE <> -1 Then

shp(DRAGGED_SHAPE).Left = X - distX

shp(DRAGGED_SHAPE).Top = Y - distY

garis.updateLines

titik(shp(DRAGGED_SHAPE).Tag).updateShapeCaptionPos

End If

End Sub

Private Sub mnuNew_Click()

load_FILE Add_BackSlash(App.Path) & "new project.tzr"

End Sub

Private Sub load_FILE(sFILE As String)

On Error GoTo err_lf

Dim i As Integer

Dim mFileNum As Integer

mFileNum = FreeFile

If sFILE = "" Then Exit Sub

For i = 1 To MAX_SHAPE

Unload shp(i)

Unload lbltengah(i)

Unload lbltitikatas(i)

Next i

MAX_SHAPE = 0

For i = titik.Count To 1 Step -1

titik.Remove i

Next i

For i = 1 To MAX_LINE

Unload ln(i)

Unload aDot(i)

Unload arrUp(i)

Unload arrDown(i)

Unload lblgaris(i)

Next i

MAX_LINE = 0

127

For i = garis.Count To 1 Step -1

garis.Remove i

Next i

Open sFILE For Input As mFileNum

Dim tempS As String

Dim lineCounter As Integer

Dim shapeCounter As Integer

Line Input #mFileNum, tempS

shapeCounter = Val(tempS)

Line Input #mFileNum, tempS

lineCounter = Val(tempS)

Dim xS As cBlock

Dim sName As String

For i = 1 To shapeCounter

Line Input #mFileNum, tempS

sName = tempS

Line Input #mFileNum, tempS

Set xS = titik.AddShape(Val(tempS), sName)

Line Input #mFileNum, tempS

xS.shapeLeft = Val(tempS)

Line Input #mFileNum, tempS

xS.shapeTop = Val(tempS)

Line Input #mFileNum, tempS

xS.shapeWidth = Val(tempS)

Line Input #mFileNum, tempS

xS.shapeHeight = Val(tempS)

Line Input #mFileNum, tempS

xS.shapeBackColor = Val(tempS)

Line Input #mFileNum, tempS

xS.shapeBorderColor = Val(tempS)

Line Input #mFileNum, tempS

xS.sCaption = tempS

Line Input #mFileNum, tempS

xS.titikatas = tempS

Line Input #mFileNum, tempS

xS.bSetUpperCaptionDown = Val(tempS)

xS.updateShapeCaptionPos

xS.Visible = True

Next i

Line Input #mFileNum, tempS

Line Input #mFileNum, tempS

Dim sFrom As String

Dim sTo As String

Dim psik_index As Integer

Dim xL As cLine

128

For i = 1 To lineCounter

Line Input #mFileNum, tempS

psik_index = InStr(1, tempS, ",")

sFrom = Mid(tempS, 1, psik_index - 1)

sTo = Mid(tempS, psik_index + 1)

Line Input #mFileNum, tempS

Set xL = garis.AddLine(sFrom, sTo, Val(tempS))

Line Input #mFileNum, tempS

xL.sCaption = tempS

Next i

garis.updateLines

Close mFileNum

update_from_to

Exit Sub

err_lf:

MsgBox "Load: " & sFILE & vbNewLine & Err.Description

End Sub

Private Sub titik_linkError(sERROR As String)

MsgBox sERROR

End Sub

Private Sub garis_linkError(sERROR As String)

MsgBox sERROR

End Sub

Private Sub update_from_to()

On Error GoTo err_uft

Dim sFrom As String

Dim sTo As String

sFrom = "?"

sTo = "?"

If PREV_SELECTED_SHAPE <> -1 Then

sFrom = titik(Form1.shp(PREV_SELECTED_SHAPE).Tag).titikatas

End I

If SELECTED_SHAPE <> -1 Then

sTo = titik(Form1.shp(SELECTED_SHAPE).Tag).titikatas

End If

Exit Sub

err_uft:

Debug.Print "update_from_to: " & Err.Description

End Sub

Private Sub Toolbar1_ButtonClick(ByVal Button As

MSComctlLib.Button)

titik.AddShape 3, titik.getFreeTagID()

End Sub

Private Sub Toolbar10_ButtonClick(ByVal Button As

MSComctlLib.Button)

129

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

Dim s As String

s = InputBox("Enter the caption")

garis.AddCaptionToLine Form1.shp(PREV_SELECTED_SHAPE).Tag,

Form1.shp(SELECTED_SHAPE).Tag, s

Else

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub Toolbar12_ButtonClick(ByVal Button As

MSComctlLib.Button)

garis.deleteLine SELECTED_SHAPE, PREV_SELECTED_SHAPE

End Sub

Private Sub Toolbar2_ButtonClick(ByVal Button As

MSComctlLib.Button)

titik.AddShape 3, titik.getFreeTagID()

End Sub

Private Sub Toolbar3_ButtonClick(ByVal Button As

MSComctlLib.Button)

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

garis.AddLine Form1.shp(PREV_SELECTED_SHAPE).Tag,

Form1.shp(SELECTED_SHAPE).Tag, False

Else

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub Toolbar4_ButtonClick(ByVal Button As

MSComctlLib.Button)

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

garis.AddLine Form1.shp(PREV_SELECTED_SHAPE).Tag,

Form1.shp(SELECTED_SHAPE).Tag, True

Else

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub Toolbar5_ButtonClick(ByVal Button As

MSComctlLib.Button)

If (SELECTED_SHAPE <> -1) Then

Dim s As String

s = InputBox("Masukan Nilai!", "Caption",

titik(Form1.shp(SELECTED_SHAPE).Tag).sCaption)

titik(Form1.shp(SELECTED_SHAPE).Tag).sCaption = s

titik(Form1.shp(SELECTED_SHAPE).Tag).updateShapeCaptionPos

Else

130

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub Toolbar7_ButtonClick(ByVal Button As

MSComctlLib.Button)

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

Dim s As String

s = InputBox("Masukan Nilai!")

garis.AddCaptionToLine Form1.shp(PREV_SELECTED_SHAPE).Tag,

Form1.shp(SELECTED_SHAPE).Tag, s

Else

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub Toolbar9_ButtonClick(ByVal Button As

MSComctlLib.Button)

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

Dim s As String

s = InputBox("Masukan Nilai!")

garis.AddCaptionToLine Form1.shp(PREV_SELECTED_SHAPE).Tag,

Form1.shp(SELECTED_SHAPE).Tag, s

Else

MsgBox "Seleksilah dua objek terlebih dahulu!"

End If

End Sub

Private Sub mnuAddCircle_Change(AddShape3 As Integer)

Dim VertexNum As Integer

Dim s As String

m_NumPoints = Val(txttitik)

m_NumPoints = AddShape3

'Make new caption (Messy calculations I know!!!)

' Make room.

If m_NumPoints > 0 Then

ReDim Preserve m_PointX(0 To m_NumPoints)

ReDim Preserve m_PointY(0 To m_NumPoints)

' Set initial points.

For VertexNum = 1 To m_NumPoints

titik.AddShape 3, titik.getFreeTagID()

s = 0 + VertexNum

titik(Form1.shp(SELECTED_SHAPE).Tag).sCaption = s

titik(Form1.shp(SELECTED_SHAPE).Tag).updateShapeCaptionPos

Next

' Draw.Refresh

End If

End Sub