Tugas UAS Logika Algoritma-Model Graph dengan Metode Greedy

PROBLEMA DAN MODEL GRAPH DALAM METODE GREEDY

Contoh:

 TRAVELLING SALESMAN

Untuk menentukan waktu perjalanan seorang salesman  seminimal mungkin.

Permasalahan:

Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Masalahnya ia menginginkan suatu rute perjalanan dengan waktu minimal.

MODEL GRAPH :

model graph

 

Misalnya : Kantor pusat adalah simpul 1 dan misalnya ada 4 telepon umum, yg kita nyatakan sebagai simpul 2, 3, 4 dan 5 dan bilangan pada tiap-tiap ruas menunjukan waktu (dalam menit ) perjalanan antara 2 simpul .

Tentukan model graph dengan waktu perjalanan seminimal mungkin.