PERBANDINGAN ALGORITMA DIJKSTRA DAN FLOYD-WARSHALL DALAM PEMILIHAN RUTE TERPENDEK JALAN

PERBANDINGAN ALGORITMA DIJKSTRA DAN FLOYD-WARSHALL DALAM PEMILIHAN RUTE TERPENDEK JALAN Yusandy Aswad¹ dan Sondang Sitanggang² ¹Departemen Teknik Sipil, Universitas Sumatera Utara, Jl. Perpustakaan No.1, Kampus USU Medan Emai : [email protected] ²Sondang Sitanggang, Jl. Perpustakaan No.1, Kampus USU Medan Email: [email protected]

ABSTRAK Pencarian rute terpendek merupakan satu masalah yang banyak dibahas dalam transportasi, misalnya seorang pengguna jalan ingin melakukan perjalanan dari suatu tempat asal ke tempat tujuan, dimana dalam melakukan perjalanan tersebut pengguna tentu akan menggunakan rute terpendek dari beberapa rute yang menghubungkan asal dengan tujuannya. Dapat dilihat bahwa, penentuan rute terpendek memegang peranan penting karena dapat mengefisiensikan jarak, waktu dan biaya yang dibutuhkan untuk mencapai suatu daerah tujuan tertentu. Saat ini banyak sekali algortima yang dapat digunakan untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari rute jalan. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Dijkstra dan Floyd-Warshall. Beberapa analisa pun menunjukkan keuntungan dan kelemahan dari kedua algoritma tersebut. Hal-hal yang dibandingkan dari kedua algoritma adalah dari segi jenis masalah, spesifikasi penyelesaian masalah, kompleksitas, dan waktu algoritma sehingga akan didapat hal-hal yang menjadi kelebihan serta kelemahan dari keduanya. Sebagai contoh aplikasi Algoritma Dijkstra dan Floyd-Warshall maka rute yang akan dicoba dengan menggunakannya tersebut adalah Jalan Sei Padang menuju Lapangan Merdeka. Dari hasil analisis dengan parameter waktu tempuh didapat rute yang berbeda dari kedua algoritma dimana dengan metode algoritma Floyd-Warshall didapat rute yang paling pendek waktu tempuhnya yaitu rute III Jl. Sei Padang – Jl. KH. Wahid Hasyim – Jl. Gajah Mada – Jl. S. Parman - Jl. Kapt. Maulana Lubis – Jl. Raden Saleh - Lap. Merdeka. Dimana jumlah waktu tempuhnya sebesar 933 detik atau sama dengan 15 menit 33 detik. Kata kunci : Algoritma Dijkstra, Floyd-Warshall, waktu tempuh, shortest path.

1.

PENDAHULUAN

Sebagai daerah yang memiliki perkembangan yang begitu pesat dalam kegiatan ekonomi, sosial, budaya dan kegiatan lainnya. Maka hal yang wajar apabila aktivitas penduduk kota Medan relatif tinggi seiring dengan kebutuhan perjalanannya. Kebutuhan akan perjalanan ini menuntut adanya pemilihan rute terpendek dari suatu daerah ke daerah lainnya sehingga dapat mengefisiensikan jarak, waktu, dan biaya yang dibutuhkan untuk mencapai daerah tujuan tersebut. Dalam melakukan aktivitas perjalanannya, setiap pelaku perjalanan akan mencoba mencari rute terbaik yang meminimkan biaya perjalanannya. Selain untuk mengefisiensikan jarak, waktu, dan biaya yang dibutuhkan untuk menuju suatu tempat tujuan tertentu ataupun sebaliknya bagi pengguna/pelaku perjalanan, juga dapat mengurangi dampak kemacetan dengan pendistribusian/sebaran pergerakan perjalanan mengingat bahwa dewasa ini jaringan jalan di kota Medan mengalami permasalahan transportasi yang sangat kritis seperti kemacetan lalu lintas yang disebabkan oleh tingginya tingkat urbanisasi, pertumbuhan ekonomi, kepemilikan kenderaan, serta berbaurnya peranan fungsi jalan arteri, kolektor, dan lokal sehingga jaringan jalan tidak dapat berfungsi secara efisien. ketidaklancaran arus lalu lintas ini menimbulkan biaya tambahan, tundaan, kemacetan dan bertambahnya polusi udara dan suara. Tujuan dari studi ini adalah melakukan review pada teori rute terpendek algoritma Dijkstra dan algoritma FloydWarshall dengan aplikasi penggunaan di lapangan sekaligus menganalisis kelebihan dan kelemahan dari kedua algoritma.

2.

POLA PEMILIHAN RUTE JARINGAN JALAN

Terdapat empat faktor yang mempengaruhi seseorang dalam pemilihan rute (Warpani, 1990) a.

Waktu perjalanan

SEMINAR NASIONAL-1 BMPTTSSI - KoNTekS 5 Universitas Sumatera Utara, Medan - 14 Oktober 2011

T-161

Transport b. c. d.

Biaya perjalanan Kenyamanan Tingkat pelayanan

Rute terbaik bagi pemakai jalan dapat diartikan sebagai rute tercepat dan termurah. Menurut (Hutchinson, 1974) menyatakan bahwa hambatan perjalanan adalah sebagai faktor utama yang berpengaruh dalam pemilihan rute. Makin tinggi hambatan di suatu jalan maka semakin sedikit lalu lintas yang menggunakan jalan tersebut dan sebaliknya.

3.

METODE ALGORITMA

Algoritma dijkstra Dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif. Elemen-elemen algoritma Dijkstra adalah: 1. Himpunan kandidat, C Himpunan ini berisi elemen-elemen yang memiliki peluang untuk membentuk solusi. Pada solusi lintasan terpendek himpunan kandidat ini adalah himpunan simpul pada lintasan tersebut. 2. Himpunan solusi, S Himpunan ini berisi solusi dari permasalahan yang diselesaikan dan elemennya terdiri dari elemen dalam kandidat namun tidak semuanya atau dengan kata lain himpunan solusi ini adalah bagian dari himpunan kandidat. 3. Fungsi seleksi Fungsi seleksi adalah fungsi yang akan memilih setiap kandidat yang akan memungkinkan akan menghasilkan solusi optimal pada setiap langkahnya. 4. Fungsi kelayakan Fungsi kelayakan akan memeriksa apakah suatu kandidat yang terpilih (terseleksi) melanggar congstraint atau tidak. Apabila kandidat melanggar constraint maka kandidat tidak akan dimaksudkan kedalam himpunan solusi. 5. Fungsi Objektif Fungsi objektif akan memaksimalkan atau meminimalkan nilai solusi. Tujuannya adalah memilih satu saja solusi terbaik dari masing-masing anggota himpunan solusi.

Algoritma Floyd-Warshall, Algoritma Floyd-Warshall adalah sebuah algoritma analisis graf untuk mencari bobot minimum dari graf berarah. Dalam satu kali eksekusi algoritma, akan didapatkan jarak sebagai jumlah bobot dari lintasan terpendek antar setiap pasang simpul tanpa memperhitungkan informasi mengenai simpul-simpul yang dilaluinya. Algoritma ini yang juga dikenal dengan nama Roy-Floyd. Dalam pengertian lain Algoritma Floyd-Warshall adalah suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu. (Novandi.R.A.D., 2007) Algoritma Floyd-Warshall ini akan memilih satu jalur terpendek dan teraman dari beberapa alternatif jalur yang telah dihasilkan dari proses kalkulasi. (Sukrisno A.T dan Rachman A., 2007)

Karakteristik Algoritma Floyd-Warshall Beberapa karakteristik yang dimiliki oleh algoritma Floyd-Warshall antara lain: 1. Persoalan dibagi atas beberap tahap, yang setiap tahapnya hanya akan diambil satu keputusan. 2. Masing-masing tahap terdiri atas sejumlah status yang saling berhubungan dengan status tersebut. Status yang dimaksud di sini adalah berbagai kemungkinan masukan yang ada pada tahap tersebut. 3. Ketika masuk ke suatu tahap, hasil keputusan akan transformasi. 4. Bobot pada suatu tahap akan meningkat secara teratur seiring bertambahnya jumlah tahapan. 5. Bobot yang ada pada suatu tahap tergantung dari bobot tahapan yang telah berjalan dan bobot pada tahap itu sendiri. 6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan pada tahap sebelumnya. 7. Terdapat hubungan rekursif yang menyatakan bahwa keputusan terbaik dalam setiap status pada tahap k akan memberikan keputusan terbaik untuk setiap status pada tahap k + 1. 8. Prinsip optimalitas berlaku pada persoalan yang dimaksud.

T-162


Transport

4.

ANALISA WAKTU PERJALANAN

Waktu tempuh perjalanan yang diperoleh dari hasil survei sebelumnya di lapangan dari Jl. Sei Padang sebagai asal dan Pusat Kota Medan atau Kawasan Lapangan Merdeka sebagai tujuan, dikompilasi dalam bentuk tabulasi berdasarkan segmen/ruas setiap rute jaringan jalan yang disurvei. Dari hasil survey yang telah dilakukan sebelumnya diperoleh lima (5) rute yang umumnya ditempuh oleh pengguna jalan raya dalam melakukan perjalanannya dari Jl. Sei Padang ke Pusat Kota Medan, dan beberapa rute lain dengan intensitas/jumlah pengguna lebih sedikit dari lima (5) rute tersebut (dapat dilihat pada Gambar 4.1 s/d 4.5). lima (5) jenis rute tersebut antara lain : 1. Rute I

: Jl. Sei Padang – Jl. Patimura – Jl. Hassanuddin- Jl. Mojopahit – Jl. Gajah Mada – Jl. S. Parman – Jl. Kapt. Maulana Lubis – Jl. Raden Saleh - Lap. Merdeka . 2. Rute II : Jl. Sei Padang – Jl. Iskandar Muda – Jl. Gajah Mada – Jl. S. Parman – Jl. Kapt. Maulana Lubis - Jl. Raden Saleh – Lap. Merdeka. 3. Rute III : Jl. Sei Padang – Jl. KH. Wahid Hasyim – Jl. Gajah Mada – Jl. S. Parman - Jl. Kapt. Maulana Lubis – Jl. Raden Saleh - Lap. Merdeka. 4. Rute IV : Jl. Sei Padang - Jl. Patimura – Jl. Sudirman – Jl. Diponogoro – Jl. Pengadilan – Jl. Raden Saleh – Lap. Merdeka. 5. Rute V : Jl. Sei Padang - Jl. Patimura – Jl. Monginsidi – Jl. DR. Cipto - Jl Sudirman - Jl. Diponogoro – Jl. Pengadilan – Jl. Raden Saleh – Lap. Merdeka. Waktu perjalanan yang diperoleh dari hasil survei lalu lintas di lapangan meliputi waktu perjalanan pada saat jam sibuk (onpeak). Tabel 4.1 waktu Perjalanan Rata-Rata Rute I

No. 1 2 3 4 5 6 7 8

Nama Segmen Jl. Sei Padang Jl. Pattimura Jl. Hassanuddin Jl. Mojopahit Jl. Gajah Mada Jl. S. Parman Jl. Maulana Lbs Jl. Raden Saleh

Panjang Lintas Tempuh (meter) 50 1430 100 200 90 1000 320 500

Lalu lintas Tempuh (detik) 39 393 31 22 28 193 180 116

Jumlah Waktu Hambatan (detik) 25 50 30 40 18

Jenis Hambatan Traffic Light Traffic Light Sekolah Traffic Light Traffic Light

Tabel 4.2 Waktu Perjalanan Rata-Rata Rute II

No. 1 2 3 4 5 6

Panjang Lintas Nama Segmen Tempuh (meter) Jl. Sei Padang 50 1460 Jl. Iskandar Muda Jl. Gajah Mada 650 Jl. S. Parman 1000 Jl. Maulana Lubis 320 Jl. Raden Saleh 500 3980 Jumlah

Lalu lintas Tempuh (detik) 39 330 110 193 180 116 969

Jumlah Waktu Hambatan (detik) 25 75 18 30 40 18 207

Jenis Hambatan Traffic Light Traffic Light & Pasar sekolah sekolah Traffic Light Traffic Light

Tabel 4.3 Waktu Perjalanan Rata-Rata Rute III

No. 1 2 3 4 5 6

Panjang Lintas Nama Segmen Tempuh (meter) Jl. Sei Padang 1590 Jl. K.W. Hasyim Jl. Gajah Mada 1100 Jl. S. Parman 1000 Jl. Maulana Lubis 320 Jl. Raden Saleh 500 Jumlah 4510

Lalu lintas Tempuh (detik) 240 204 193 180 116 933


Jumlah Waktu Hambatan (detik) 55 58 30 40 18 201

Jenis Hambatan Traffic Light Traffic Light & Pasar sekolah sekolah Traffic Light Traffic Light

T-163

=

Transport Tabel 4.4 Waktu Perjalanan Rata-Rata Rute IV

No. 1 2 3 4 5 6

Nama Segmen Jl. Sei Padang Jl. Pattimura Jl. Sudirman Jl. Diponogoro Jl. Pengadilan Jl. Raden Saleh Jumlah

Lalu lintas Tempuh (detik) 39 228 222 362 97 116 1064

Panjang Lintas Tempuh (meter) 50 730 760 1200 400 500 3640

Jumlah Waktu Hambatan (detik) 25 50 106 28 18 227

Jenis Hambatan Traffic Light Traffic Light Traffic Light Traffic Light Traffic Light Traffic Light

Tabel 4.4 Waktu Perjalanan Rata-Rata Rute IV No.

Nama Segmen

Panjang Lintas Tempuh (meter)

1 2 3 4 5 6 7 8

Jl. Sei Padang Jl. Pattimura Jl. Mongonsidi Jl. Dr. Cipto Jl. Sudirman Jl. Diponegoro Jl. Pengadilan Jl. Raden Saleh Jumlah

50 200 560 700 220 1200 400 500 3830

Lalu lintas Jumlah Waktu Tempuh Hambatan (detik) (detik) 39 64 146 121 53 362 97 116 998

25 15 20 32 106 28 18 244

Jenis Hambatan Traffic Light Traffic Light Traffic Light Sekolah & Traffic Light Traffic Light Traffic Light Traffic Light

G

180 dtk

( Daerah Tujuan ) 116 dtk

B

H

193 dtk 97 dtk

T

D

153 dtk

28 dtk O F

E

94 dtk

82 dtk

22 dtk N

M

R

113 dtk 140 dtk

Jl. P atim ura

165 dtk S

96 dtk c

J

169 dtk

L

P

ura tim Pa Jl.

126 dtk

53 dtk Q

121 dtk K

JL. Sei Padang ( Daerah Asal )

A

I

146 dtk

U

Gambar rute jalan dari simpang sei padang ke Lapangan Merdeka

T-164


Transport

Analisis pencarian rute terpendek berdasarkan waktu tempuh Ø Metode Dijkstra Tabel 4.2 Hasil Iterasi ke-1 Node Status Bobot Prodecessor

A 1 -

B 0 -

C 0 100 A

D 0 -

E 0 -

F 0 -

G 0 -

Node Status Bobot Prodecessor

A 1 -

B 0 -

C 0 100 A

D 0 -

E 0 -

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 0 240 C

E 0 -

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 0 240 C

E 0 -

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 0 240 C

E 0 415 J

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 0 334 D

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 0 334 D

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 0 334 D

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 0 -

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 0 -

G 0 -

H 0 -

I 0 39 A

J 0 -

K 0 -

L 0 -

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 -

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 -

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 -

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 249 K

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 249 K

M 0 -

N 0 -

O 0 -

P 0 -

Q 0 -

R 0 -

S 0 -

T 0 -

U 0 249 K

M 0 -

N 0 -

O 0 -

P 0 370 U

Q 0 -

R 0 -

S 0 -

T 0 -

U 1 249 K

M 0 431 L

N 0 -

O 0 -

P 0 436 L

Q 0 -

R 0 -

S 0 -

T 0 -

U 1 249 K

M 0 431 L

N 0 -

O 0 416 E

P 0 370 U

Q 0 -

R 0 -

S 0 -

T 0 -

U 1 249 K

N 0 -

O 0 416 E

P 1 370 U

Q 0 423 P

R 0 -

S 0 -

T 0 -

U 1 249 K

Tabel 4.3 Hasil Iterasi ke-2 H 0 -

I 1 39 A

J 0 165 I

K 0 103 I

L 0 -


I 1 39 A

J 0 165 I

K 0 103 I

L 0 -


I 1 39 A

J 0 165 I

K 1 103 I

L 0 267 K


I 1 39 A

J 1 165 I

K 1 103 I

L 0 267 K


I 1 39 A

J 1 165 I

K 1 103 I

L 0 267 K


I 1 39 A

J 1 165 I

K 1 103 I

L 0 267 K


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K


I 1 39 A

J 1 165 I


K 1 103 I

L 1 267 K

M 0 431 L

T-165

Transport

Tabel 4.12 Hasil Iterasi ke-11 Node Status Bobot Prodecessor

A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 0 444 O

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 0 444 O

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 0 444 O

G 0 -


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 0 705 F


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 0 705 F


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 0 705 F


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 0 705 F


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 1 705 F


A 1 -

B 0 -

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 1 705 F


A 1 -

B 0 998 H

C 1 100 A

D 1 240 C

E 1 334 D

F 1 444 O

G 1 705 F

H 0 -

I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 0 431 L

N 0 -

O 1 416 E

P 1 370 U

Q 0 423 P

R 0 -

S 0 -

T 0 -

U 1 249 K

N 0 -

O 1 416 E

P 1 370 U

Q 1 423 P

R 0 -

S 0 519 Q

T 0 -

U 1 249 K

N 0 462 M

O 1 416 E

P 1 370 U

Q 1 423 P

R 0 -

S 0 519 Q

T 0 -

U 1 249 K

N 0 462 M

O 1 416 E

P 1 370 U

Q 1 423 P

R 0 -

S 0 519 Q

T 0 -

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 0 -

S 0 519 Q

T 0 -

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 0 632 S

S 1 519 Q

T 0 -

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 1 632 S

S 1 519 Q

T 0 785 R

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 1 632 S

S 1 519 Q

T 0 785 R

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 1 632 S

S 1 519 Q

T 1 785 R

U 1 249 K

N 1 462 M

O 1 484 N

P 1 370 U

Q 1 423 P

R 1 632 S

S 1 519 Q

T 1 785 R

U 1 249 K


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 0 431 L


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L


I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L

Tabel 4.19 Hasil Iterasi ke-18 H 0 885 G

I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L

Tabel 4.20 Hasil Iterasi ke-19 H 0 882 T

I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L

Tabel 4.21 Hasil Iterasi ke-20 H 0 882 T

I 1 39 A

J 1 165 I

K 1 103 I

L 1 267 K

M 1 431 L

Hasil Aplikasi: Dari aplikasi algoritma Dijkstra dalam penentuan rute terpendek jaringan jalan dari Sei Padang ka Pusat Kota Medan berdasarkan waktu tempuh, diperoleh rute V sebagai terpendek yaitu : Jl. Sei Padang - Jl. Patimura – Jl. Monginsidi – Jl. DR. Cipto - Jl Sudirman - Jl. Diponogoro – Jl. Pengadilan – Jl. Raden Saleh – Lap. Merdeka. Dimana jumlah waktu tempuhnya sebesar 998 detik atau sama dengan 16 menit 38 detik.

T-166


Transport Ø Metode Floyd-Warshall Tahap II

Tahap I

Node Tujuan

Node Asal

Node Tujuan

Solusi Optimum f1(s) X1 39 A 100 A `

S1 I C

S2 K J D

Tahap III

Node Asal f2(s) I C ∞ 103 ∞ 168 ∞ 240

Solusi Optimum f2(s) X2 103 I 168 C 240 I

Tahap IV

Node Tujuan

Node Tujuan

Node Asal

S3

K 249 267 ∞

U L E

f3 ( s ) J ∞ ∞ 418

D ∞ ∞ 334

Solusi Optimum f3(s) X3 249 K 267 K 334 D

Tahap V

S4 P M O

Node Asal U 370 ∞ ∞

f4 ( s ) L 436 412 ∞

E ∞ ∞ 416

Solusi Optimum f4(s) X4 370 L 412 L 416 E

Tahap VI

Node Tujuan

Node Tujuan

Node Asal

S5

P 423 ∞ ∞

Q N F

f5 ( s ) M ∞ 443 ∞

O ∞ ∞ 444

Solusi Optimum f5(s) X5 423 P 443 M 444 O

Tahap VII

S6 S O G

Node Asal Q 519 ∞ ∞

f6 ( s ) N ∞ 465 ∞

F ∞ ∞ 637

Solusi Optimum f6(s) X6 519 Q 465 N 637 F

Tahap VIII

Node Tujuan

Node Tujuan

Node Asal

S7

G 817 ∞ ∞

H F R

f6 ( s ) O ∞ 493 ∞

S ∞ ∞ 632

Solusi Optimum f7(s) X7 817 Q 493 N 632 F

Tahap IX

H

B G T

H 933 ∞ ∞

f8 ( s ) F ∞ 1186 ∞

R ∞ ∞ 785

Solusi Optimum f8(s) X8 933 H 1186 F 785 R

Tahap X

Node Tujuan S9

S8

Node Asal

Node Asal f3 ( s ) G 1366

T 882

Solusi Optimum f9(s) X9 882 T

Node Tujuan S 10 B

Node Asal Solusi Optimum f 10 ( s ) X 10 998 H

Hasil Aplikasi: Dari aplikasi algoritma Floyd-Warshall dalam penentuan rute terpendek jaringan jalan dari Sei Padang ka Pusat Kota Medan berdasarkan waktu tempuhnya, diperoleh rute III sebagai rute terpendek, yaitu : Jl. Sei Padang – Jl. KH. Wahid Hasyim – Jl. Gajah Mada – Jl. S. Parman - Jl. Kapt. Maulana Lubis – Jl. Raden Saleh - Lap. Merdeka. Dimana jumlah waktu tempuhnya sebesar 933 detik.

5. 1.

PERBANDINGAN ALGORITMA DIJKSTRA DENGAN FLOYD-WARSHALL Algoritma Dijkstra yang menerapkan strategi greedy, yaitu pada setiap langkah, ambil sisi yang berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang terpendek diantara semua lintasannya ke simpul-simpul yang belum terpilih. Ternyata tidak selalu berhasil memberikan solusi optimum untuk kasus penentuan lintasan terpendek.


T-167

Transport 2. 3. 4.

5. 6.

Algoritma Floyd-Warshall yang menerapkan pemrograman dinamis lebih menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasan terpendek. Berdasarkan masalah yang dapat diselesaikan Algoritma Dijkstra untuk masalah Single Source Shortest Path, Algoritma Floyd-Warshall untuk masalah All Pairs Shortest Path. Keputusan yang diambil pada tiap tahap pada Algoritma Dijkstra hanya berdasarkan pada informasi yang terbatas sehingga nilai optimum yang diperoleh pada saat itu tidak memikirkan konsekuensi yang akan terjadi kedepannya, sementara Algoritma Floyd-Warshall melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu. Dari waktu penyelesaian masalah algoritma Dijkstra mampu meyelesaikan masalah lebih cepat bila dibandingkan dengan algoritma Floyd-Warshall. Dari segi kerumitan algoritma Dijkstra jauh lebih sederhana dibandingkan dengan algoritma Floyd-Warshall. Untuk lebih jelasnya kelebihan Dijkstra dan Floyd-Warshall dapat dilihat dalam tabel berikut: Tabel 5 Perbandingan Algoritma Dijkstra dan Floyd-Warshall

7.

Perbandingan Algoritma Dijkstra Floyd-Warshall Faktor Pembanding single all-pairs Jenis Cukup Sederhana Rumit Kerumitan Sangat cepat cepat Kecepatan Solusi Solusi tidak selalu terbaik Solusi terbaik Tidak memikirkan konsekuensi Memikirkan konsekuensi Konsekuensi Dari table perbandingan kedua algoritma tersebut disimpulkan algoritma Floyd-Warshall merupakan algoritma terbaik.

DAFTAR PUSTAKA Ching (1905). Arsitektur bentuk dalam ruang dan susunannya. Penerbit Institute Teknologi Bandung Handaka, M. S. (2010), Perbandingan Algoritma Dijkstra (Greedy) dan Floyd-Warshall (Dynamic Programing) Dalam Pengaplikasian Lintasan Terpendek pada Link-State Routing Protocol. Teknik Informatika Bandung. Bandung http:/www.informatika.org/rinaldi/STMK/makalah2010/makalahstma2010-040.pdf. Tanggal akses : 08 Januari 14.00 Kamayudi, Apri. (2008), Study dan Implementasi Algoritma Dijkstra, Bellman Ford dan Floyd-Warshall Dalam Menangani Masalah Terpendek Dalam Graf. Teknik Informatika Bandung. Bandung http://www.scribd.com/38876049/study-dan-implementasi-algoritma-dijkstra.pdf Tanggal akses : 08 Januari 14.00 Khisty, C Jotin and Lall, B. Kent, (2006), Dasar-dasar Rekayasa Transportasi. Jilid I. Penerbit Erlangga. Jakarta Khisty, C Jotin and Lall, B. Kent, (2006), Dasar-dasar Rekayasa Transportasi. Jilid II. Penerbit Erlangga. Jakarta Miro, Fidel (2002), Perencanaan Transportasi. Penerbit Erlangga. Jakarta Munawar, Ahmad. (1995), Dasar-dasar Teknik Transportasi. Penerbit Beta Offset. Yogyakarta Morlok (1991). Perencanaan Transportasi. Penerbit Erlangga. Jakarta Novandi, R. A. D. (2007), Perbandingan Algoritma Dijkstra dengan Algoritma Floyd-Warshall Dalam Penentuan Lintasan Terpendek. Teknik Informatika Bandung. Bandung http://www.informatika.org/rinaldi/STMK/2006-2007/makalah-2007/makalahSTMK2007-021.pdf. Tanggal akses : 08 Januari 14.00 Ognem (1984). Kemacetan dan Kecelakaan dan Gangguan Lalulintas. Jurnal Pradhana. A, Bayu. (2009). Studi dan Implementasi Persoalan Lintasan Terpendek Suatu Graf dengan Algoritma Dijkstra dan Bellamn-Ford. Teknik Informatika Bandung. Bandung Rachmah. N. F. (2008). Aplikasi Algoritma Dijkstra Dalam Pencarian Lintasan Terpendek Graf. Teknik Informatika Bandung. Bandung http://www.informatika.org/rinaldi/matdis/2007-2008makalah/makalahIF1253-708.pdf. Tanggal akses : 08 Januari 14.00 Sitanggang, Meijer. (2011). Pemilhan Rute Terpendek dengan Menggunakan Metode GIS dan Floyd-Warshall. Tugas Akhir. Departemen Teknik Sipil USU Tamin, O. Z (1997). Perencanaan dan Pemodelan Transportasi. Penerbit Institute Teknologi Bandung. Bandung Tamin, O. Z (2000). Perencanaan dan Pemodelan Transportasi. Penerbit Institute Teknologi Bandung. Bandun

T-168


PERBANDINGAN ALGORITMA DIJKSTRA DAN FLOYD-WARSHALL DALAM PEMILIHAN RUTE TERPENDEK JALAN

Recommend Documents