sistem informasi pencarian lintasan terpendek …

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

SISTEM INFORMASI PENCARIAN LINTASAN TERPENDEK

MENGGUNAKAN PEMROGRAMAN DINAMIS

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

ii

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,

Nur Inayah, M.Si

NIP. 19740125 200312 2 001

Penguji II,

Gustina Elfiyanti, M.Si

NIP. 19820820 200901 2 006

Pembimbing I,

Drs. Slamet Aji Pamungkas, M.Eng

NIP. 19670618 199301 1 001

Pembimbing II,

Yanne Irene, M.Si

NIP. 19741231 200501 2 018

Mengetahui,

Ketua Program Studi Matematika,

Yanne Irene, M.Si

NIP. 19741231 200501 2 018

Dekan Fakultas Sains dan Teknologi,

Dr. Syopiansyah Jaya Putra, M.Sis

NIP. 19680117 200112 1 001

iii

PERNYATAAN

DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENAR-

BENAR 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

iv

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.

v

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.

vi

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.

vii

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.

viii

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, teman-

teman 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

ix

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

x

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

xi

BAB V KESIMPULAN DAN SARAN ................................................... 38

5.1 Kesimpulan .............................................................................. 38

5.2 Saran ......................................................................................... 39

DAFTAR PUSTAKA ............................................................................... 40

LAMPIRAN

BIODATA PENULIS

xii

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

xiii

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

1

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

2

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”.

3

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 simpul-

simpul 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.

4

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.

5

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,

6

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.

7

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

8

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 perhitungan-

perhitungan yang diperlukan dalam komputer jadi lebih mudah dilakukan [9].

9

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

10

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.

11

Contoh penerapan pemrograman dinamis pada permasalahan lintasan

terpendek, tentukan lintasan terpendek dari Jakarta ke Tasikmalaya dari Gambar

2.6.

Jakarta

Bekasi

Depok

Bogor

Sukabumi

Karawang

Cianjur

Purwakarta

TasikmalayaBandung

Sumedang

Garut

49

32

61 68

50 86

41

24

54

65

80

24

6041

1 2 3 4 5 6

95

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).

12

Maka penyelesaian masalah pada contoh diatas adalah sebagai berikut:

1. Penyelesaian Dengan Pendekatan Maju

a. Tahap 1 : f1(s) =

Tabel 2.1 Tahap 1

s Solusi Optimum

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

s

f2(x2 , s) = + f1(x2) Solusi Optimum

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

x3

s


Karawang Sukabumi f3(s) x3*

Purwakarta 106 - 106 Karawang

Cianjur - 151 151 Sukabumi

d. Tahap 4 : f4(s) = { + f3(x4)}

Tabel 2.4 Tahap 4

x4

s


Purwakarta Cianjur f4(s) x4*

Bandung 166 212 166 Purwakarta

e. Tahap 5 : f5(s) = { + f4(x5)}

Tabel 2.5 Tahap 5

x5

s


Bandung f5(s) x5*

Sumedang 216 216 Bandung

Garut 234 234 Bandung

13

f. Tahap 6 : f6(s) = { + f5(x6)}

Tabel 2.6 Tahap 6

x5

s


Sumedang Garut f5(s) x6*

Tasikmalaya 302 283 283 Garut

Solusi optimum dapat dibaca pada tabel di bawah ini:

Tabel 2.7 Solusi Pendekatan Maju

x1 x2 x3 x4 x5 x6 N Jumlah

Label

Jakarta Bekasi Karawang Purwakarta Bandung Garut Tasikmalaya 283

2. Penyelesaian Dengan Pendekatan Mundur

a. Tahap 6 : f6(s) =

Tabel 2.8 Tahap 6

s Solusi Optimum

f6(s) x6*

Sumedang 86 Tasikmalaya

Garut 49 Tasikmalaya

b. Tahap 5 : f5(s) = { + f6 (x5)}

Tabel 2.9 Tahap 5

x5

s

f5(s,x5) = + f6 (x5) Solusi Optimum

Sumedang Garut f5(s) x5*

Bandung 136 117 117 Garut

c. Tahap 4 : f4(s) = { + f5 (x4)}

Tabel 2.10 Tahap 4

x4

s


Bandung f4(s) x4*

Purwakarta 177 177 Bandung

Cianjur 178 178 Bandung

d. Tahap 3 : f3(s) = { + f4 (x3)}

Tabel 2.11 Tahap 3

x3

s


Purwakarta Cianjur f3(s) x3*

Karawang 218 - 218 Purwakarta

Sukabumi - 210 210 Cianjur

14

e. Tahap 2 : f2(s) = { + f3 (x2)}

Tabel 2.12 Tahap 2

x2

s


Karawang Sukabumi f2(s) x2*

Bekasi 242 - 242 Karawang

Depok 298 - 298 Karawang

Bogor 313 275 275 Sukabumi

f. Tahap 1 : f1(s) = { + f2 (x1)}

Tabel 2.13 Tahap 1

x1

s


Bekasi Depok Bogor f1(s) x1*

Jakarta 283 322 329 283 Bekasi

Solusi optimum dapat dibaca pada tabel di bawah ini:

Tabel 2.14 Solusi Pendekatan Mundur

1 x1 x2 x3 x4 x5 x6 Jumlah

Label

Jakarta Bekasi Karawang Purwakarta Bandung Garut Tasikmalaya 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 Bekasi

Karawang Purwakarta Bandung Garut 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 masing-

masing. Kompleksitas algoritma adalah suatu ukuran dari banyaknya perhitungan

15

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.

16

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.

17

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.

18

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 atribut-

atributnya. 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.

19

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.

20

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.

21

terdapat Kasus

no_simpul

Simpul

Sisi

terdapat

Komentarmemuat

id_simpul

nm_simpul

kode_kasus pass_kasusnama_kasus tanggal

nama_pembuatkode_kasus

kode_kasus

id_komen

komentarkomentator

no_sisi nm_sisiid_sisi

asalbobot

tujukode_kasus

kontrol

Admin

id_admin

nm_admin

password agama nm_lengkap

alamat

pekerjaan

email

kontak jml_kasus

berhubungan kontrol

Gambar 3.1 ERD

3.3.2 Logical Record Structure (LRS)

Admin

id_admin

nm_admin

password

jml_kasus

nm_lengkap

alamat

agama

pekerjaan

kontak

email

Komentar

id_komen

kode_kasus

komentator

komentar

<pk>no_edge<pk

Kasus

kode_kasus

nm_pembuat

nm_kasus

pass_kasus

tanggal

<pk>kode_kasus

Simpul

no_simpul

id_simpul

nm_simpul

kode_kasus

Sisi

no_sisi

id_sisi

nm_sisi

asal

tuju

bobot

kode_kasus

Gambar 3.2 LRS

22

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

Tabel 3.2 Normalisasi Kedua

Kasus

kode_kasus

nm_pembuat

nm_kasus

pass_kasus

tanggal

<pk>kode_kasus

<pk>

Simpul

no_simpul

id_ simpul

nm_ simpul

kode_kasus

<pk>no_verte

k<pk>

Sisi

no_sisi

id_sisi

nm_sisi

asal

tuju

bobot

kode_kasus

<pk>no_edge

<pk>

Komentar

id_komen

kode_kasus

komentator

komentar

<pk>no_edge<pk

>

Admin

id_admin

nm_admin

password

nm_lengkap

alamat

agama

pekerjaan

kontak

jml_kasus

email <pk>kode_kasus

<pk>

Kasus

kode_kasus

nm_pembuat

nm_kasus

pass_kasus

tanggal

<pk>kode_kasus

<pk>

Simpul

id_simpul

nm_simpul

kode_kasus

<pk>no_verte

k<pk>

Sisi

id_sisi

nm_sisi

asal

tuju

bobot

kode_kasus

<pk>no_edge

<pk>

Komentar

id_komen

kode_kasus

komentator

komentar

<pk>no_edge<pk

>

Admin

id_admin

nm_admin

password

nm_lengkap

alamat

agama

pekerjaan

kontak

jml_kasus

email <pk>kode_kasus

<pk>

23

3.3.4 Kamus Data

Kamus data merupkan suatu penjabaran atau pendeskripsian struktur-

struktur 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 Type Size Keterangan

kode_kasus Varchar 10 Kode kasus

nm_pembuat Varchar 50 Nama pembuat

nm_kasus Varchar 100 Nama kasus

pass_kasus Varchar 32 Password kasus

tanggal Date 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


no_simpul Int auto_increment No simpul

id_simpul Int 11 Identitas simpul

nm_simpul Varchar 50 Nama simpul


24

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


no_sisi Int auto_increment No sisi

id_sisi Int 11 Identitas sisi

nm_sisi Varchar 100 Nama sisi

asal Int 11 Identitas simpul asal

tuju Int 11 Identitas simpul tujuan

bobot Int 11 Bobot


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


id_komen Int auto_increment Identitas setiap komentar


komentator Varchar 30 Nama pengomentar

komentar Varchar 500 Isi komentar

e) Tabel Admin

Nama Tabel : admin

Deskripsi : pengontrol sistem informasi

Primery key : id_admin

Foreign key : jml_kasus, nm_admin

25

Tabel 3.7 Struktur Data Tabel Admin


id_admin Varchar 10 Identitas Admin

nm_admin Varchar 20 Nama panggilan Admin

password Varchar 32 Password Admin

nm_lengkap Varchar 50 Nama Lengkap Admin

jml_kasus Int 11 Jumlah Keseluruhan Kasus

alamat Varchar 200 Alamat Admin

pekerjaan Vvarchar 50 Pekerjaan Admin

agama Varchar 10 Agama Admin

kontak Varchar 20 Kontak Personal Admin

email Varchar 30 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

26

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

1.0*

Manajemen

pengguna

kasus

Admin

Umum

registrasi,

password

data registrasi

2.0*

Manajemen

simpul

simpul data Input

3.0*

Manajemen

sisi

sisi data input

4.0*

Manajemen

komentar

komentar

Admin

UmumInput komentar

Input komentar

profile admin,

display data

dispay data

display data,

ubah data,

hapus data

display data

display data

display data

display data

display data,

hapus data,

komentar

login

hapus data,

komentar

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.

27

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++) (n+1).n

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

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

end

end

end +

n3 + 2n

2 + 2n + 1

Didapat kompleksitas algoritma pemrograman dinamis adalah Order n3

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

28

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

Pemilihan Data

Pemrograman

Dinamis

Kesimpulan

End

Ya

Tidak

Hasil

Input Data

Gambar 3.5 Flowchart Sistem

29

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 Kota Tujuan Nama Jalan Jarak(km)

1 Jakarta Bekasi Tol Jakarta - Cikampek 41

2 Jakarta Depok Jalan Margonda 24

3 Jakarta Bogor Jalan Citayam 54

4 Bekasi Karawang Jalan Raya Rengas -

Lemahabang 24

5 Depok Karawang

Tol Lingkar Luar TMII -

Cikunir dan Tol Jakarta –

Cikampek

80

6 Bogor Sukabumi Jalan Raya Sukabumi 65

7 Bogor Karawang Jalan Jendral S. Parman dan Tol

Jakarta - Cikampek 95

8 Karawang Purwakarta Jalan Raya Curug 41

9 Sukabumi Cianjur Jalan Sukabumi - Cianjur 32

10 Purwakarta Bandung Tol Cipularang 60

11 Cianjur Bandung Jalan Raya Bandung dan Jalan

Raya Raja Mandala 61

12 Bandung Sumedang Jalan Raya Jatinangor 50

13 Bandung Garut Jalan Cicalengka - Nagrek 68

14 Sumedang Tasikmalaya Jalan Malangbong - Ciawi 86

15 Garut Tasikmalaya Jalan Garut – Tasikmalaya 49

30

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)

31

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)

32

Gambar 4.3 Tahap Input kedua (Form Simpul)

Gambar 4.4 Tahap Input ketiga (Form Sisi)

33

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.

memiliki SimpulKasus

Sisi

memiliki terdapat

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.

memiliki KomentarKasus

Gambar 4.6 Tabel Relationship Komentar

34

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.

35

Gambar 4.8 Fitur viewdata kasus

Gambar 4.9 Fitur Matriks

36

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

37

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.

38

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.

39

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 parameter-

parameter pendukungnya. Atau dengan penggabungan dari dua atau bahkan

tiga pencarian maka akan menghasilkan sebuah sistem informasi pencarian

lintasan yang lebih sempurna.

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

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 RIWAYAT HIDUP

Data Pribadi

Riwayat Pendidikan

BIODATA PENULIS

mailto:[email protected]

mailto:[email protected]

40

DAFTAR PUSTAKA

[1] Dynamic Programming : Universitas Oxford. pada tanggal 27 Mei 2011

pukul 10.05 WIB. http://www.oxford-

mphil.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.

http://www.oxford-mphil.com/images/c/.../Dynamic-programming-4-principle.pdf

http://www.oxford-mphil.com/images/c/.../Dynamic-programming-4-principle.pdf

http://map.google.co.id/

41

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 ,

`id_simpul` INT NOT NULL ,

`nm_simpul` VARCHAR( 50 ) NOT NULL ,


PRIMARY KEY ( `no_simpul` ))

4. Membuat Tabel Sisi

CREATE TABLE `lintasan`.`sisi` (

`no_sisi` INT NOT NULL AUTO_INCREMENT ,

42

ìd_sisi` INT NOT NULL ,

`nm_sisi` VARCHAR( 50 ) NOT NULL ,

àsal` INT NOT NULL ,

`tuju` INT NOT NULL ,

`bobot` INT NOT NULL ,


PRIMARY KEY ( `no_sisi` ) )

5. Membuat Tabel Komentar

CREATE TABLE `lintasan`.`komentar` (

ìd_komen` INT( 11 ) 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 ,

43

à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

44

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'"

SISTEM INFORMASI PENCARIANLINTASAN TERPENDEK MENGGUNAKAN

PEMROGRAMAN DINAMIS

Oleh: Gerdyandanu Nilanto (107094003005)

SIDANG SKRIPSI

1

Jum’at, 10 Juni 2011

LATAR BELAKANG

Sidang Skripsi Gerdy2

Graf

Aplikasi Graf

Pencarian Lintasan Terpendek

Metode Penyelesaian

Pemrograman Dinamis

Informasi Lintasan Terpendek

Hasil

LATAR BELAKANG


Informasi Lintasan Terpendek

BahasaPemrograman

Basis Data

SISTEMINFORMASI

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 berarahdan 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 simpul-

simpul yang dilewatinya.


TUJUAN

Tujuan yang ingin dicapai dalam skripsi ini adalah menerapkan teori grafpada permasalahan lintasan yang diselesaikan dengan metode pemrogramandinamis. Pada skripsi ini akan disediakan sebuah fasilitas pencarian lintasanterpendek berbasis web dengan mengimplementasikan suatu bahasapemrograman dan pengoperasian basis data.


MANFAAT

Manfaat yang ingin dicapai dalam skripsi ini adalah untuk memberikanfasilitas kepada pengguna yang ingin mencari atau menemukan lintasanterpendek sehingga mempermudah pengguna dalam mengambil keputusan untukmenuju ke suatu tempat dengan jarak yang lebih pendek dan memungkinkandapat sampai ke tempat tujuan lebih cepat.

LANDASAN TEORI

1. GrafGraf adalah himpunan yang terdiri dari himpunan simpul yang tak kosong danhimpunan sisi yang mungkin kosong yang merupakan pasangan tak terurutdari dua buah simpul.

Matriks ketetanggaan didefinisikan sebagai berikut, misalkan A = (aij) adalahmatriks m × m yang didefinisikan oleh,

Maka A disebut matriks ketetanggaan dari G.

Contoh :


LANDASAN TEORI

2. Lintasan Terpendek

lintasan terpendek dapat diartikan sebagai jarak paling terpendek

dari beberapa lintasan.

Gambar 2.1

7Sidang Skripsi Gerdy

Jakarta

Bekasi

Depok

Bogor

Sukabumi

Karawang

Cianjur

Purwakarta

TasikmalayaBandung

Sumedang

Garut

49

32

61 68

50 86

41

24

54

65

80

24

6041

1 2 3 4 5 6

95

LANDASAN TEORI

3. Pemrograman DinamisPemrograman Dinamis adalah suatu metode pemecahan masalahdengan cara menguraikan solusi menjadi sekumpulan tahapsedemikian sehingga solusi dari permasalahan dapat dipandang dariserangkaian keputusan yang saling berkaitan.Rangkaian keputusan yang optimal dibuat dengan menggunakanprinsip 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 masalah denganpemrograman dinamis yaitu maju dan mundur.


LANDASAN TEORI

3. Pemrograman DinamisRumusan Pemrograman Dinamis:


LANDASAN TEORI

3. Pemrograman DinamisPenyelesaian PD dengan Pendekatan Maju pada permasalahangambar 2.1:

…


LANDASAN TEORI

3. Pemrograman DinamisPenyelesaian PD dengan Pendekatan Mundur pada permasalahangambar 2.1:

…


LANDASAN TEORI

12

3. Pemrograman DinamisHasil penyelesaian dari pendekatan maju dan mundur menghasilkanhasil solusi lintasan terpendek yang sama. Maka disimpulkan jarakterpendek dari Jakarta ke Tasikmalaya dengan menggunakan metodepemrograman dinamis adalah 283. Sedangkan kota-kota yangdilewatinya yaitu,Jakarta -> Bekasi -> Karawang -> Purwakarta -> Bandung -> GarutTasikmalaya.

Sidang Skripsi Gerdy

LANDASAN TEORI

13

4. Algoritma Pemrograman DinamisFor (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

endendHasil:K=1

i=1j=1 -> : A(1,1)=min{A(1,1), A(1,1)+A(1,1)} = 0j=2 -> : A(1,2)=min{A(1,2), A(1,1)+A(1,2)} = 41j=3 -> : A(1,3)=min{A(1,3), A(1,1)+A(1,3)} = 24j=4 -> : A(1,4)=min{A(1,4), A(1,1)+A(1,4)} = 54…

i=2…

…K=2

…


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.


PERANCANGAN SISTEM

1. Metode Pengumpulan Data


PERANCANGAN SISTEM

2. Metode Pengolahan DataTools Yang digunakan antara lain:

- Bahasa Pemrograman

Version 5.2.5

- Basis Data

Version 5.0.51

- Software

Version 1.6.5


PERANCANGAN SISTEM

3. Rancangan SistemDFD (Data Flow Diagram)

DFD Level 0

SistemInformasiPencarianLintasan

Terpendek

UMUMADMIN

registrasi

view data kasus

Input data

daftar kasus

view data kasus

komentar

komentar

edit dan hapus data

hapus kasus

login

solusi

daftar kasus

komentar


PERANCANGAN SISTEM

3. Rancangan SistemDFD (Data Flow Diagram)

DFD Level 1


1.0*

Manajemen

pengguna

kasus

Admin

Umum

registrasi,

password

data registrasi

2.0*

Manajemen

simpul

simpul data Input

3.0*

Manajemen

sisi

sisi data input

4.0*

Manajemen

komentar

komentar

Admin

UmumInput komentar

Input komentar

profile admin,

display data

dispay data

display data,

ubah data,

hapus data

display data

display data

display data

display data

display data,

hapus data,

komentar

login

hapus data,

komentar

PERANCANGAN SISTEM

3. Rancangan Sistem

Alur Sistem :


Start

Tema

Design

Membuat ERD, LRS, Kamus Data

dan DFD

Pengambilan Data

Pemilihan Data

Pemrograman

Dinamis

Kesimpulan

End

Ya

Tidak

Hasil

Input Data


1. Registrasi

QUERY :

INSERT INTO kasusVALUES('$kode','$_POST[nm]','$_POST[nk]','no',now())



2. Input Simpul

QUERY :

INSERT INTO simpul(no,id_simpul,nama_simpul,kode_kasus) VALUES('','$no','$nv[$i]','$rst4[0]')



3. Input Sisi

QUERY :

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

QUERY :

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



5. View DataQUERY :

--view simpul-SELECT id_simpul,nama_simpulFrom simpul WHERE kode_kasus='$h1' Order By id_simpul ASC

--view sisi—SELECT q.id_sisi,q.nama_sisi,p.nama_simpul,r.nama_simpul,q.bobot,q.no FROM simpul p,sisi q, simpulr Where p.kode_kasus=r.kode_kasusAnd r.kode_kasus=q.kode_kasusAnd q.kode_kasus='$h1’ And p.id_simpul=q.asal And r.id_simpul=q.tujuOrder By q.no ASC



6. Hasil



1. KesimpulanDengan menggunakan metode pemrograman dinamis dapat

dihasilkan solusi optimum dalam setiap permasalahan lintasan terpendek.Dan metode ini dapat diimplementasikan dengan suatu bahasapemrograman dan basis data sehingga dapat menghasilakan sebuahsistem informasi pencarian lintasan terpendek yang dapatmempermudah dan mempercepat dalam pengambilan keputusan untuksetiap permasalahan pencarian lintasan terpendek.



2. Sarana. Agar hasil lebih akurat, gunakan graf berarah dalam permasalahan

lintasan terpendek karena ada kemungkinan jarak suatu jalan dari Ake B tidak selalu sama dengan jarak dari B ke A.

b. Gunakan pula data yang lebih akurat untuk menghasilakan hasil yanglebih akurat. Misalanya pergunakan bobot atau jarak sedetil mungkintidak hanya sebuah bilangan bulat saja.

c. Agar aplikasi lebih menarik dan terlihat jelas, tampilkan graf ataudiagram pada setiap permasalahan lintasan terpendeknya.

d. Aplikasi pencarian lintasan terpendek ini dapat dimodifikasi menjadipencarian lintasan tercepat atau termurah dengan ditambahkanparameter-parameter pendukungnya. Atau dengan penggabuangandari kedua atau bahkan ketiga pencarian maka akan menghasilakansebuah aplikasi pencarian yang lebih sempurna.


28

PENUTUP

SEKIAN & TERIMAKASIHWASSALAM . . .


PERANCANGAN SISTEM

3. Rancangan Sistemb. Normalisasi


PERANCANGAN SISTEM

3. Rancangan Sistema. ERD


terdapat Kasus

no_simpul

Simpul

Sisi

terdapat

Komentarmemuat

id_simpul

nm_simpul

kode_kasus pass_kasusnama_kasus tanggal

nama_pembuatkode_kasus

kode_kasus

id_komen

komentarkomentator

no_sisi nm_sisiid_sisi

asalbobot

tujukode_kasus

kontrol

Admin

id_admin

nm_admin

password agama nm_lengkap

alamat

pekerjaan

email

kontak jml_kasus

berhubungan kontrol

sistem informasi pencarian lintasan terpendek …

Documents