Computer File

Studi dan implementasi algoritma untuk multiple pairs shortest path : Dijkstra, Floyd - Warshall, dan Dlu

Dua kelas permasalahan klasik pencarian lintasan terpendek adalah Single
Source Shortest Path (SSSP) dan All Pairs Shortest Path (APSP). Algoritma yang
biasa digunakan untuk menyelesaikan kedua permalasahan tersebut adalah algoritma
Dijkstra dan Floyd-Warshall. Penelitian ini tentang kelas permasalahan lintasan
terpendek baru yang disebut Multiple Pairs Shortest Path (MPSP). MPSP dapat
dipandang sebagai kasus umum dari SSSP dan kasus khusus dari APSP sehingga
algoritma Dijkstra dan Floyd-Warshall dapat digunakan untuk menyelesaikan
permasalahan ini. Sayangnya kedua pendekatan ini mempunyai kelemahan. Untuk itu
Wang, Ellis, dan Sokol mengusulkan sebuah algoritma yang khusus digunakan untuk
menyelesaikan MPSP yaitu algoritma DLU.
Penelitian ini bertujuan untuk membandingkan performansi algoritma
Dijkstra, Floyd-Warshall, dan DLU dalam menyelesaikan MPSP. Untuk itu
dikembangkan sebuah perangkat lunak yang mengimplementasikan ketiga algoritma
tersebut.
Untuk menjamin kebenaran perangkat lunak dilakukan pengujian fungsional
dengan pendekatan black box. Sedangkan untuk eksperimen dilakukan dengan
menggunakan sejumlah data percobaan. Berdasarkan hasil pengujian dan
eksperimenm dapat disimpulkan bahwa algoritma DLU memiliki waktu eksekusi
yang tercepat.
Two classical classes of shortest path problem are Single Source Shortest Path
(SSSP) and All Pairs Shortest Path (APSP). The most common algorithm that is
usually used to solve this problems is Dikstra and Floyd-Warshall, respectively. This
research deals with a new class of shortest path problem called Multiple Pairs Shortest
Path. MPSP can be considered as a general case of SSSP and a special case of APSP.
Therefore, Dijkstra and Floyd-Warshall algorithms can be used for solving this
problem. However, the both approaches have limitations. Wang, Ellis, dan Sokol
proposed an algorithm for solving MPSP problem which is called DLU.
The goal of this research is to compare the performance of Dijkstra, Floyd-
Warshall, dan DLU algorithms in the context of MPSP. For this purpose, a software is
developed, which implements the three algorithms.
To guarantee the correctness of the software, a black box functional test is
done; whereas for the experiment, some experiment data are used. The experiments
show that DLU algorithm has the least execution time compared to the other
algorithms.

Ketersediaan

Informasi Detail

Judul Seri

No. Panggil

KOMP SUA s/07

Penerbit

Bandung : Program Studi Ilmu Komputer - FMIPA Universitas Katolik Parahyangan., 2007

Deskripsi Fisik

ix, 6-1 p. : il. ; 30 cm

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

KOMP

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

566 - FTIS

Pernyataan Tanggungjawab

Raiman Suandi

Versi lain/terkait

Lampiran Berkas

Komentar