Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

 
Data Skripsi
 
Judul : ALGORITMA PENENTUAN LINTASAN TERPENDEK UNTUK SEMUA PASANGAN SIMPUL
Jenis : Skripsi
Penulis : Syamsul Bahri
NRP : G300326
Tanggal Lulus : 01 January 1970
Tanggal Seminar :
Tanggal Sidang :
Pembimbing : Dr. Ir. Amril Aman, M.Sc.
Drs. Prapto Tri Supriyo, M.Kom.
Ringkasan : Graf merupakan pasangan terurut (V,E), dimana V adalah himpunan tak kosong dan terbatas yang anggotanya disebut simpul (vertex) dan E adalah himpunan sisi (edge). Hubungan antara simpul dan sisi tersebut membentuk suatu jaringan (network). Selanjutnya, dari jaringan tersebut dapat ditentukan lintasan (path) yang dilalui untuk suatu pasangan simpul, tetapi masalah yang penting dalam hal ini adalah menentukan lintasan terpendek (shortest path) di antara lintasan-lintasan yang mungkin dari pasangan simpul tersebut. Hal ini menarik, karena berkaitan dengan masalah pengoptimuman, antar lain meminimumkan biaya dan efisiensi waktu yang digunakan. Ada dua kelas permasalahan lintasan terpendek, yaitu masalah lintasan terpendek satu pasangan simpul dan masalah lintasan terpendek untuk semua pasangan simpul. Beberapa algoritma telah dikembangkan untuk menyelesaikan masalah ini; masing-masing algoritma memiliki penampilan yang berbeda dalam menyelesaikan suatu permasalah tertentu. Kelebihan suatu algoritma dibandingkan dengan algoritma lainnya, antara lain ditentukan oleh struktur dan efisiensi dari algorima tersebut. Salah satu penentu efisiensi dari suatu algoritma adalah banyaknya langkah yang dibutuhkan oleh suatu program yang menggunakan algoritma tersebut dalam menyelesaiakan suatu masalah yang berukuran n. Masalah lintasan terpendek untuk semua pasangan simpul dapat antara lain dengan menggunakan algoritma Floyd atau algoritma Dijkstra secara berulang-ulang untuk setiap simpul sebagai sumber. Pada (worst case) dapat menyelesaikan masalah lintasan terpendek untuk semua pasangan simpul dengan waktu eksekusi O(n4), dimana n adalah banyaknya simpul pada suatu jaringan. Untuk masalah yang sama algoritma Floyd hanya membutuhkan waktu eksekusi O(n3). Oleh karena itu, algoritma Floyd lebih efisien dibandingakan lagoritma Dijkstra dalam menyelesaikan masalah lintasan terpendek untuk semua pasangan simpul, jika ditinjau pada kasus terburuk.

Random Quotes

Jika seseorang telah mengambil keputusan yang tidak masuk akal, berarti ia telah melakukan kesalahan.

anonim