18
BAB 2
LANDASAN TEORI
2.1.
Pengertian Algoritma
Algoritma adalah urutan atau deskripsi langkah- langkah penyelesaian masalah yang tersusun secara logis, ditulis dengan notasi yang mudah dimengerti sedemikian sehingga langkah- langkah tersebut dapat dilaksanakan oleh pemroses dan merubah masukan masukan menjadi keluaran (Thomas, 2009). Algoritma adalah ilmu yang mempelajari cara penyelesaian suatu masalah berdasarkan urutan langkah-langkah terbatas yang disusun secara sistematis dan menggunakan bahasa yang logis dengan tujuan tertentu (Barakbah, dkk, 2013).
2.1.1. Syarat Algoritma Menurut (Knuth, 1997) algoritma harus memenuhi persyaratan : 1. Finiteness : Algoritma harus berakhir (terminate) setelah melakukan sejumlah langkah proses. 2. Definiteness : Tidak menimbulkan makna ganda (ambgious). 3. Input : Setiap algoritma memerlukan data sebagai masukan untuk diolah. 4. Output : Setiap algoritma memberikan satu atau beberapa hasil keluaran. 5. Effectiveness : langkah-langkah algoritma dikerjakan dalam waktu yang wajar 2.2. Shortest Path Masalah jalan terpendek adalah salah satu masalah yang paling mendasar dalam kombinasi optimasi. Bahkan dalam rangka memecahkan masalah yang paling kombinatorial, baik perhitungan jalur terpendek disebut untuk, atau konsep yang dibuat menggunakan yang pertama kali dikembangkan dalam kerangka jalur terpendek. Selain itu meningkatnya peran model jaringan skala besar, seperti yang dikembangkan dalam analisis transportasi dan perencanaan telah meningkatkan
Universitas Sumatera Utara
19
kebutuhan untuk efisien algoritma jalur terpendek dikelompokkan berdasarkan jenis pola dan metode pencocokan string yang digunakan (Giorgio, 1998).
2.3. Teori Dasar Graph Teori graph adalah cabang kajian yang mempelajari sifat-sifat graph. Secara informal, suatu graph adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc) (Diestel, 2006). Graph dapat dikelompokkan menjadi beberapa jenis bergantung pada sudut pandang pengelompokkan-nya.
Pengelompokkan
graph
dapat
dipandang
berdasarkan ada tidak nya sisi ganda atau sisi kalang, berdasarkan jumlah simpul atau berdasarkan orientasi arah pada sisi (Munir, 2007). Berdasarkan ada atau tidaknya gelang atau busur ganda pada suatu graph maka secara umum graph dapat dikelompokkan menjadi dua jenis: 1. Graph sederhana (simple graph) yaitu graph yang tidak mengandung gelang maupun sisi-ganda. Pada graph sederhana, sisi adalah pasangan tak-terurut (unordered pairs). Jadi menuliskan sisi (u, v) sama saja dengan (v, u). Kita dapat juga mendefinisikan graph sederhana G = (V, E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak-terurut yang berbeda disebut sisi (Munir, 2007). 2. Graph tak-sederhana (unsimple graph) yaitu graph yang mengandung sisi ganda atau gelang dinamakan graph tak-sederhana (unsimple graph). Ada dua macam graph tak-sederhana, yaitu graph ganda dan graph semu. Sisi pada graph dapat mempunyai orientasi arah. Menurut orientasi arah pada sisinya, graph dibagi menjadi dua jenis, yaitu: 1. Graph tidak berarah (undirected graph) adalah graph yang sisinya tidak mempunyai orientasi arah, pada graph ini, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Sebagai contoh graph tidak berarah dapat dilihat pada gambar2.1 (Munir, 2007).
Universitas Sumatera Utara
20
Gambar 2.1 Graph Tidak berarah
2. Graph berarah (directed graph) adalah graph yang setiap sisinya diberikan orientasi arah, graph berarah sering dipakai untuk menggambarkan aliran proses, peta lintas suatu kota, dan sebagainya (Munir, 2007). Sebagai contoh graph berarah dapat dilihat pada gambar 2.2
Gambar 2.2 Graph Berarah
2.4. Algoritma L-Queue Antrian (queue) merupakan pilihan yang sangat bijak ketika kita menerapkan SPT, biasanya disebut Algoritma L-queue, merupakan implementasi yang efisien dalam metode lintasan terpendek yang banyak diketahui dimana ditujukan kepada Bellman- Ford-Moore (Giorgio,1998) Queue beroperasi dengan cara First In First Out (FIFO) elemen pertama masuk merupakan elemen yang pertama keluar yaitu, grafik yang tingkat demi tingkat dieksplorasi.. Untuk penyisipan (insert) hanya dapat dilakukan pada satu sisi yaitu sisi belakang (rear), sedangkan untuk penghapusan (remove) pada sisi depan (front) dari list (Francois,1991).
Universitas Sumatera Utara
21
Operasi dasar pada queue : 1. create Adalah suatu operator untuk membentuk dan menunjukkan suatu antrian hampa Q. Noel ( Create(Q)) = 0 Front (Create(Q)) = tidak terdefinisi Rear (Create(Q))
= tidak terdefinisi
2. isEmpty Adalah operator yang menentukan apakah antrean Q hampa atau tidak. Hasil dari operator ini merupakan tipe data berjenis Boolean. isEmpty (Q)
= True , jika Q hampa = False , jika Q tidak hampa.
3. insert Suatu operator yang menyisipkan elemen ke dalam queue pada bagian belakang (rear) -
rear (insert(A,Q)) = A
-
isEmpty (insert(A,Q)) = false
Algoritma Qinsert 1. if front = 1 and rear = N , or If front = rear + 1, then overflow,
Return
2. if front := null, then set front := 1 and rear := 1 else if rear = N , then set rear := 1 else set rear := rear + 1 3. set queue [rear] := item 4. Return
4.
remove Operator yang menghapus elemen bagian depan (front) dari queue
Universitas Sumatera Utara
22
Algoritma Qdelete 1. if front := null , then underflow , Return 2. set item := queue[front] 3. [find new value of front] if front = rear , then set front := null and rear := null else if front = N, then set front := 1 else set front := front + 1 4. Return
2.5. Algoritma Floyd Teknik untuk menghitung panjang jalan terpendek antara semua pasangan node dalam jaringan n-node yang tidak mengandung sirkuit panjang negatif merupakan teknik dari algoritma Floyd (Douglas, 1981). Algoritma floyd adalah salah satu varian dari pemrograman dinamis, yaitu suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusisolusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu (Khan, 2014). Algoritma floyd juga dikenal sebagai metode penempatan vertex yang juga merupakan jenis pemrograman dinamis dan digunakan untuk menemukan jalur terpendek antara simpul dari graph berbobot (Wei, 2010). Algoritma Floyd sangat efisien dari sudut pandang penyimpanan data karena dapat diimplementasikan dengan hanya pengubahan sebuah matriks jarak (Rudi, 2014). Algoritma ini dapat digunakan untuk mencari jarak terpendek antara semua titik dalam graph. Bentuk algoritma untuk mencari R+ adalah sebagai berikut (Aini, 2012). Step 1
:
Jika
antara
i-j
merupakan
jalan
(edge),
T[i,j]
berisi panjang jalan. Jika tidak, T[i,j]= ∞. Step 2
: For k=1 to n do For i=1 to n do For j=1 to n do
Universitas Sumatera Utara
23
T[i,j]= min{ T[i,j] , T[i,j] · T[k,j] } Step 3
: R+=T.
Gambar 2.3. Graph Berbobot untuk Algoritma Floyd Graph berbotot diatas dapat dijadikan sebagai matriks inisialiasi seperti pada Tabel 2.1.
A
B
C
D
A
0
3
∞
∞
B
∞
0
4
1
C
2
∞
0
∞
D
∞
∞
1
0
DARI/KE
Tabel 2.1. Inisialisasi Matriks
Dari matriks inisialisasi dapat dicari R0, R1, R2, R3 dan R4. Kotak abjad berwarna hijau disamping kiri adalah titik awal dan kotak abjad berwarna merah yang ada di atas adalah titik tujuan-nya. Sedangkan kotak angka hijau dan merah berfungsi untuk menentukan sebuah index. Dalam gambar graph 2.3 diatas terdapat 4 buah titik, yaitu A, B, C, D maka akan ada 5 proses yang akan dilewati yaitu R0, R1, R2, R3, dan R4 sebagai
Universitas Sumatera Utara
24
hasil akhir, perlu diingat bahwa hasil dari sebuah proses akan digunakan untuk proses berikutnya. Dari proses perhitungan tersebut maka akan didapatkan hasil seperti pada gambar 2.4 berikut,
Gambar 2.4. Matriks Hasil Proses Algoritma Floyd
Universitas Sumatera Utara
25
2.5.1. PSEUDOCODE Pseudocode Algoritma Floyd Function fw(int [1 .. n, 1 .. n] graph) { // inisialisasi Var int [1 .. n, 1 .. n] jarak := graph Var int [1 .. n, 1 .. n] sebelum For i from 1 to n For j from 1 to n If jarak[i,j] < takhingga Sebelum[i,j] := i // perulangan utama For k from 1 to n For i from 1 to n For j from 1 to n If jarak[i,j] > jarak [i,k] + jarak[k,j] Jarak[i,j]=jarak[i,k] + jarak[k,j] Sebelum[i,j] = sebelum[k,j]
Universitas Sumatera Utara
