Perpustakaan Digital ITB

Pada tesis ini telah diimplementasikan algoritma auction graf tereduksi untuk mencari lintasan terpendek dari simpul asal tunggal ke semua simpul tujuan pada suatu digraf berarah. Hasil implementasi diberi nama SPPAR. Penerapan algoritma auction graf tereduksi pada pencarian lintasan terpendek memungkinkan mencari persoalan yang lebih umum dengan adanya penambahan operasi pereduksian graf ke operasi kontraksi atau perlnacan. Operasi pereduksian graf didefinisikan sebagai penghapusan busur atau simpul tidak penting pada digraf. Pada operasi pereduksian graf, semua busur yang menuju ke simpul terminal, kecuali busur tunggal elemen lintasan, dthapus. Akibatnya, siklus proses pada siklik nol yang muncul pada penerapan algoritma auction dapat diatasi. Algoritma auction graf tereduksi memelihara lintasan ganda pada keseluruhan iterasi. Penentuan vektor nilai awal yang memenuhi kondisi complementary slackness sebagai persyaratan awal algoritma auction graf tereduksi dilakukan melalui preprosesing. Di masing-masing iterasi, operasi pereduksian graf dilakukan mendahului operasi kontraksi atau perluasan. Algoritma ini juga dilengkapi dengan pengujian apakah suatu persoalan memiliki penyelesaian atau tidak (infeasibility test). Hasil eksekusi implementasi memberikan lintasan terpendek yang sama dengan lintasan terpendek yang diperoleh dari graf asal.