CONTOH PEMBAHASAN SHORTEST PATH

SOAL: 

Badan Antariksa telah menjadwalkan penelitian dan pengembangan kendaraan angkasa luar baru yang berlangsung dalam empat tahap. setiap tahap melibatkan berbagai keputusan mengenai desain kendaraan.

Pada tahap 1, terdapat 3 Pilihan (1A, 1B, dan 1C) dengan biaya masing-masing $1 juta, $1.5 juta, $2juta.

Untuk tahap 2, terdapat 4 pilihan (2A, 2B, 2C, dan 2D) masing-masing dengan biaya $4juta, $3juta, $9juta, dan $7juta.

Opsi 2 A hanya akan diikuti jika salah satu dari opsi 1A dan 1C terpilih ditahap 1, 2B hanya bisa mengikuti 1A atau 1B, 2C hanya bisa mengikuti 1A dan 2 D dapat terpilih terlepas dari pilihan yang dibuat dalam fase 1.

Pada fase 3 terdapat 3 opsi yaitu 3A, 3B, dan 3C dengan biaya masing-masing $7juta, $5juta, dan $3juta.

Opsi 3A dapat mengikuti setiap pilihan yang dibuat dalam fase 2 . 3B dapat mengikuti 2A, 2B, 2D. 3C dapat mengikuti 2C atau 2D.

Pada tahap 4, terdapat 2 opsi yaitu 4A dan 4B, dengan biaya masing-masing $3juta dan $4juta dan salah satu dari kedua opsi ini bisa dipilih terlebih terlepas dari pilihan yang dibuat dalam fase 3.

Pertanyaan:

1. Buat gambar jaringan dari persoalan diatas

2. Tentukan metode yang digunakan (minimal spanning tree, TSP, Shortest Path, atau Maximal Flow)

3. Bagaimana cara badan antariksa melakukan seleksi setiap opsi yang ada jika diharapkan total biaya yang digunakan minimal?

Jawab:

1A – 2A – 3A – 4A = 1 + 4 + 7 + 3 = 15

1A – 2A – 3B – 4A = 1 + 4 + 5 + 3 = 13

1A – 2A – 3A – 4B = 1 + 4 + 7 + 4 = 16

1A – 2A – 3B – 4B = 1 + 4 + 5 + 4 = 14

1A – 2B – 3A – 4A = 1 + 3 + 7 + 3 = 14

1A – 2B – 3A – 4B = 1 + 3 + 7 + 4 = 15

1A – 2B – 3B – 4A = 1 + 3 + 5 + 3 = 12

1A – 2B – 3B – 4B = 1 + 3 + 5 + 4 = 13

1A – 2C – 3A – 4A = 1 + 9 + 7 + 3 = 20

1A – 2C – 3C – 4A = 1 + 9 + 3 + 3 = 16

1A – 2C – 3A – 4B = 1 + 9 + 7 + 4 = 21

1A – 2C – 3C – 4B = 1 + 9 + 3 + 4 = 17

1A – 2D – 3A – 4A = 1 + 7 + 7 + 3 = 18

1A – 2D – 3A – 4B = 1 + 7 + 7 + 4 = 19

1A – 2D – 3B – 4B = 1 + 7 + 5 + 4 = 17

1A – 2D – 3C – 4A = 1 + 7 + 3 + 3 = 14

1A – 2D – 3C – 4B = 1 + 7 + 3 + 4 = 15

1B – 2B – 3A – 4A = 1,5 + 3 + 7 + 3 = 14,5

1B – 2B – 3A – 4B = 1,5 + 3 + 7 + 4 = 15,5

1B – 2B – 3B – 4A = 1,5 + 3 + 5 + 3 = 12,5

1B – 2B – 3B – 4B = 1,5 + 3 + 5 + 4 = 13,5

1B – 2D – 3A – 4A = 1,5 + 7 + 7 + 3 = 18,5

1B – 2D – 3A – 4B = 1,5 + 7 + 7 + 4 = 19,5

1B – 2D – 3C – 4A = 1,5 + 7 + 3 + 3 = 14,5

1B – 2D – 3C – 4B = 1,5 + 7 + 3 + 4 = 15,5

1C – 2A – 3A – 4A = 2 + 4 + 7 + 3 = 16

1C – 2A – 3A – 4B = 2 + 4 + 7 + 4 = 17

1C – 2A – 3B – 4A = 2 + 4 + 5 + 3 = 14

1C – 2A – 3B – 4B = 2 + 4 + 5 + 4 = 15

1C – 2D – 3A – 4A = 2 + 7 + 7 + 3 = 19

1C – 2D – 3A – 4B = 2 + 7 + 7 + 4 = 20

1C – 2D – 3B – 4A = 2 + 7 + 5 + 3 = 17

1C – 2D – 3B – 4B = 2 + 7 + 5 + 4 = 18

1C – 2D – 3C – 4A = 2 + 7 + 3 + 3 = 15

1C – 2D – 3C – 4B = 2 + 7 + 3 + 4 = 16

•Shortest Path

•Bukan: Spanning Tree karena pada tree graph tak berarah dan tidak ada simpul awal atau simpul akhir contoh: panjang kabel listrik terpendek yang dapat mensuplai kebutuhan listrik tiap rumah

•Bukan: TSP karena pada dasarnya TSP digunakan untuk menentukan sirkuit terpendek dari suatu simpul keseluruh simpul lain tepat satu kali dan kembali ke simpul awal atau asal

•Bukan: Maximum Flow karena maximum flow digunakan untuk menghitung nilai maksimumgraph, contohnya: menghitung waku sampai tujuan dengan banyaknya kemacetan.