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 i
ii
iii
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
memberikan doa, semangat, dan dukungan.
Untuk keluarga Matematika 2011.
Almamaterku.
iv
henti-hentinya
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.
v
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
vi
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 FloydWarshall 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 FloydWarshall 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.
vii
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 viii
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
ix
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
x
DAFTAR TABEL Halaman' Gambar 4.1 Data tempat dan jarak wilayah kota Semarang ............................... 38
xi
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
xii
DAFTAR LAMPIRAN Halaman Lampiran 1 Analisis Manual………………………………………………... Lampiran 2 Listing Program………………………………………………
xiii
79 116
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 1
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
menghemat
biaya
transportasi
20% dari negara maju. Selama dapat 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. Titiktitik 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.
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
dinyatakan dengan pasangan ( ,
), atau dengan lambang
kata lain, jika e adalah sisi yang menghubungkan titik maka e dapat dituliskan sebagai e = ( , bilangan asli 1, 2, 3, ...
10
dengan titik ,
, ... Dengan
dengan titik
,
), di mana i,j adalah indeks angka
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 titik
dan
dan titik . titik
. Titik
menunjukkan arah ke
menunjukkan kearah titik
, dan seterusnya. Bobot antara titik
ke
,
dan titik
adalah 2, titik
ke
adalah 4 dan seterusnya. 𝑣
𝑣
3
2 𝑣
6
𝑣
2
7
5 6 6
4
𝑣
3
𝑣 3
𝑣 2
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 tidak menunjukkan arah ke titik dan titik
dan atau
. Titik
, namun bobot antara titik
telah diketahui. Begitu juga dengan titik yang lain.
13
𝑣
𝑣
3
2 𝑣
6
𝑣
6
3
𝑣
4
𝑣
2
6
7
5
3 𝑣
2 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 ke titik
dan
atau
. Titik
. Titik
menunjukkan arah
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
.
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.
𝑣
𝑣
𝑒
𝑒 𝑣
𝑒 𝑒
𝑣
𝑣
𝑒
𝑒
𝑒8 𝑒 𝑒9
𝑒
0
𝑣8 𝑒
𝑣
𝑒 Gambar 2.5 Representasi Graf
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 [ , terdapat sisi dari
ke
] berharga 1 bila
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
A=
(
)
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=
(
)
17
2.1.5 Keterhubungan pada Graf 1) Jalan (Walk) Jalan atau walk pada suatu Graf G adalah barisan titik dan sisi berganti-ganti. dan
:
,…,
,
,
, …,
;
sisi
,
menghubungkan
dapat hanya ditulis barisan sisi atau barisan titik saja. ;
awal, dan diantara
,
atau
,
,…,
;
,
. Dalam hal ini,
disebut titik
disebut titik akhir, sedangkan titik-titik yang berada 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.
𝑣
3
𝑣 2 𝑣
7
5 6
𝑣
2
6 6
4
3
3
𝑣
𝑣
𝑣
2 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
20
→ → →
= 4+3+6
= 13
→ → →
= 4+2+3
=9
Berdasarkan data di atas, lintasan terpendek dari melewati
dan
ke
adalah 9 dengan
.
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. ketetanggaan berbobot terkecil dengan dari titik
ke
1)
sama dengan lintasan terpendek
.
0
2) Untuk =1 hingga , lakukan: Untuk =1 hingga , lakukan: Untuk =1 hingga
lakukan:
3) Jika W[ ,j] > W[ , ] + Tukar 4)
=
[ ,j] dengan
[ , ] maka [ , ]+
adalah matriks
[ ,]
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 sisi
ke
adalah panjang dari sisi
. Setelah iterasi pertama pada langkah 2 (k=1),
jarak yang diperoleh digantikan dengan panjang dari lintasan iterasi k pada algoritma ini dapat ditentukan jarak terpendek dari pada titik-titik
,
, …..,
. Setelah ke
. 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
𝑽𝟏 5 𝑽𝟐 9
3
1
𝑽𝟑
𝑽𝟒
1 Gambar 2.7 : Graf Berbobot
Bentuk matriksnya adalah sebagai berikut.
(
)
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 adalah 0, jarak dari titik adalah 6 dan sebagainya.
ke
adalah 5,
ke
adalah 7,
ke ke
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
Gambar 2.8 Interface Visual Basic 6.0 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.
BAB III METODE PENELITAN
Untuk melakukan penelitian harus memperhatikan prosedur dan langkahlangkah 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
33
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.
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.
74
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 FloydWarshall.
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.
76
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)}
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)}
+
+
}
0,9, 0 + 0,9} = 0,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)}
d(3,2)
d(3,1) + d(1,2)}
0,9, 0,9 + 0} = 0,9 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)}
d(3,8) d(3,9) d(3,10)
+ +
}
+
}
d(3,8), d(3,1) + d(1,8)}
+
}
d(3,9), d(3,1) + d(1,9)}
+
}
d(3,10), d(3,1) + d(1,10)}
4,9,
+
}
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)}
d(4,3)
d(4,3), d(4,1) + d(1,3)
d(4,4)
d(4,4), d(4,1) + d(1,4)}
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,9)
+ } +
} = 4,1
+ 0.
+ ,
,
} }
+
}
+
}
+
}
d(4,8), d(4,1) + d(1,8)}
+
}
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.
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,9)
}
+
}
+
} = 2,4
+
}
+
}
+
}
d(5,8), d(5,1) + d(1,8)}
+
}
d(5,9), d(5,1) + d(1,9)}
+
}
,
d(5,10)
d(5,10), d(5,1) + d(1,10)}
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)}
8,1,
+
}
+
+ } +
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)}
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)}
2,7,
+
}
+
}
+ } +
}
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)
+
}
+
}
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)}
2,9,
+ } +
. ,
,
}
+
}
+
}
+
}
+
}
+
}
+
}
+
}
86
d(10,10)
d(10,10), d(10,1) + d(1,10)}
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
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)}
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,9)
0,
+
2,9,
}
+ } +
}
+ 0.
+ ,
} }
+
}
+
}
+
}
d(11,8), d(11,1) + d(1,8)}
+
}
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)}
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)}
2,6,
+
}
+
}
+ } + +
}
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)}
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,9)
2,9,
+ +
} }
+ ,
+
} }
+
}
+ } +
}
+
}
.
+
}
,
+
}
+
}
+
}
d(14,8), d(14,1) + d(1,8)}
+
}
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)}
d(14,14)
d(14,14), d(14,1) + d(1,14)}
d(14,15)
d(14,15), d(14,1) + d(1,15)}
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,9)
4,1,
+ +
3,5,
} }
+
}
+ } +
}
+
}
.
+
}
,
+
}
+
}
+
}
d(15,8), d(15,1) + d(1,8)}
+
}
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)}
d(17,16)
d(17,16), d(17,1) + d(1,16)}
+
}
d(17,17)
d(17,17), d(17,1) + d(1,17)}
+
}
8,5,
+
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)}
d(3,8) d(3,9)
+
}
+
}
d(3,8), d(3,2)+d(2,8)}
+
}
d(3,9), d(3,2)+d(2,9)}
+
}
4,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)}
d(4,3)
d(4,3), d(4,2)+d(2,3)
d(4,4)
d(4,4), d(4,2)+d(2,4)}
d(4,5)
d(4,5), d(4,2)+d(2,5)}
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)}
,
+
}
+ 0} = 4,1 + 0.
}
+ 4,1} = 0 ,
+ 5,7} = 2,4 +
,
}
+
}
+
}
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)}
d(5,5)
d(5,5), d(5,2)+d(2,5)}
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,9)
+
}
+ } +
}
2,4. 5,7 + 4,1} = 2,4 , 5,7 + 5,7} = 0 +
}
+
}
d(5,8), d(5,2)+d(2,8)}
+
}
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)}
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)}
2,7,
+
}
+
}
}
+ }
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)
+
}
+
}
d(9,14)
+
}
+
}
d(9,15)
+
}
+
}
d(9,16)
+
}
+
}
d(9,17)
+
}
+
}
2,9,
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)}
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)}
+
}
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)}
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)}
0,
}
+
2,9,
+
}
}
+ } + 0.
+ ,
,
} }
+
}
+
}
+
}
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)}
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)}
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)}
9,0,
+
19,7,
}
+ +
+
} }
}
+ }
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)}
d(12,14)
d(12,14), d(12,2)+d(2,14)}
2,6,
+
}
+
}
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)}
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)
2,9,
+ +
} }
+ ,
+
} }
+
+
}
+ } +
}
}
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,9)
+
}
+
}
d(14,8), d(14,2)+d(2,8)}
+
}
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)}
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)}
4,1,
+
}
+
}
+
} +
+
}
+
}
+
}
+ }
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,9) d(15,10)
+
}
+
}
+
}
d(15,8), d(15,2)+d(2,8)}
+
}
d(15,9), d(15,2)+d(2,9)}
+
}
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,9)
+
+
} +
}
+
}
}
+ } +
}
.
+
}
,
+
}
+
}
+
}
d(16,8), d(16,2)+d(2,8)}
+
}
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,9)
+
}
+
}
d(17,8), d(17,2)+d(2,8)}
+
}
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)}
d(17,16)
d(17,16), d(17,2)+d(2,16)}
+
}
d(17,17)
d(17,17), d(17,2)+d(2,17)}
+
}
8,5,
+
}
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)}
d(1,4)
d(1,4), d(1,3) + d(3,4)}
+
}
d(1,5)
, d(1,3) + d(3,5)}
+
}
+
}
0,9, 0,9 + 0,9} = 0,9
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)}
d(3,2)
d(3,3) + d(3,2)}
0,9, 0 + 0} = 0,9 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)
d(4,4)
d(4,4), d(4,3) + d(3,4)}
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,9)
+
}
+ 0,9} = 0.
+ ,
,
} +
}
+
}
+
}
d(4,8), d(4,3) + d(3,8)}
+
}
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.
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)}
}
+
,
}
+
} = 2,4
+
}
+
}
+
}
+
}
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)}
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,1,
+
} +
}
+ } 8,7 +
d(6,3)
d(6,3), d(6,3) + d(3,3)
d(6,4)
d(6,4), d(6,3) + d(3,4)}
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)}
}
8,7 + 0,9} = 8,7 2,2. 8,7 + 9,1} = 2,2 ,
+
}
+
}
+
}
+
}
+
}
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)}
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)}
2,7,
+
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,11)
. ,
+
}
}
}
+
}
+
}
+
}
+
}
+
}
+ +
d(9,10), d(9,3) + d(3,10)} +
}
+ }
d(9,3)
d(9,10)
+
} }
1,9,
+ +
} }
110
d(9,12)
+
}
d(9,13)
+
}
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)}
2,9,
+
}
+
}
+ } +
.
+
}
+
}
,
,
}
+
}
+
}
+
}
+
}
+ 0,
}
d(10,10)
d(10,10), d(10,3) + d(3,10)}
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
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)}
+
}
2,9,
+
}
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)}
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,9)
+ } +
}
+ 0.
+
} }
,
+
}
+
}
+
}
d(11,8), d(11,3) + d(3,8)}
+
}
d(11,9), d(11,3) + d(3,9)}
+
}
,
d(11,10)
d(11,10), d(11,3) + d(3,10)}
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)}
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)}
9,0,
+
19,7,
+ +
+ } +
}
+
}
.
+
}
,
+
}
+
}
1,9,
+
}
}
} }
112
d(12,8)
d(12,8), d(12,3) + d(3,8)}
d(12,9)
d(12,9), d(12,3) + d(3,9)}
3,0,
+ +
} }
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)}
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)}
2,6,
+
}
+
}
+ } +
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,
d(13,9)
d(13,9), d(13,3) + d(3,9)}
d(13,10)
d(13,10), d(13,3) + d(3,10)}
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)}
+
} }
+
} = 2,7
+
}
2,9,
+ +
} }
+ ,
+ +
} } }
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,9)
+ } +
}
+
}
.
+
}
,
+
}
+
}
+
}
d(14,8), d(14,3) + d(3,8)}
+
}
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)}
d(14,14)
d(14,14), d(14,3) + d(3,14)}
d(14,15)
d(14,15), d(14,3) + d(3,15)}
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)
4,1,
+
}
+
}
+ 3,5,
} +
+ } + +
} }
}
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,9)
+
}
+ +
} }
+
}
+ } +
}
+
}
.
+
}
,
+
}
+
}
+
}
d(17,8), d(17,3) + d(3,8)}
+
}
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)}
d(17,16)
d(17,16), d(17,3) + d(3,16)}
+
}
d(17,17)
d(17,17), d(17,3) + d(3,17)}
+
}
8,5,
+
}
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 Dim Dim Dim
Sub markLINES() i As Integer tagFrom As String 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
