SISTEM INFORMASI PENCARIAN LINTASAN TERPENDEK MENGGUNAKAN PEMROGRAMAN DINAMIS. Gerdyandanu Nilanto

SISTEM INFORMASI PENCARIAN LINTASAN TERPENDEK MENGGUNAKAN PEMROGRAMAN DINAMIS

Gerdyandanu Nilanto

PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011 M /1432 H


Skripsi Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Sarjana Sains Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta

Oleh: Gerdyandanu Nilanto 107094003005

PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2011 M /1432 H

PENGESAHAN UJIAN

Skripsi berjudul “Sistem Informasi Pencarian Lintasan Terpendek Menggunakan Pemrograman Dinamis” yang ditulis oleh Gerdyandanu Nilanto, NIM 107094003005 telah diuji dan dinyatakan lulus dalam Sidang Munaqosyah Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta pada tanggal 10 Juni 2011. Skripsi ini telah diterima sebagai salah satu syarat untuk memperoleh gelar Sarjana Strata Satu (S1) Program Studi Matematika. Menyetujui, Penguji I,

Penguji II,

Nur Inayah, M.Si NIP. 19740125 200312 2 001

Gustina Elfiyanti, M.Si NIP. 19820820 200901 2 006

Pembimbing I,

Pembimbing II,

Drs. Slamet Aji Pamungkas, M.Eng NIP. 19670618 199301 1 001

Yanne Irene, M.Si NIP. 19741231 200501 2 018 Mengetahui,

Dekan Fakultas Sains dan Teknologi,

Ketua Program Studi Matematika,

Dr. Syopiansyah Jaya Putra, M.Sis NIP. 19680117 200112 1 001

Yanne Irene, M.Si NIP. 19741231 200501 2 018 ii

PERNYATAAN

DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENARBENAR HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU LEMBAGA MANAPUN.

Jakarta, 16 Juni 2011

Gerdyandanu Nilanto NIM. 107094003005

iii

PERSEMBAHAN Skripsi ini aku persembahkan untuk ayahku Tarto, ibuku Ratini, adik-adikku (Mige, Bahy), saudara-saudaraku, sahabat-sahabatku dan kepada seluruh keluarga besar Prodi Matematika, terimakasih atas segalanya. Semoga kita selalu diridoi Allah SWT dan selalu dalam lindungan-Nya. serta selalu dibukakan pintu rahmat, kasih sayang dan hidayah-Nya kepada kita semua. Amiin.

MOTTO “Orang yang sukses adalah orang yang siap untuk sukses”.

“Hai orang-orang yang beriman, jadikanlah sabar dan shalat sebagai penolongmu, sesungguhnya Allah beserta orang-orang yang sabar”. (QS. Al Baqarah: 153)

“Jika kebahagiaan itu memang ada, maka carilah kebahagiaan itu. Dan jangan pernah menyerah” (Naruto)

Ingat 4S (© Gerdy) Siap : siapkan apa yang akan anda lakukan. Sabar : sabar dalam mengejakan apapun. Senyum : tersenyumlah agar semuanya baik-baik saja_^, Dan Syukur : syukuri apa yang didapat.

iv

ABSTRAK

Pada skripsi ini akan dibahas sebuah sistem informasi untuk mencari lintasan terpendek. Pencarian lintasan terpendek merupakan salah satu permasalahan pada graf yang diaplikasikan dalam kehidupan sehari-hari dengan mencari jarak minimal dari suatu tempat ke tempat lain melalui beberapa lintasan. Dapat dikatakan permasalahan ini merupakan sebuah permasalahan optimasi. Selanjutnya metode yang coba digunakan untuk menyelesaikan permasalahan ini adalah dengan menggunakan pemrograman dinamis. Pemrograman dinamis merupakan sebuah metode penyelesaian masalah dengan cara menguraikan permasalahan menjadi subpermasalahan yang berkaitan untuk menghasilkan solusi optimal. Kemudian dengan mengimplementasikan suatu bahasa pemrograman dan pengoperasian basis data maka skripsi ini menghasilkan sebuah sistem informasi yang berguna untuk mempermudah dalam pencarian lintasan terpendek. Kata Kunci : Basis Data, Graf, Lintasan Terpendek, dan Pemrograman Dinamis.

v

ABSTRACT

In this paper will be explained a information system of looking for shortest path. Looking for the shortest path is one of problem in graph, which is applied in daily life to look for a minimal distance from a place to another place through some path. This problem can be said a optimation problem. Furthermore the method will be used to complete this problem by using dynamic programming. Dynamic Programming is a finishing method problem which analyze a problem become subproblem that related to get optimal solution. Then to implement a programming language and operation database, so this paper get a result a information of that can be useful to look for the shortest path. Keyword : Database, Dynamic Programming, Graph, and Shortest Path.

vi

KATA PENGANTAR

Segala puji bagi Allah SWT, Alhamdulillah atas segala karunia-Nya, sehingga penulis dapat menyelesaikan skripsi yang berjudul “Sistem Informasi Pencarian Lintasan Terpendek Menggunakan Pemrograman Dinamis”. Penulis menyadari bahwa skripsi ini dapat diselesaikan karena dukungan dan bantuan dari berbagai pihak yang tidak dapat penulis balas dengan seimbang budi baik mereka karena keterbatasan penulis sebagai manusia biasa. Pada kesempatan ini, penulis ingin mengucapkan terima kasih kepada : 1. DR. Syopiansyah Jaya Putra, M.Sis, Dekan Fakultas Sains dan Teknologi. 2. Yanne Irene, M.Si, Ketua Program Studi Matematika sekaligus sebagai pembimbing II penulis, terima kasih atas ketulusan dan kesabaran ibu dalam membimbing penulis baik dari segi materi skripsi maupun penyemangat penulis untuk menyelesaikan skripsi. 3. Suma’inna, M.Si, Sekertaris Program Studi Matematika yang selalu memberikan semangat kepada mahasiswa, terima kasih banyak ibu. 4. Drs. Slamet Aji Pamungkas, M.Eng, sebagai pembimbing I penulis yang telah banyak membantu penulis dalam menyelesaikan aplikasi skripsi ini sampai selesai, terimaksih banyak bapak. 5. Kepada Ayah dan Ibuku tersayang, atas kasih sayang dan dukungan yang tidak henti-hentinya, terima kasih banyak karena telah memberikan jalan untuk hidup ini, serta kepada adik-adikku terhebat yang selalu ceria,amin. Aku sayang kalian.

vii

6. Pak Taufik Edy Sutanto, M.ScTech, yang sudah mau direpotkan oleh penulis dari sebelum penulisan skripsi sampai skripsi ini selesai. Terimakasih banyak dan semangat selalu ngajarnya pak. 7. Ka Dennis Sugianto, S.Si, terima kasih banyak atas bantuan laptopnya dan sudah menjadi teman yang baik sampai saat ini, thanks for all ka’, 8. Serta, terima kasih kepada seluruh dosen Prodi Matematika yang telah memberikan ilmu-ilmunya yang bermanfaat selama kuliah. 9. Aghia, Ari, Nova, Dendy, Hamza, Ubai, Adil, sahabat-sahabat matsos, temanteman angkatan 2007, Nur, Selly, Derry, teman-teman angkatan 2008, Maya (FAH) serta seluruh keluarga besar matematika atas semangat yang telah diberikan saya ucapkan terimakasih banyak, Sukses Buat Kalian Semua Ya !! Penulis menyadari bahwa dalam penyusunan laporan ini masih banyak kekurangannya. Oleh karena itu, penulis memohon kritik dan saran yang dapat membangun tulisan skripsi ini agar lebih baik lagi sehingga dapat bermanfaat untuk orang banyak. Jakarta, April 2010

Penulis

viii

DAFTAR ISI

HALAMAN JUDUL ................................................................................ i PENGESAHAN UJIAN ........................................................................... ii PERNYATAAN ........................................................................................ iii PERSEMBAHAN DAN MOTTO ............................................................ iv ABSTRAK ................................................................................................ v ABSTRACT .............................................................................................. vi KATA PENGANTAR .............................................................................. vii DAFTAR ISI ............................................................................................. ix DAFTAR TABEL .................................................................................... xii DAFTAR GAMBAR ................................................................................ xiii BAB I PENDAHULUAN ......................................................................... 1 1.1 Latar Belakang ......................................................................... 1 1.2 Perumusan Masalah ................................................................. 3 1.3 Pembatasan Masalah ................................................................ 3 1.4 Tujuan ...................................................................................... 3 1.5 Manfaat .................................................................................... 4 BAB II LANDASAN TEORI .................................................................. 5 2.1 Konsep Dasar Teori Graf ......................................................... 5 2.2 Lintasan Terpendek .................................................................. 8 2.3 Representasi Graf dalam Matriks ............................................. 8 2.4 Pemrograman Dinamis ............................................................. 10

ix

2.5 Algoritma Pemrograman Dinamis ........................................... 14 2.6 Basis Data ................................................................................ 15 2.7 Normalisasi .............................................................................. 17 2.8 Entity Relathionship Diagram (ERD) ...................................... 18 2.9 MySQL ..................................................................................... 18 2.10 Hypertext Preprocessor (PHP) .............................................. 19 BAB III METODOLOGI PERANCANGAN SISTEM ........................ 20 3.1 Metode Pengumpulan Data ...................................................... 20 3.2 Metode Pengolahan Data ......................................................... 20 3.3 Rancangan Sistem ..................................................................... 20 3.3.1 Entity Relathionship Diagram (ERD) ............................. 21 3.3.2 Logical Record Structure (LRS) ..................................... 21 3.3.3 Normalisasi ..................................................................... 22 3.3.4 Kamus Data ..................................................................... 23 3.3.5 Data Flow Diagram (DFD) ............................................. 25 3.4 Analisis Algoritma Pemrograman Dinamis ............................. 27 3.5 Alur Sistem .............................................................................. 28 BAB IV HASIL DAN PEMBAHASAN ................................................. 29 4.1 Pembahasan Data ..................................................................... 29 4.2 Tampilan Sistem Informasi ...................................................... 30 4.2.1 Tampilan Antar Muka (Menu Home) ............................. 30 4.2.2 Menu ............................................................................... 31 4.3 Pengujian .................................................................................. 36 4.4 Proses Pengembangan ............................................................... 37 x

BAB V KESIMPULAN DAN SARAN ................................................... 38 5.1 Kesimpulan .............................................................................. 38 5.2 Saran ......................................................................................... 39 DAFTAR PUSTAKA ............................................................................... 40 LAMPIRAN BIODATA PENULIS

xi

DAFTAR TABEL

Tabel 2.1 Tahap 1 ....................................................................................... 12 Tabel 2.2 Tahap 2 ....................................................................................... 12 Tabel 2.3 Tahap 3 ....................................................................................... 12 Tabel 2.4 Tahap 4 ....................................................................................... 12 Tabel 2.5 Tahap 5 ....................................................................................... 12 Tabel 2.6 Tahap 6 ....................................................................................... 13 Tabel 2.7 Solusi Pendekatan Maju ............................................................ 13 Tabel 2.1 Tahap 6 ....................................................................................... 13 Tabel 2.2 Tahap 5 ....................................................................................... 13 Tabel 2.3 Tahap 4 ....................................................................................... 13 Tabel 2.4 Tahap 3 ....................................................................................... 13 Tabel 2.5 Tahap 2 ....................................................................................... 14 Tabel 2.6 Tahap 1 ....................................................................................... 14 Tabel 2.7 Solusi Pendekatan Mundur ....................................................... 14 Tabel 3.1 Normalisasi Pertama .................................................................. 22 Tabel 3.2 Normalisasi Kedua ..................................................................... 22 Tabel 3.2 Struktur Data Tabel Kasus ......................................................... 23 Tabel 3.2 Struktur Data Tabel Vertek ........................................................ 23 Tabel 3.2 Struktur Data Tabel Edge ........................................................... 24 Tabel 3.2 Struktur Data Tabel Komentar ................................................... 24 Tabel 3.2 Struktur Data Tabel Admin ........................................................ 25 Tabel 4.1 Data Jarak Antar Kota di Jawa Barat .......................................... 29

xii

DAFTAR GAMBAR

Gambar 2.1 Contoh Graf ............................................................................ 5 Gambar 2.2 (a) Graf Terhubung dan (b) Graf Tak Terhubung .................. 7 Gambar 2.3 Graf Berlabel .......................................................................... 7 Gambar 2.4 Graf dan Matriks Ketetanggaan ............................................. 8 Gambar 2.5 Graf dan Matriks Bersisian .................................................... 9 Gambar 2.6 Contoh Permasalahan Lintasan Terpendek ............................ 11 Gambar 3.1 ERD ........................................................................................ 21 Gambar 3.2 LRS ........................................................................................ 21 Gambar 3.3 DFD Level 0 ........................................................................... 25 Gambar 3.4 DFD Level 1 ........................................................................... 26 Gambar 3.5 Flowchart Sistem .................................................................... 28 Gambar 4.1 Tampilan Antar Muka ............................................................ 30 Gambar 4.2 Tahap Input pertama (Form Akun Baru) ................................ 31 Gambar 4.3 Tahap Input kedua (Form Vertek) ........................................... 32 Gambar 4.4 Tahap Input ketiga (Form Edge) ............................................ 32 Gambar 4.5 Tabel Relationship Input ........................................................ 33 Gambar 4.6 Tabel Relationship Komentar ................................................ 33 Gambar 4.7 Fitur View ................................................................................ 34 Gambar 4.8 Fitur View Data Kasus ........................................................... 35 Gambar 4.9 Fitur View Matriks ................................................................. 35 Gambar 4.10 Fitur Output ......................................................................... 36

xiii

BAB I PENDAHULUAN

1.1 Latar Belakang Graf G(V,E) adalah pasangan dua himpunan (V,E) dimana V adalah himpunan elemen-elemen tak kosong yang disebut simpul dan E adalah himpunan pasangan tak terurut yang mungkin kosong dari simpul yang disebut sisi [6]. Secara umum graf merupakan suatu diagram yang memuat informasi-informasi yang dapat diaplikasikan ke dalam kehidupan sehari-hari. Salah satu aplikasi graf yang ada dalam kehidupan sehari-hari adalah mencari lintasan terpendek antara dua buah simpul. Sebagai contoh, misalnya terdapat banyak lintasan yang menghubungkan kota asal ke kota tujuan seseorang, maka yang akan dicari adalah lintasan mana yang jaraknya paling pendek dari kota asal menuju kota tujuan. Jadi, kita dapat mengartikan lintasan terpendek adalah jarak minimal dari suatu lintasan. Dapat disimpulkan juga, permasalahan pencarian lintasan terpendek merupakan permasalahan optimasi dimana akan dicari nilai minimum dari beberapa lintasan. Banyak metode yang dapat digunakan untuk menyelesaikan permasalahan optimasi, salah satunya adalah pemrograman dinamis. Pemrograman dinamis merupakan metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan [7]. Agar permasalahan diatas dapat optimal, maka rangkaian

1

keputusan untuk menentukan solusi permasalahan tersebut haruslah optimal. Pada pemrograman dinamis, rangkaian keputusan optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas, yaitu suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan selanjutnya harus membentuk suatu kebijakan optimal yang berkaitan dengan keadaan yang dihasilkan dari keputusan awal [1]. Dengan prinsip optimalitas ini, dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya [7]. Intinya, pemrograman dinamis adalah metode penyelesaian masalah dengan memecah permasalahan menjadi subpermasalahan yang berkaitan sehingga menghasilkan solusi optimal [11]. Hasil solusi optimal ini adalah informasi yang akan digunakan sebagai penyelesaian permasalahan. Agar informasi ini dapat bermanfaat dan berguna oleh banyak orang, dibutuhkan fasilitas

yang

tepat

untuk

menyajikan

informasi

tersebut.

Sesuai

perkembangannya, teknologi internet merupakan teknologi informasi yang perkembangannya cepat saat ini. Maka dari itu, diyakini tepat untuk menyajikan informasi di internet saat ini. Maka berdasarkan latar belakang tersebut, penulis membuat skripsi dengan judul “Sistem Informasi Pencarian Lintasan Terpendek Menggunakan Pemrograman Dinamis”.

2

1.2 Perumusan Masalah Sesuai latar belakang tersebut, permasalahan yang akan dibahas pada skripsi ini yaitu mengaplikasikan teori graf pada permasalahan lintasan terpendek yang diselesaikan menggunakan metode pemrograman dinamis. Kemudian menyediakan fasilitas pencarian lintasan terpendek tersebut berbasis web.

1.3 Pembatasan Masalah Pembatasan masalah dalam skripsi ini adalah: 1. Graf yang digunakan adalah graf berhingga, graf terhubung, graf tak berarah dan graf berlabel. 2. Data yang digunakan adalah data jarak antar kota di Jawa Barat. 3. Pemrograman dinamis yang digunakan hanya pada permasalahan lintasan terpendek. 4. Keluaran yang dihasilkan hanya berupa jarak terpendeknya beserta simpulsimpul yang dilewatinya.

1.4 Tujuan Tujuan yang ingin dicapai dalam skripsi ini adalah menerapkan teori graf pada permasalahan lintasan yang diselesaikan dengan metode pemrograman dinamis. Pada skripsi ini akan disediakan sebuah fasilitas pencarian lintasan terpendek berbasis web dengan mengimplementasikan suatu bahasa pemrograman dan pengoperasian basis data.

3

1.5 Manfaat Manfaat yang ingin dicapai dalam skripsi ini adalah untuk memberikan fasilitas kepada pengguna yang ingin mencari atau menemukan lintasan terpendek sehingga mempermudah pengguna dalam mengambil keputusan untuk menuju ke suatu tempat dengan jarak yang lebih pendek dan memungkinkan dapat sampai ke tempat tujuan lebih cepat.

4

BAB II LANDASAN TEORI

2.1 Konsep Dasar Teori Graf Graf (V,E) adalah himpunan yang terdiri dari himpunan simpul V yang tak kosong dan himpunan sisi E yang mungkin kosong yang merupakan pasangan tak terurut dari dua buah simpul [6]. Elemen-elemen di himpunan simpul dinotasikan dengan V = {v1, v2, …, vn}, sedangkan elemen-elemen di himpunan sisi yang merupakan pasangan tak terurut dari elemen-elemen di himpunan simpul dinotasikan dengan E = {e1, e2, …, en}. Jika sisi e1 menghubungkan simpul v1 dengan v2 maka sisi e1 dinotasikan dengan e1=(v1,v2)=(v2,v1).

Gambar 2.1 Contoh Graf Dalam sebuah graf seperti gambar diatas, dapat dimungkinkan terdapat sisi lebih dari satu dengan sepasang simpul yang sama, contohnya e4 dan e5. Sisi-sisi dengan pasangan simpul yang sama ini disebut sisi paralel. Graf yang mengandung sisi paralel tersebut disebut graf ganda. Dalam teori graf banyak istilah-istilah dasar mengenai graf yang perlu diketahui, antara lain: 1. Ketetanggaan Dua simpul dikatakan bertetangga jika terdapat sisi yang menghubungkan kedua simpul tersebut. Misalnya e={u,v} adalah sebuah sisi dalam graf G,

5

maka dapat dikatakan simpul u bertetangga dengan simpul v karena ada sisi e yang menghubungkan simpul u dan v. Contohnya pada Gambar 2.1 yaitu v1 bertetangga dengan v2. 2. Bersisian Jika sebuah sisi menempel pada sebuah simpul sebagai titik ujungnya, maka sisi tersebut dikatakan bersisian dengan simpul tersebut demikian juga sebaliknya. Misalnya e={u,v} adalah sisi pada sebuah graf G, maka dapat dikatakan sisi e bersisian terhadap simpul u dan v. Contohnya pada Gambar 2.1 yaitu v1 besisian dengan e3 dan v2 bersisian dengan e3. 3. Derajat Derajat suatu simpul adalah jumlah sisi yang bersisian pada simpul v. Derajat tersebut dinotasikan dengan d(v). Simpul v dikatakan genap atau ganjil tergantung dari jumlah d(v) genap atau ganjil. Contohnya pada Gambar 2.1 yaitu d(v1) = 3 dan d(v2) = 4. 4. Simpul Pendan Simpul pendan adalah simpul yang memiliki derajat satu. Contohnya pada Gambar 2.1 adalah v5. 5. Jalan Jalan dari simpul u ke v dengan panjang n pada graf G adalah suatu barisan u=v0,v1,v2,v3, … vn-1,vn = v sedemikian sehingga (vi-1,vi) adalah sisi di G untuk setiap i = 1,2, … , n. Jalan dikatakan tertutup jika v0 = vn, dan dikatakan terbuka jika v0 ≠ vn.

6

6. Lintasan Lintasan adalah suatu jalan yang semua simpulnya berbeda. Contohnya pada Gambar 2.1 yaitu v1, e4, v3, e6, v4, e7, v5. 7. Trail Trail adalah suatu jalan yang sisi-sisinya hanya muncul sekali. Contohnya pada Gambar 2.1 yaitu v1, e4, v3, e6, v4, e2, v2. 8. Graf Berhingga Sebuah graf G(V,E) adalah berhingga jika V berhingga dan E berhingga. Perlu diketahui bahwa sebuah graf G dengan jumlah simpul V berhingga secara otomatis mempunyai jumlah sisi E yang berhingga. 9. Graf Terhubung Graf dikatakan terhubung jika terdapat sebuah lintasan antara sembarang dua simpulnya. Jika tidak demikian maka graf tersebut disebut graf tak terhubung.

Gambar 2.2 (a) Graf Terhubung dan (b) Graf Tak Terhubung 10. Graf Berlabel Sebuah graf dikatakan berlabel jika setiap sisinya diberikan sebuah data.

Gambar 2.3 Graf Berlabel

7

2.2 Lintasan Terpendek Dalam kehidupan sehari-hari kita pernah dihadapkan pada permasalahan untuk menentukan lintasan terpendek dari suatu tempat ke tempat lain. Sebagai contoh, misalnya terdapat banyak lintasan yang menghubungkan kota asal ke kota tujuan yang ingin dituju oleh seseorang, maka yang akan dicari adalah lintasan mana yang jaraknya paling pendek dari kota asal menuju kota tujuan. Jadi, kita dapat mengartikan lintasan terpendek sebagai jarak minimal dari beberapa lintasan. Oleh karena itu, permasalahan pencarian lintasan terpendek dalam graf merupakan salah satu permasalahan optimasi [6]. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berlabel, yaitu graf yang setiap sisinya diberikan suatu data. Data pada sisi graf dapat menyatakan jarak, waktu, ongkos dan sebagainya, sedangkan simpul pada graf menyatakan kota asal atau tujuan. Ada beberapa macam kasus pada permasalahan lintasan terpendek, yaitu: a. Lintasan terpendek antara dua buah simpul tertentu, b. Lintasan terpendek antara semua pasangan simpul, c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain, d. Lintasan terpendek antara dua buah simpul melalui beberapa simpul tertentu.

2.3 Representasi Graf dalam Matriks Matriks dapat digunakan untuk menyatakan suatu graf. Matriks ini dapat membantu untuk membuat sebuah program komputer yang berhubungan dengan graf. Dengan menyatakan graf menjadi sebuah matriks, maka perhitunganperhitungan yang diperlukan dalam komputer jadi lebih mudah dilakukan [9]. 8

Misalkan G adalah sebuah graf dengan simpul-simpul v1, v2, v3, … , vm dan sisi-sisinya e1, e2, e3, … , en. 1. Matriks Ketetanggaan Matriks ketetanggaan didefinisikan sebagai berikut, misalkan A = (aij) adalah matriks m × m yang didefinisikan oleh,

Maka A disebut matriks ketetanggaan dari G. Perhatikan aij = aji , sehingga A adalah sebuah matiks simetris.

Gambar 2.4 Contoh Graf dan Matriks Ketetanggaan 2. Matriks Bersisian Matriks bersisian didefinisikan sebagai berikut, misalkan B = (bij) adalah matriks m × n yang didefinisikan oleh,

Maka B disebut matriks bersisian dari G.

Gambar 2.5 Contoh Graf dan Matriks Bersisian

9

2.4 Pemrograman Dinamis Pemrograman Dinamis adalah metode pemecahan masalah dengan cara menguraikan masalah menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan [7]. Pada pemrograman dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas yaitu, suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan selanjutnya harus membentuk suatu kebijakan optimal yang berkaitan dengan keadaan yang dihasilkan dari keputusan awal [1]. Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya [7]. Ada dua pendekatan dalam penyelesaian masalah dengan pemrograman dinamis yaitu maju dan mundur. Misalkan x1, x2, …, xn menyatakan peubah keputusan yang harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka [7], 1. Pendekatan Maju Pemrograman dinamis maju bekerja mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah x1, x2, …,xn. 2. Pendekatan Mundur Pemrograman dinamis mundur bekerja mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan adalah xn, xn-1, …, x1.

10

Contoh penerapan pemrograman dinamis pada permasalahan lintasan terpendek, tentukan lintasan terpendek dari Jakarta ke Tasikmalaya dari Gambar 2.6. 1

2

Bekasi

3

4

5

6

24 41 80

Jakarta

Karawang

Purwakarta

41

60

Sumedang 50

86

Bandung

Tasikmalaya

24

Depok

61

95

68

49

32

54 65

Sukabumi

Cianjur

Garut

Bogor

Gambar 2.6 Contoh Permasalahan Lintasan Terpendek Misalkan x1, x2, .., x6 = xk adalah simpul-simpul yang dikunjungi pada tahap k (k = 1, 2, 3, 4, 5, 6) dengan k adalah banyaknya tahap. Berikut adalah rumusan pemrograman dinamis pada permasalahan lintasan terpendek ini [7]: 1. Pendekatan Maju fk(s) = fk(s) =

{fk(xk ,s)}, dengan fk(xk , s) =

+ fk-1(xk)

2. Pendekatan Mundur fk(s) = fk(s) =

{fk(s, xk)} , dengan fk(s, xk) =

+ fk+1(xk)

Keterangan: s

: simpul-simpul pada setiap tahap disebut status. : label sisi dari s ke xk.

fk(s, xk) : total label lintasan dari s ke xk. fk(s)

: nilai minimum dari fk(s, xk). 11

Maka penyelesaian masalah pada contoh diatas adalah sebagai berikut: 1. Penyelesaian Dengan Pendekatan Maju a. Tahap 1 : f1(s) = Tabel 2.1 Tahap 1 Solusi Optimum s f1(s) x1* Bekasi 41 Jakarta Depok 24 Jakarta Bogor 54 Jakarta b. Tahap 2 : f2(s) =

{

+ f1(x2)}

Tabel 2.2 Tahap 2 x2 f2(x2 , s) = + f1(x2) Solusi Optimum s Bekasi Depok Bogor f2(s) x2* Karawang 65 104 149 65 Bekasi Sukabumi 119 119 Bogor c. Tahap 3 : f3(s) =

{

+ f2(x3)}

Tabel 2.3 Tahap 3 f3(x3 , s) = + f2(x3) Solusi Optimum s Karawang Sukabumi f3(s) x3* Purwakarta 106 106 Karawang Cianjur 151 151 Sukabumi x3

d. Tahap 4 : f4(s) = x4 s Bandung e. Tahap 5 : f5(s) =

x5 s Sumedang Garut

{

+ f3(x4)}

Tabel 2.4 Tahap 4 f4(x4 , s) = + f3(x4) Solusi Optimum Purwakarta Cianjur f4(s) x4* 166 212 166 Purwakarta {

+ f4(x5)}

Tabel 2.5 Tahap 5 f5(x5 , s) = + f4(x5) Bandung 216 234

Solusi Optimum f5(s) x5* 216 Bandung 234 Bandung 12

f. Tahap 6 : f6(s) = x5 s Tasikmalaya

{

+ f5(x6)}

Tabel 2.6 Tahap 6 f5(x6 , s) = + f5(x6) Sumedang Garut 302 283

Solusi Optimum f5(s) x6* 283 Garut

Solusi optimum dapat dibaca pada tabel di bawah ini: Tabel 2.7 Solusi Pendekatan Maju x1

x2

x3

x4

x5

x6

N

Jakarta Bekasi Karawang Purwakarta Bandung Garut Tasikmalaya

Jumlah Label 283

2. Penyelesaian Dengan Pendekatan Mundur a. Tahap 6 : f6(s) = Tabel 2.8 Tahap 6 Solusi Optimum s f6(s) x6* Sumedang 86 Tasikmalaya Garut 49 Tasikmalaya b. Tahap 5 : f5(s) = x5 s Bandung c. Tahap 4 : f4(s) =

{

+ f6 (x5)}

Tabel 2.9 Tahap 5 f5(s,x5) = + f6 (x5) Solusi Optimum Sumedang Garut f5(s) x5* 136 117 117 Garut {

+ f5 (x4)}

Tabel 2.10 Tahap 4 x4 f4(s,x4) = + f5 (x4) s Bandung Purwakarta 177 Cianjur 178 d. Tahap 3 : f3(s) = x3 s Karawang Sukabumi

{

Solusi Optimum f4(s) x4* 177 Bandung 178 Bandung

+ f4 (x3)}

Tabel 2.11 Tahap 3 f3(s,x3) = + f4 (x3) Purwakarta Cianjur 218 210

Solusi Optimum f3(s) x3* 218 Purwakarta 210 Cianjur

13

e. Tahap 2 : f2(s) =

+ f3 (x2)}

{

Tabel 2.12 Tahap 2 f2(s,x2) = + f3 (x2) Karawang Sukabumi 242 298 313 275

x2 s Bekasi Depok Bogor f. Tahap 1 : f1(s) =

Solusi Optimum f2(s) x2* 242 Karawang 298 Karawang 275 Sukabumi

+ f2 (x1)}

{

Tabel 2.13 Tahap 1 f1(s,x1) = + f2 (x1) Solusi Optimum Bekasi Depok Bogor f1(s) x1* 283 322 329 283 Bekasi

x1 s Jakarta

Solusi optimum dapat dibaca pada tabel di bawah ini: Tabel 2.14 Solusi Pendekatan Mundur 1

x1

x2

x3

x4

x5

x6

Jakarta Bekasi Karawang Purwakarta Bandung Garut Tasikmalaya

Jumlah Label 283

Dapat dilihat hasil penyelesaian dari pendekatan maju dan mundur pada Tabel 2.7 dan Tabel 2.14 menghasilkan hasil yang sama. Maka disimpulkan jarak terpendek dari Jakarta ke Tasikmalaya dengan menggunakan metode pemrograman dinamis adalah 283. Sedangkan kota-kota yang dilewatinya yaitu, Jakarta Karawang

Purwakarta

Bandung

Garut

Bekasi

Tasikmalaya.

2.5 Algoritma Pemrograman Dinamis Agoritma adalah tahap-tahap well-define (jelas) yang dibutuhkan untuk menyelesaikan pekerjaan. Algoritma ditulis dalam tata caranya sendiri yang disebut PSEUDOCODE. Setiap algoritma memiliki kompleksitasnya masingmasing. Kompleksitas algoritma adalah suatu ukuran dari banyaknya perhitungan

14

yang dilakukan. Dengan komplesitas ini dapat diketahui sebuah algoritma apakah efisien atau tidak. Dibawah ini adalah algoritma pemrograman dinamis untuk menyelesaikan permasalah lintasan terpendek dengan menggunakan pendekatan maju. for (k=1 n,k++) for (i=1 n,i++) for (j=1 n,j++) A(i,j) = min{A(i,j) , A(i,k) + A(k,j)} end end end

2.6 Basis Data Data adalah fakta mengenai objek, orang, dan lain-lain. Sedangkan informasi adalah hasil analisis dan sintesis terhadap data. Basis data adalah kumpulan data sistematis yang digunakan untuk menyimpan informasi atau data [10]. Data akan disimpan dalam tabel-tabel yang ada pada basis data. Tabel-tabel tersebut terdiri dari baris dan kolom yang didalamnya terdapat nama kolom (field) dan isi kolomnya (record) [8]. Untuk mengelola data pada basis data diperlukan suatu perangkat lunak yang disebut Database Management System (DBMS). DBMS merupakan suatu sistem perangkat lunak yang memungkinkan pengguna untuk membuat, memelihara, mengontrol dan mengakses basis data secara praktis dan mudah.

15

Contoh DBMS adalah Relationship Database Management System (RDBMS) yang merupakan salah satu jenis DBMS yang mendukung adanya hubungan antar tabel [8]. Beberapa perangkat lunak DBMS yang sering digunakan yaitu Oracle, MySQL, SQL Server dan lain-lain. Keuntungan yang dapat diperoleh dari penerapan DBMS, yaitu: 1. Kebebasan data dan akses data yang efisien. 2. Pengembangan aplikasi yang cepat. 3. Integritas dan keamanan data. 4. Administrasi keseragaman data. 5. Akses bersamaan dan perbaikan dari terjadinya tabrakan dari proses serentak. Data dalam DBMS dapat digambarkan dalam tiga level abstraksi, yaitu: 1. Konseptual, adalah skema yang mendefinisikan struktur logika. 2. Fisik, adalah skema yang menggambarkan file dan indeks yang digunakan. 3. Eksternal adalah skema yang menggambarkan cara user dalam melihat data. Skema-skema tersebut dapat didefinisikan menggunakan DDL dan dimodifikasi dengan menggunakan DML. Data Definition Language (DDL) adalah skema basis data dengan menggunakan perintah SQL yang berhubungan dengan pendefinisian suatu struktur basis data dan tabel. Perintah DDL diantaranya: 1. CREATE, digunakan untuk membuat database atau tabel baru. 2. ALTER, digunakan untuk merubah, menambah,dan menghapus tabel. 3. DROP, digunakan untuk menghapus database.

16

Data Manipulation Language (DML) adalah skema basis data dengan menggunakan perintah SQL yang berhubungan dengan manipulasi atau pengolahan data dalam tabel. Perintah DML antara lain: 1. SELECT, perintah untuk memilih data pada tabel. 2. INSERT, perintah untuk menambahkan data baru pada tabel. 3. UPDATE, perintah untuk merubah data pada tabel. 4. DELETE, perintah untuk menghapus data pada tabel.

2.7 Normalisasi Normalisasi merupakan suatu teknik yang menstrukturkan data untuk membantu mengurangi atau mencegah timbulnya masalah pada pengolahan data dalam basis data dan untuk memperolah logical design yang valid sehingga mampu menghindari duplikasi data dan menghasilkan struktur data yang baik serta mudah dimengerti. Aturan-aturan normalisasi dinyatakan dalam istilah bentuk normal. Bentuk normal adalah suatu aturan yang dikenakan pada relasi-relasi dalam basis data dan harus dipenuhi oleh relasi-relasi tersebut pada level-level normalisasi. Berikut urutan aturan normalisasi. 1. Bentuk Normal Pertama (1st NF) Pada bentuk normal pertama ini, data dibentuk dari satu record demi satu record dan nilai dari setiap field-nya berupa atomic value, serta masih adanya perulangan dari atribut-atributnya.

17

2. Bentuk Normal Kedua (2nd NF) Dalam bentuk normal kedua, bentuk normal pertama harus sudah dipenuhi dan semua atribut bukan kunci hanya bergantung pada primary key.

2.8 Entity Relationship Diagram (ERD) ERD merupakan suatu pemodelan data berisi kumpulan entitas dan relasi. Entitas adalah objek yang dapat dibedakan dengan objek lain berdasarkan atributatributnya. Relasi adalah hubungan alamiah yang terjadi antara satu atau lebih entitas. ERD dapat merepresentasikan seluruh fakta dari penggambarannya yang sistematis sehingga memberikan kefleksibelan dalam mendesain skema basis data.

2.9 MySQL MySQL merupakan Database Management System (DBMS) tools open source yang mendukung multiuser, multithreaded [4]. MySQL dimiliki dan disponsori oleh sebuah perusahaan komersial asal Swedia yaitu MySQL AB, dimana perusahaan tersebut memegang seluruh hak cipta atas kode sumbernya. Beberapa kelebihan menggunakan DBMS seperti MySQL diantaranya: 1. Free (Bebas diunduh). 2. Fleksibel dengan berbagai pemrograman. 3. Stabil dan memberi kemudahan manajemen basis data. 4. Mudah dipelajari.

18

2.10 Hypertext Preprocessor (PHP) PHP adalah bahasa pemorgraman yang memungkinkan para web developer untuk membuat dan mengembangkan aplikasi web yang dinamis dengan cepat [10]. PHP ditulis dan diperkenalkan pertama kali oleh Rasmus Lerdorf pada 1994. PHP merupakan salah satu bahasa script yang tersedia secara bebas dan masih memungkinkan untuk dikembangkan lebih lanjut. Karakteristik yang paling unggul dan paling kuat dalam PHP adalah lapisan integrasi basis data. Basis data yang didukung PHP diantaranya Oracle, MySQL, dBase, ODBC, Unix dbm, PostgreSQL, dan lain-lain.

19

BAB III METODOLOGI PERANCANGAN SISTEM

3.1 Metode Pengumpulan Data Graf yang digunkan untuk menerapkan sistem informasi ini adalah berupa data dengan simpulnya adalah kota-kota dan sisinya adalah nama-nama jalan yang menghubungkan antar kota dengan label setiap sisinya adalah jarak antar kota tersebut. Data yang coba digunkan adalah data jarak antar kota di Jawa Barat. Data tersebut dapat diperoleh dari hasil pencarian di google map.

3.2 Metode Pengolahan Data Dalam sistem informasi ini, data diolah dengan menggunakan bahasa pemrograman PHP (Hypertext Preprocessor) Version 5.2.5 dan bahasa pengoperasian

basis

data

MySQL

Version

5.0.51

yang

disimulasikan

menggunakan tools XAMPP.

3.3 Rancangan Sistem 3.3.1 Entity Relationship Diagram (ERD) ERD merupakan suatu permodelan data utama yang akan membantu mengorganisasikan data dalam suatu proyek ke dalam entitas-entitas dan menentukan hubungan antar entitas tersebut. Berikut adalah gambar ERD pada sistem informasi ini.

20

kontak

no_sisi

id_sisi

password

nm_sisi

jml_kasus

agama

nm_lengkap

alamat

nm_admin bobot

asal

Sisi

Admin

pekerjaan

id_admin kode_kasus

tuju email

berhubungan

terdapat

kontrol

kontrol kode_kasus

nm_simpul

Simpul

terdapat

memuat

Kasus

Komentar id_komen

no_simpul komentator id_simpul

kode_kasus

nama_kasus

pass_kasus

komentar

tanggal

nama_pembuat

kode_kasus

Gambar 3.1 ERD 3.3.2 Logical Record Structure (LRS) Komentar

Simpul no_simpul id_simpul nm_simpul kode_kasus

Sisi no_sisi id_sisi nm_sisi asal tuju bobot kode_kasus

Kasus kode_kasus nm_pembuat nm_kasus pass_kasus tanggal kode_kasus

id_komen kode_kasus komentator komentar

no_edge
Admin id_admin nm_admin password jml_kasus nm_lengkap alamat agama pekerjaan kontak email

Gambar 3.2 LRS

21

3.3.3 Normalisasi Pada pembuatan basis data di sistem informasi ini, dilakukan normalisasi sampai ke tahap 2. Berikut normalisasi tabelnya: Tabel 3.1 Normalisasi Pertama Kasus

Simpul

kode_kasus nm_pembuat nm_kasus pass_kasus tanggal

id_simpul nm_simpul kode_kasus

kode_kasus Komentar

no_verte Sisi k


no_edge

id_sisi nm_sisi asal tuju bobot kode_kasus

Admin id_admin nm_admin password nm_lengkap alamat agama pekerjaan kontak jml_kasus email kode_kasus

no_edge

Tabel 3.2 Normalisasi Kedua Kasus

Simpul

kode_kasus nm_pembuat nm_kasus pass_kasus tanggal

no_simpul id_ simpul nm_ simpul kode_kasus

kode_kasus

no_verte k Sisi

Komentar


no_edge

no_sisi id_sisi nm_sisi asal tuju bobot kode_kasus no_edge

Admin id_admin nm_admin password nm_lengkap alamat agama pekerjaan kontak jml_kasus email kode_kasus

22

3.3.4 Kamus Data Kamus data merupkan suatu penjabaran atau pendeskripsian strukturstruktur atribut secara jelas dalam suatu proyek dari setiap entitas-entitas yang ada. Berikut ini adalah tabel-tabel kamus data yang digunakan pada sistem informasi ini. a) Tabel Kasus Nama Tabel

: kasus

Deskripsi

: tempat penyimpanan data registrasi

Primery key

: kode_kasus

Foreign key

: Tabel 3.3 Struktur Data Tabel Kasus

Field kode_kasus nm_pembuat nm_kasus pass_kasus tanggal

Type Varchar Varchar Varchar Varchar Date

Size 10 50 100 32

Keterangan Kode kasus Nama pembuat Nama kasus Password kasus Tanggal pembuatan kasus

b) Tabel Simpul Nama Tabel

: simpul

Deskripsi

: tempat penyimpanan data input simpul

Primery key

: no_simpul

Foreign key

: kode_kasus, id_simpul Tabel 3.4 Struktur Data Tabel Simpul

Field no_simpul id_simpul nm_simpul kode_kasus

Type Int Int Varchar Varchar

Size auto_increment 11 50 10

Keterangan No simpul Identitas simpul Nama simpul Kode kasus

23

c) Tabel Sisi Nama Tabel

: sisi

Deskripsi

: tempat penyimpanan data input sisi

Primery key

: no_sisi

Foreign key

: kode_kasus, asal, dan tuju Tabel 3.5 Struktur Data Tabel Sisi

Field no_sisi id_sisi nm_sisi asal tuju bobot kode_kasus

Type Int Int Varchar Int Int Int Varchar

Size auto_increment 11 100 11 11 11 10

Keterangan No sisi Identitas sisi Nama sisi Identitas simpul asal Identitas simpul tujuan Bobot Kode kasus

d) Tabel Komen Nama Tabel

: komen

Deskripsi

: tempat penyimpanan komentar setiap kasus

Primery key

: id_komen

Foreign key

: kode_kasus Tabel 3.6 Struktur Data Tabel Komen

Field id_komen kode_kasus komentator komentar

Type Int Varchar Varchar Varchar

Size auto_increment 10 30 500

Keterangan Identitas setiap komentar Kode kasus Nama pengomentar Isi komentar

e) Tabel Admin Nama Tabel

: admin

Deskripsi

: pengontrol sistem informasi

Primery key

: id_admin

Foreign key

: jml_kasus, nm_admin

24

Tabel 3.7 Struktur Data Tabel Admin Field id_admin nm_admin password nm_lengkap jml_kasus alamat pekerjaan agama kontak email

Type Varchar Varchar Varchar Varchar Int Varchar Vvarchar Varchar Varchar Varchar

Size 10 20 32 50 11 200 50 10 20 30

Keterangan Identitas Admin Nama panggilan Admin Password Admin Nama Lengkap Admin Jumlah Keseluruhan Kasus Alamat Admin Pekerjaan Admin Agama Admin Kontak Personal Admin Email Admin

3.3.5 Data Flow Diagram (DFD) Data Flow Diagram merupakan suatu diagram yang menggambarkan aliran data dan semua prosesnya dalam suatu sistem. Dibawah ini adalah DFD dari sistem informasi yang dibuat. 1. DFD Level 0

Gambar 3.3 DFD Level 0 Penjelasan Gambar 3.2 : a. Proses Nama proses : Sisitem Informasi Pencarian Lintasan Terpendek Menggunakan Pemrograman Dinamis

25

b. Arus Data Masukkan : login, registrasi, input data, edit data, hapus data, hapus kasus,dan komentar Keluaran : daftar kasus, view data kasus, solusi, komentar. c. Entitas Luar : Admin, Umum 2. DFD Level 1 profile admin, display data

kasus

data registrasi display data

registrasi, password dispay data

simpul

sisi

3.0* Manajemen sisi

data input

Input komentar display data

Umum

2.0* Manajemen simpul

data Input display data

display data

komentar

Admin

login

1.0* Manajemen pengguna

4.0* Manajemen komentar

display data, hapus data, komentar hapus data, komentar

Input komentar display data, ubah data, hapus data

Admin

Umum

Gambar 3.4 DFD Level 1 Penjelasan Gambar 3.4 : a. Proses 1.0* Ringkasan prosesnya yaitu, pengguna (umum) dapat masuk ke sistem ini dan dapat membuat akun serta dapat melihat semua data yang ada. Sedangkan admin dengan login terlebih dahulu dan dapat melihat semua data.

26

b. Proses 2.0* Ringkasan prosesnya yaitu, setelah membuat akun pengguna (umum) dapat memasukkan data simpul dengan cara input secara manual. c. Proses 3.0* Ringkasan prosesnya yaitu, setelah memasukkan data simpul, pengguna (umum) selanjutnya memasukkan data sisi dengan cara input secara manual. d. Proses 4.0* Ringkasan prosesnya yaitu, setelah registrasi selesai, pengguna dapat melihat data yang sudah dimasukkan. Dan dapat memberikan komentar terhadap kasus yang dibuat. Jika ada komentar yang masuk, maka admin dapat membalas komentar tersebut.

3.4 Analisis Algoritma Pemrograman Dinamis for (k=1 n,k++)

n+1

for (i=1 n,i++) for (j=1 n,j++)

(n+1).n ((n+1).n).n

A(i,j) = min{A(i,j) , A(i,k) + A(k,j)} end end end

+ n3 + 2n2 + 2n + 1 Didapat kompleksitas algoritma pemrograman dinamis adalah Order n3

(O(n3)) artinya ketika permasalahan membesar banyaknya operasi yang dilakukan

27

akan bertambah lebih besar. Maka dapat disimpulakan algoritma pemrograman dinamis kurang efisien penggunaanya saat permasalahan besar.

3.5 Alur Sistem Untuk memudahkan membuat sistem maka dibuat alur sistem yang menunjukkan proses sistem dari awal sampai mendapatkan kesimpulan. Alur dari sistem informasi dapat dilihat pada gambar flowchart dibawah ini. Start

Tema

Design

Membuat ERD, LRS, Kamus Data dan DFD

Pengambilan Data

Input Data

Pemilihan Data

Tidak

Pemrograman Dinamis

Ya Hasil

Kesimpulan

End

Gambar 3.5 Flowchart Sistem

28

BAB IV HASIL DAN PEMBAHASAN

4.1 Pembahasan Data Data yang didapat dari google map [5], diurutkan berdasarkan asal dan tujuannya. Data yang dambil adalah data jalan besar yang umum dilalui saja dari beberapa kota besar di Jawa Barat. Berikut data-datanya, dapat dilihat pada Tabel 4.1 dibawah ini. Tabel 4.1 Data Jarak Antar Beberapa Kota Di Jawa Barat No Kota Asal 1 Jakarta 2 Jakarta 3 Jakarta

Kota Tujuan Bekasi Depok Bogor

4

Bekasi

Karawang

5

Depok

Karawang

6

Bogor

Sukabumi

7

Bogor

Karawang

8 9 10

Karawang Sukabumi Purwakarta

Purwakarta Cianjur Bandung

11

Cianjur

Bandung

12 13 14 15

Bandung Bandung Sumedang Garut

Sumedang Garut Tasikmalaya Tasikmalaya

Nama Jalan Tol Jakarta - Cikampek Jalan Margonda Jalan Citayam Jalan Raya Rengas Lemahabang Tol Lingkar Luar TMII Cikunir dan Tol Jakarta – Cikampek Jalan Raya Sukabumi Jalan Jendral S. Parman dan Tol Jakarta - Cikampek Jalan Raya Curug Jalan Sukabumi - Cianjur Tol Cipularang Jalan Raya Bandung dan Jalan Raya Raja Mandala Jalan Raya Jatinangor Jalan Cicalengka - Nagrek Jalan Malangbong - Ciawi Jalan Garut – Tasikmalaya

29

Jarak(km) 41 24 54 24 80 65 95 41 32 60 61 50 68 86 49

4.2 Tampilan Sistem Informsi 4.2.1 Tampilan Antar Muka (Menu Home) Gambar 4.2 adalah tampilan awal saat pertama kali sistem informasi ini dibuka. Pada tampilan awal ini, terdapat dua fitur utama yaitu menu home dan menu sistem informasi. Pada memu home dijelaskan tentang pendahuluan sistem informasi ini dibuat dengan tujuan mempermudah pengguna dalam mencari lintasan terpendek. Sistem informasi ini dapat membantu menyelesaikan permasalahan lintasan terpendek sesuai penggunanya dan dapat menggunakan permasalahan dari pengguna yang lain jika tidak menggunakan password. Menariknya,

disini

memungkin

pengguna

dapat

menyelesaikan

permasalahan sendiri dengan input data sendiri atau dengan data yang sudah ada dalam basis data sistem informasi ini. Jika ada yang berminat untuk mengetahui bagaimana cara pembuatanya bisa menghubungi kontak yang juga diberikan pada tampilan antar muka ini.

Gambar 4.1 Tampilan Antar Muka (menu home) 30

4.2.2 Menu Didalam menu sistem informasi ini terdapat dua buah fitur yaitu input dan view. Fitur input digunakan untuk membuat akun baru dengan kasus yang baru pula dengan memasukkan nama pembuat kasus dan nama kasusnya dengan atau tanpa password. Selanjutnya, setelah akun selesai dibuat kemudian masukkan data-data simpul dan sisinya. Maka tahap input akan selesai dilakukan. Berikut gambar tahap input pada sistem informasi ini.

Gambar 4.2 Tahap Input pertama (Form Akun Baru)

31

Gambar 4.3 Tahap Input kedua (Form Simpul)

Gambar 4.4 Tahap Input ketiga (Form Sisi)

32

Setiap data yang akan dimasukkan, data tersebut akan masuk ke dalam basis data sistem informasi ke dalam tabel yang berbeda-beda sesuai dengan tabelnya masing-masing. Data akun baru akan masuk ke dalam tabel kasus, sedangkan data simpul akan masuk ke dalam tabel simpul dan terakhir data sisi akan masuk ke dalam tabel sisi. Tabel-tabel tersebut merupakan tabel-tabel yang saling berhubungan. Untuk memperjelas hubungan ketiga tabel tersebut, berikut adalah gambar dari hubungan ketiganya. Kasus

Simpul

memiliki

memiliki

terdapat

Sisi

Gambar 4.5 Tabel Relationship Input Fitur view merupakan fitur untuk melihat daftar-daftar kasus yang sudah dimasukkan kedalam basis data sistem informasi ini sehingga semua kasus yang sudah masuk dapat ditampilkan dan digunakan untuk mencari lintasan terpendek. Kemudian pada setiap kasus diberikan fitur komentar untuk memberikan komentar pada setiap kasusnya. Setiap komentar yang masuk akan masuk ke dalam basis data dengan tabel yang bernama komentar. Berikut adalah tabel hubungan antara kasus dan komentar. Kasus

memiliki

Komentar

Gambar 4.6 Tabel Relationship Komentar

33

Dalam fitur view juga terdapat fitur searching yang dapat membantu untuk mencari kasus sesuai dengan keinginan (jika ada). Dibawah ini adalah tampilan gambar dari fitur view.

Gambar 4.7 Fitur View Kemudian dari fitur view ini, kita dapat melihat data yang sudah ada dalam basis data. Data seperti nama kasus, nama-nama simpul, dan nama-nama sisi beserta bobotnya akan tampil setelah mengklik salah satu kasus yang ada pada daftar fitur view ini. Didalamnya akan terdapat fitur seperti fitur matriks yang akan memberikan gambaran tentang hubungan antara kedua simpul yang salaing berhubungan atau bertetangga. Kemudian fitur selanjutnya adalah fitur utama dalam sistem informasi ini, yaitu tentu saja fitur

output untuk memperoses pencarian lintasan terpendek

dengan memilih titik asal dan tujuan yang ingin dicari lintasan terpendeknya. Dan dibawah ini adalah gambar fitur hasil dari fitur view.

34

Gambar 4.8 Fitur viewdata kasus

Gambar 4.9 Fitur Matriks

35

4.3 Pengujian Pada bab sebelumnya sudah dibahas pencarian lintasan terpendak dari Jakarta ke Tasikmalaya dengan perhitungan secara manual dan lintasan terpendeknya adalah 283 km. Sekarang sistem informasi ini akan coba di uji apakah dapat memberikan hasil yang sama dengan perhitungan secara manualnya. Dari data yang sama yaitu pada Tabel 4.1 akan dicari lintasan terpendek dari Jakarta ke Tasikmalaya. Dibawah adalah gambar dari hasil pencariannya.

Gambar 4.10 Fitur Output

36

Dapat dilihat hasilnya bahwa lintasan terpendek dari Jakarta ke Tasikmalaya adalah 283 km dan kota-kota yang dilewatinya yaitu Jakarta Bekasi

Karawang

Purwakarta

Bandung

Garut

Tasikmalaya.

Kesimpulannya hasil perhitungan dari sistem informasi ini dengan menggunakan pemrograman dinamis pada pencarian lintasan terpendek dari Jakarta ke tasikmalaya akan memberikan hasil yang sama dengan hasil secara manual.

4.4 Proses Pengembangan Pada sistem informasi ini belum semua fitur dapat berjalan dengan baik, terdapat fitur yang masih dalam tahap pengembangan. Pada fitur input yang masih dalam tahap pengembangan adalah fitur Import yang akan menginputkan data dari Microsoft Excel ke dalam basis data sistem informasi. Fitur tersebut belum selesai dibuat atau masih dalam pengembangan dikarenakan keterbatasan waktu dalam pembuatan sistem informasi ini. Sistem informasi ini terbuka untuk pengembangan lebih lanjut dalam penelitian selanjutnya.

37

BAB V KESIMPULAN DAN SARAN

5.1 Kesimpulan Aplikasi graf pada permasalahan lintasan terpendek dapat diselesaikan menggunakan metode pemrograman dinamis dan dapat diimplementasikan dengan suatu bahasa pemrograman dan basis data sehingga menghasilkan sebuah sistem informasi pencarian lintasan terpendek yang dapat mempermudah dalam pengambilan keputusan untuk setiap permasalahan pencarian lintasan terpendek. Sistem informasi ini dapat digunakan oleh siapa saja yang dapat memberikan kemudahan pada setiap pengguna dalam mencari lintasan terpendek yang ingin dituju oleh setiap penggunanya.

5.2 Saran Sistem informasi ini masih belum sempurna karena keterbatasan waktu penulis sehingga membatasi masalah dalam pembuatan sistem informasi ini. Sistem informasi ini dibuat hanya sebatas membuat fitur yang dibutuhkan dalam pencarian lintasan terpendek dengan menggunakan pemrograman dinamis. Saran dari penulis agar sistem informasi ini dapat lebih disempurnakan lagi yaitu dengan: 1. Agar hasil lebih akurat, gunakan graf berarah dalam permasalahan lintasan terpendek karena ada kemungkinan jarak suatu jalan dari A ke B tidak selalu sama dengan jarak dari B ke A.

38

2. Gunakan pula data yang lebih akurat untuk memperoleh hasil yang lebih akurat. 3. Agar sistem informasi lebih menarik dan terlihat jelas, dengan menampilkan graf atau diagram pada setiap permasalahan lintasan terpendeknya. 4. Sistem informasi pencarian lintasan terpendek ini dapat dimodifikasi menjadi pencarian lintasan tercepat atau termurah dengan ditambahkan parameterparameter pendukungnya. Atau dengan penggabungan dari dua atau bahkan tiga pencarian maka akan menghasilkan sebuah sistem informasi pencarian lintasan yang lebih sempurna.

39

BIODATA PENULIS

DAFTAR RIWAYAT HIDUP Data Pribadi Nama Lengkap

: Marsa Gerdiyandanu Nilanto

NIM

: 107094003005

Tempat Tanggal Lahir

: Jakarta, 04 Juli 1989

Alamat

: Jl. Nirmala V Cipondoh Makmur Blok P.I/9 Rt.06/07 CIPONDOH TANGERANG 15148

Phone / Hand Phone

: 02156108788 / 08568722654

Email

: [email protected] / [email protected]

Jenis Kelamin

: laki-laki

Riwayat Pendidikan 1. S1

: Program Studi Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri (UIN) Syarif Hidayatullah Jakarta, Tahun 2007 - 2011

2. SMA

: SMAN 84 Kalideres Jakarta Barat, Tahun 2004 - 2007

3. SMP

: SMPN 204 Pegadungan Jakarta Barat, Tahun 2001 - 2004

4. SD

: SDN 08 pagi Kalideres,Tahun 1995 - 2001

5. TK

: Al - Fathir Cipondoh Tangerang, Tahun 1993 - 1995

DAFTAR PUSTAKA

[1]

Dynamic Programming : Universitas Oxford. pada tanggal 27 Mei 2011 pukul 10.05 WIB. http://www.oxfordmphil.com/images/c/.../Dynamic-programming-4-principle.pdf.

[2]

Gunawan. Ellen dan A. Wirda Mulya, “Pengantar Riset Operasi Jilid 1”. Edisi Kelima, Erlangga, 1990.

[3]

Hakim. Lukmanul, “Membongkar Trik Rahasia Para Master PHP” Lokomedia, 2008.

[4]

Kristanto. Andri, “Kupas Tuntas PHP & MySQL”. Klaten: Cable Book, 2010.

[5]

Mencari Data Jarak Antar Kota Di Jawa Barat, pada tanggal 29 April 2011 pukul 14.10 WIB, http://map.google.co.id.

[5]6

Munir. Rinaldi, “Matematika Diskrit”. Bandung: Informatika, 2007.

[6]7

Munir. Rinaldi, “Diktat Kuliah IF2251 Program Dinamis (Bagian 1)”. Bandung: Informatika ITB.

[7]8

Puspitosari. Heni, “Pemrograman Web Database dengan PHP MySQL”. Skripta. 2011.

[8]9

Siang. Jong Jek, “Matematika Diskrit dan Aplikasinya pada Ilmu Komputer”, Edisi keempat. Yogyakarta: ANDI, 2009.

[9]10 Simarmata. Janner, “Basis Data”, Edisi kesatu. Yogyakarta: ANDI, 2006. [10]11 Subagyo. Pangestu, Marwan Asri dan T. Hani Handoko. “Dasar-Dasar Operations Research”. Edisi kedua, PTBPFE: Yogyakarta.

40

LAMPIRAN

1. Data Definition Language (DDL): 1. Membuat Database CREATE DATABASE `lintasan` ; 2. Membuat Tabel Kasus CREATE TABLE `lintasan`.`kasus` ( `kode_kasus` VARCHAR( 10 ) NOT NULL , `nm_pembuat` VARCHAR( 50 ) NOT NULL , `nm_kasus` VARCHAR( 100 ) NOT NULL , `pass` VARCHAR( 32 ) NOT NULL , `tanggal` DATE NOT NULL , PRIMARY KEY ( `kode_kasus` ) ) 3. Membuat Tabel Simpul CREATE TABLE `lintasan`.`simpul` ( `no_simpul` INT NOT NULL AUTO_INCREMENT , ìd_simpul` INT NOT NULL , `nm_simpul` VARCHAR( 50 ) NOT NULL , `kode_kasus` VARCHAR( 10 ) NOT NULL , PRIMARY KEY ( `no_simpul` )) 4. Membuat Tabel Sisi CREATE TABLE `lintasan`.`sisi` ( `no_sisi` INT NOT NULL AUTO_INCREMENT ,

41

ìd_sisi` INT NOT NULL , `nm_sisi` VARCHAR( 50 ) NOT NULL , àsal` INT NOT NULL , `tuju` INT NOT NULL , `bobot` INT NOT NULL , `kode_kasus` VARCHAR( 10 ) NOT NULL , PRIMARY KEY ( `no_sisi` ) ) 5. Membuat Tabel Komentar CREATE TABLE `lintasan`.`komentar` ( ìd_komen` INT( 11 ) NOT NULL , `kode_kasus` VARCHAR( 10 ) NOT NULL , `komentator` VARCHAR( 50 ) NOT NULL , `komentar` VARCHAR( 200 ) NOT NULL , PRIMARY KEY ( ìd_komen` ) ) 6. Membuat Tabel Admin CREATE TABLE `lintasan`.àdmin` ( ìd_admin` VARCHAR( 10 ) NOT NULL , `nm_admin` VARCHAR( 20 ) NOT NULL , `password` VARCHAR( 32 ) NOT NULL , `nm_lengkap` VARCHAR( 50 ) NOT NULL , `jml_kasus` INT( 11 ) NOT NULL , àlamat` VARCHAR( 200 ) NOT NULL , `pekerjaan` VARCHAR( 50 ) NOT NULL ,

42

àgama` VARCHAR( 10 ) NOT NULL , `kontak` VARCHAR( 20 ) NOT NULL , èmail` VARCHAR( 30 ) NOT NULL , PRIMARY KEY ( ìd_admin` ) )

2. Data Manipulation Languange (DML) 1. Registrasi "INSERT INTO ssp VALUES('$kode','$_POST[nm]','$_POST[nk]','no',now())". 2. Input Simpul “INSERT INTO simpul(no,id_simpul,nama_simpul,kode_kasus) VALUES('','$no','$nv[$i]','$rst4[0]')”. 3. Input Sisi "INSERT INTO sisi(no,id_sisi,nama_sisi,asal,tuju,bobot,kode_kasus) VALUES ('','$no','$ne[$p]','$asal[$p]','$tuju[$p]','$bobot[$p]','$rst5[0]')". 4. View Kasus “SELECT * FROM ssp ORDER BY kode Desc Limit $posisi,$batas". 5. View Data Simpul “SELECT id_simpul,nama_simpul FROM simpul WHERE kode_kasus='$h1' ORDER BY id_simpul ASC”. 6. View Data Sisi "SELECT q.id_sisi,q.nama_sisi,p.nama_simpul,r.nama_simpul,q.bobot,q.no

43

FROM simpul p,sisi q, simpul r WHERE p.kode_kasus=r.kode_kasus AND r.kode_kasus=q.kode_kasus AND q.kode_kasus='$h1' AND p.id_simpul=q.asal AND r.id_simpul=q.tuju ORDER BY q.no ASC". 7. View Matriks "SELECT * FROM simpul WHERE kode_kasus='$row[0]' ORDER BY id_simpul" "SELECT * FROM sisi WHERE asal=$simpul1[$j] OR tuju=$simpul1[$j] AND kode_kasus='$row[0]' Order By id_sisi". 8. Proses PD "SELECT DISTINCT id_simpul FROM simpul WHERE kode_kasus='G4789001' ORDER BY id_simpul" "SELECT bobot FROM sisi WHERE asal=$i AND tuju=$j AND kode_kasus='G4789001'"

44

SIDANG SKRIPSI

Jum’at, 10 Juni 2011


Oleh: Gerdyandanu Nilanto (107094003005)

1

LATAR BELAKANG Graf

Informasi Lintasan Terpendek Hasil

Pemrograman Dinamis Aplikasi Graf Metode Penyelesaian

Pencarian Lintasan Terpendek

Sidang Skripsi Gerdy

2

LATAR BELAKANG Informasi Lintasan Terpendek

Bahasa Pemrograman

Basis Data

SISTEM INFORMASI


3

PERUMUSAN MASALAH 1. Bagaimana penggunaan graf pada sebuah sistem informasi. 2. Menyelesaikan permasalahan lintasan terpendek dengan pemrograman dinamis. 3. Menyediakan fasilitas pencarian lintasan terpendek berbasis web.

PEMBATASAN MASALAH 1. Graf yang digunakan adalah graf berhingga, graf terhubung, graf tak berarah dan graf berlabel. 2. Data yang digunakan adalah data jarak antar kota di Jawa Barat. 3. Pemrograman dinamis yang digunakan hanya pada permasalahan lintasan terpendek. 4. Keluaran yang dihasilkan hanya berupa jarak terpendeknya beserta simpulsimpul yang dilewatinya.


4

TUJUAN Tujuan yang ingin dicapai dalam skripsi ini adalah menerapkan teori graf pada permasalahan lintasan yang diselesaikan dengan metode pemrograman dinamis. Pada skripsi ini akan disediakan sebuah fasilitas pencarian lintasan terpendek berbasis web dengan mengimplementasikan suatu bahasa pemrograman dan pengoperasian basis data.

MANFAAT Manfaat yang ingin dicapai dalam skripsi ini adalah untuk memberikan fasilitas kepada pengguna yang ingin mencari atau menemukan lintasan terpendek sehingga mempermudah pengguna dalam mengambil keputusan untuk menuju ke suatu tempat dengan jarak yang lebih pendek dan memungkinkan dapat sampai ke tempat tujuan lebih cepat.


5

LANDASAN TEORI 1.

Graf Graf adalah himpunan yang terdiri dari himpunan simpul yang tak kosong dan himpunan sisi yang mungkin kosong yang merupakan pasangan tak terurut dari dua buah simpul. Matriks ketetanggaan didefinisikan sebagai berikut, misalkan A = (aij) adalah matriks m × m yang didefinisikan oleh,

Maka A disebut matriks ketetanggaan dari G.

Contoh :


6

LANDASAN TEORI 2.

Lintasan Terpendek lintasan terpendek dapat diartikan sebagai jarak paling terpendek dari beberapa lintasan. 1

2

Bekasi

3

4

5

6

24 41 80

Jakarta

Karawang

Purwakarta

41

60

Sumedang 50

86

Bandung

Tasikmalaya

24

Depok

61

95

68

49

32

54 65

Sukabumi

Cianjur

Garut

Bogor

Gambar 2.1 Sidang Skripsi Gerdy

7

LANDASAN TEORI 3.

Pemrograman Dinamis Pemrograman Dinamis adalah suatu metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan tahap sedemikian sehingga solusi dari permasalahan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas yaitu, “suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan selanjutnya harus membentuk suatu

kebijakan optimal yang berkaitan dengan keadaan yang dihasilkan dari keputusan awal” Ada dua pendekatan dalam penyelesaian pemrograman dinamis yaitu maju dan mundur.


masalah

dengan

8

LANDASAN TEORI 3.

Pemrograman Dinamis Rumusan Pemrograman Dinamis:


9

LANDASAN TEORI 3.

Pemrograman Dinamis Penyelesaian PD dengan Pendekatan Maju pada permasalahan gambar 2.1:

…


10

LANDASAN TEORI 3.

Pemrograman Dinamis Penyelesaian PD dengan Pendekatan Mundur pada permasalahan gambar 2.1:

…


11

LANDASAN TEORI 3.

Pemrograman Dinamis Hasil penyelesaian dari pendekatan maju dan mundur menghasilkan hasil solusi lintasan terpendek yang sama. Maka disimpulkan jarak terpendek dari Jakarta ke Tasikmalaya dengan menggunakan metode pemrograman dinamis adalah 283. Sedangkan kota-kota yang dilewatinya yaitu, Jakarta -> Bekasi -> Karawang -> Purwakarta -> Bandung -> Garut Tasikmalaya.


12

LANDASAN TEORI 4.

Algoritma Pemrograman Dinamis For (k=1->n,k++) For (i=1->n,i++) For (j=1->n,j++) A(i,j)=min{A(i,j) , A(i,k) + A(k,j)} end end end Hasil: K=1 i=1 j=1 -> : A(1,1)=min{A(1,1), A(1,1)+A(1,1)} = 0 j=2 -> : A(1,2)=min{A(1,2), A(1,1)+A(1,2)} = 41 j=3 -> : A(1,3)=min{A(1,3), A(1,1)+A(1,3)} = 24 j=4 -> : A(1,4)=min{A(1,4), A(1,1)+A(1,4)} = 54 … i=2 … … K=2 … Sidang Skripsi Gerdy

13

LANDASAN TEORI 5.

Basis Data Basis data adalah kumpulan data sistematis yang digunakan untuk

menyimpan informasi atau data.

6.

MySQL MySQL adalah Database Management System (DBMS) tools open source yang mendukung multiuser.

7.

PHP PHP adalah bahasa pemrograman yang memungkinkan para web

developer untuk membuat aplikasi web yang dinamis dengan cepat.


14

PERANCANGAN SISTEM 1.

Metode Pengumpulan Data


15


Metode Pengolahan Data Tools Yang digunakan antara lain:

- Bahasa Pemrograman

Version 5.2.5

- Basis Data Version 5.0.51

- Software Version 1.6.5 Sidang Skripsi Gerdy

16


Rancangan Sistem DFD (Data Flow Diagram) DFD Level 0 login

registrasi

daftar kasus

daftar kasus

view data kasus komentar

ADMIN

hapus kasus

komentar

Sistem Informasi Pencarian Lintasan Terpendek

view data kasus solusi Input data

UMUM

komentar edit dan hapus data


17


Rancangan Sistem DFD (Data Flow Diagram)

DFD Level 1 profile admin, display data

kasus

data registrasi display data

1.0* Manajemen pengguna

registrasi, password dispay data

simpul

data Input display data

data input

sisi

display data

komentar

Input komentar display data

Umum

2.0* Manajemen simpul

3.0* Manajemen sisi

4.0* Manajemen komentar

display data, hapus data, komentar hapus data, komentar

Input komentar display data, ubah data, hapus data


Admin

login

Admin

Umum

18

Start

PERANCANGAN SISTEM Tema

3.

Rancangan Sistem Design

Membuat ERD, LRS, Kamus Data dan DFD

Pengambilan Data

Input Data

Alur Sistem :

Pemilihan Data

Tidak

Pemrograman Dinamis

Ya Hasil

Kesimpulan

End


19

HASIL DAN PEMBAHASAN 1.

Registrasi

QUERY : INSERT INTO kasus VALUES('$kode','$ _POST[nm]','$_PO ST[nk]','no',now())


20


Input Simpul

QUERY : INSERT INTO simpul(no,id_simp ul,nama_simpul,k ode_kasus) VALUES('','$no','$n v[$i]','$rst4[0]')


21


Input Sisi

QUERY : INSERT INTO sisi(no,id_sisi,nam a_sisi,asal,tuju,bo bot,kode_kasus) VALUES ('','$no','$ne[$p]',' $asal[$p]','$tuju[$ p]','$bobot[$p]','$r st5[0]')


22


View Kasus

QUERY : SELECT * FROM komen WHERE kode_kasus='$rst6 [0]'


23


View Data

QUERY : --view simpulSELECT id_simpul,nama_simpul From simpul WHERE kode_kasus='$h1' Order By id_simpul ASC

--view sisi— SELECT q.id_sisi,q.nama_sisi,p.nama_si mpul,r.nama_simpul,q.bobot,q. no FROM simpul p,sisi q, simpul r Where p.kode_kasus=r.kode_kasus And r.kode_kasus=q.kode_kasus And q.kode_kasus='$h1’ And p.id_simpul=q.asal And r.id_simpul=q.tuju Order By q.no ASC Sidang Skripsi Gerdy

24


Hasil


25

KESIMPULAN DAN SARAN 1.

Kesimpulan Dengan menggunakan metode pemrograman dinamis dapat dihasilkan solusi optimum dalam setiap permasalahan lintasan terpendek. Dan metode ini dapat diimplementasikan dengan suatu bahasa pemrograman dan basis data sehingga dapat menghasilakan sebuah sistem informasi pencarian lintasan terpendek yang dapat mempermudah dan mempercepat dalam pengambilan keputusan untuk setiap permasalahan pencarian lintasan terpendek.


26

KESIMPULAN DAN SARAN 2.

Saran a. Agar hasil lebih akurat, gunakan graf berarah dalam permasalahan lintasan terpendek karena ada kemungkinan jarak suatu jalan dari A ke B tidak selalu sama dengan jarak dari B ke A. b. Gunakan pula data yang lebih akurat untuk menghasilakan hasil yang lebih akurat. Misalanya pergunakan bobot atau jarak sedetil mungkin tidak hanya sebuah bilangan bulat saja. c. Agar aplikasi lebih menarik dan terlihat jelas, tampilkan graf atau diagram pada setiap permasalahan lintasan terpendeknya. d. Aplikasi pencarian lintasan terpendek ini dapat dimodifikasi menjadi pencarian lintasan tercepat atau termurah dengan ditambahkan parameter-parameter pendukungnya. Atau dengan penggabuangan dari kedua atau bahkan ketiga pencarian maka akan menghasilakan sebuah aplikasi pencarian yang lebih sempurna.


27

PENUTUP

SEKIAN & TERIMAKASIH WASSALAM . . . Sidang Skripsi Gerdy

28


Rancangan Sistem b. Normalisasi


29


Rancangan Sistem a. ERD kontak

no_sisi

id_sisi

password

nm_sisi

jml_kasus

agama

nm_lengkap

alamat

nm_admin bobot

asal

Sisi

Admin

pekerjaan

id_admin kode_kasus

tuju email

berhubungan

terdapat

kontrol

kontrol kode_kasus

nm_simpul

Simpul

terdapat

Kasus

memuat

Komentar id_komen

no_simpul komentator id_simpul

kode_kasus

nama_kasus

kode_kasus


pass_kasus

komentar

tanggal

nama_pembuat

30


31

SISTEM INFORMASI PENCARIAN LINTASAN TERPENDEK MENGGUNAKAN PEMROGRAMAN DINAMIS. Gerdyandanu Nilanto

Recommend Documents