Masalah Lintasan TerpendekAZICO 1002579DWININGRUM 1002452FAIZAL 1005225GHEA 1002514MILA 1005202NADIA 1005195PUTRI 1003399

Masalah Lintasan Terpendek (Nadia Shabilla)Masalah lintasan terpendek berkaitan dengan penentuan busur-busur tak berarah yang terhubungkan dalam sebuah jaringan tak berarah yang secara bersama-sama membentuk jarak terdekat diantara sumber dan tujuan.

Beberapa masalah dalam menentukan lintasan terpendekdiantara pasangan simpul tertentu dalam suatu graph ataujaringan kerja, antara lain :

• masalah transportasi• jaringan komunikasi,• masalah pengiriman barang tidak bisa lepas dari

permasalahan jarak (waktu) dan tentunya juga masalah biaya.

• Pada masalah jaringan kerja yang harus dipecahkan adalah penentuan lintasan yang menghubungkan dua buah simpul tertentu dengan suatu jumlah nilai busur terkecil.

• Permasalahan dituntut untuk meminimisasijarak (waktu) ke tujuan yaitu dengan memilihlintasan tersingkat dengan biaya yang telahdianggarkan sehingga dapat dicapai hasil yang optimal

• Masalah menentukan urutan kegiatan dengan biaya minimum,maka nilai-nilai busur pada jaringan tersebut mewakili biaya pelaksanaan kegiatan.

• Masalah menentukan urutan kegiatan dengan waktu minimum,maka nilai-nilai busur pada jaringan tersebut mewakili waktu pelaksanaan kegiatan.

Contoh:

Dapat kita lihat pada masalah Pengirimanbarang, kita dihadapkan pada pilihan lintasanperjalanan dari Kota S (sumber) ke Kota T(tujuan).untuk sampai ke Kota T ada beberapa lintasanberbeda yang dapat dilalui dan juga biayaperjalanan yang berbeda,permasalahan yang terjadi adalah lintasanterpendek mana yang harus dipilih yangsesuai dengan biaya yang dianggarkanuntuk perjalanan tersebut agar hasil yangoptimal diperoleh.

Algoritma pencarian lintasanterpendek (Dwiningrum Prihastiwi)• Tujuan dari iterasi ke-n▫ Menentukan simpul yang menduduki urutan ke-n

dalam jaraknya tehadap simpul asal• Masalah bagi iterasi ke-n▫ Simpul terdekat ke-(n-1) dalam jaraknya terhadap

simpul asal termasuk lintasan terpendeknya danjaraknya terhadap simpul asal

• Calon untuk simpul terdekat ke-n▫ Setiap simpul terselesaikan yang secara langsung

terhubungkan dengan busur tak berarah menuju satuatau lebih simpul tak terselesaikan akan memberikansatu calon-satu simpul

ILUSTRASI

BO

EC

D

A

T22

5

41

4

3

7

4

17

5

Pengelola taman servada ingin menentukan lintasan terpendek dari pintu taman (simpul O) menuju tempat yang berpemandangan indah (simpul T) melalu sistem jalan yang diperlihatkan gambar diatas.

Penerapan algoritma untuk masalah lintasan terpendek terhadap masalah taman servada(Azico Sudhagama)

n Simpul terselesaikan

Simpul tak terselesaikan

Jumlah jarak

Simpul terdekatKe-n

Jarakmin

Busur yg dipilih

1 O A 2 A 2 OA

2,3 OA

CB

42+2=4

CB

44

OCAB

4 ABC

DEE

2+7=94+3=74+4=8

E 7 BE

5 ABE

DDD

2+7=94+4=87+1=8

DD

88

BDED

6 DE

TT

8+5=137+7=14

T 13 DT

ILUSTRASI

BO

EC

D

A

T22

5

41

4

3

7

4

17

5

SOAL 1 (Ghea Novani)

O

A

C

B

D

E

T

Lintasan terpendek yang diperoleh

Soal 1

O

A

B

D

T

5

146

SOAL 2 (Putri Noviyandari)

72

2

6

6

3

4 225

4

154 2 3

2

3

4

5

5 8O

A

B IE

H TFC

GD

Lintasan terpendek yang diperoleh

Soal 2

O C F

G

T6 2

2 7

Soal 3 (Mila Utari Apriyani)Sebuah perusahaan penyewaan mobil sedang mengembangkansebuah rencana penggantian armadanya untuk 5 tahun (1996 –2000). Tiap awal tahun, keputusan harus diambil, apakah suatu mobilharus tetap dioperasikan/diganti. Sebuah mobil harus dioperasikanpaling tidak 1 tahun dan harus diganti setelah 3 tahun.

Biaya ($)

1 2 3

1996 4000 5400 9800

1997 4300 6200 8750

1998 4800 7100 -

1999 4900 - -

SOAL 4 (Faisal Rachman) :

Cari jarak terpendek dan lintasannya dari :- 1 ke 8 - 1 ke 6

• 1 ke 8

Dengan lintasan terpendek : 1, 2, 3, 5, 6, 8 = 1 + 1 + 1 + 3 +2 = 8 Jalur terdekat dari 1 ke 8 adalah 8

• 1 ke 6

Dengan lintasan terpendek : 1, 2, 3, 5, 6 = 1 + 1 + 1 + 3 = 6 Jalur terdekat dari 1 ke 6 adalah 6

KESIMPULAN

• Lintasan terpendek ialah lintasan pada suatujaringan tak berarah yang berawal dari simpulawal ke simpul tujuan melewati simpul lainnyadengan jumlah nilai pada busur-busurnya paling kecil

• Penerapan masalah lintasan terpendek diantaralain bertujuan untuk meminimalisasi total jaraktempuh,meminimalisasi total waktu dan total biaya.