Basis Path Testing of Iterative Deepening Search and Held-Karp on Pathfinding Algorithm

Main Article Content

I Gede Surya Rahayuda Ni Putu Linda Santiari


This research is a continuation of previous research, where in previous research discussed about the implementation of both methods. Implementation is done using visual basic programming language. Both methods are compared based on the results obtained. While in the current study, research is more focused on the analysis of the program flow that has been made. Evaluation is done by using basis path method, there are several processes performed on the method, such as: flowgraph, independent path, cyclomatic complexity and graph matrix. In addition to the evaluation of program flow, evaluation is also done based on program performance. Performance tests are based, time, cpu and memory. Based on the evaluation using the base path, obtained flowgraph structure and independent path different, but obtained the result of CC and Graph Matrix calculation of the same between IDS and HK method is 4. Based on evaluation in terms of performance, process the program from entering data and until getting the result,
the HK method takes a longer time than the IDS method. The IDS method takes 2.7 seconds while the HK method takes 2.8 seconds.


Download data is not yet available.

Article Details

How to Cite
RAHAYUDA, I Gede Surya; SANTIARI, Ni Putu Linda. Basis Path Testing of Iterative Deepening Search and Held-Karp on Pathfinding Algorithm. Jurnal Ilmiah Kursor, [S.l.], v. 9, n. 2, apr. 2018. ISSN 2301-6914. Available at: <>. Date accessed: 19 apr. 2019. doi:


[1] I Gede Surya Rahayuda and N. P. L. Santiari, “Implementasi dan Perbandingan Metode Iterative Deepening Search dan Held-Karp pada Manajemen Pengiriman Produk,” Sisfo ITS, vol. 6, no. 3, 2017.
[2] D. Zai, “Simulasi Rute Terpendek Lokasi Pariwisata Di Nias Dengan Metode Breadth First Search Dan Tabu Search,” J. InFact, vol. 1, pp. 30–41, 2016.
[3] Sukiswo, “Evaluasi Kinerja Algoritma Penjadwalan Weighted Round Robin Pada Wimax,” J. Tek. Elektro, pp. 58–64, 2008.
[4] I. A. A. T.S, “Penerapan Algoritma Alpha Beta Pruning Sebagai Kecerdasan Buatan Pada Game Pawn Battle,” J. Infotel, vol. 9, p. 85, 2016.
[5] S. R. Wulandari, Y. Purwanto, and B. Irawan, “Evaluasi Algoritma Pencarian Jalur Pada Aplikasi e-iTRIP Guna Menentukan Rute Pariwisata Kota Bandung Berbasis Perangkat Mobile Android,” Semin. Nas. Teknol. Inf. 2012, 2012.
[6] J. Sophia I, “Improving the Proactive Routing Protocol using Depth First Iterative Deepening Spanning Tree in Mobile Ad Hoc Network,” Int. J. Electr. Comput. Eng., vol. 7, no. 1, p. 316, 2017.
[7] Y. Irawan, “Pengujian Sistem Informasi Pengelolaan Pelatihan Kerja UPT BLK Kabupaten Kudus dengan Metode Whitebox Testing,” Sentra Penelit. Eng. dan Edukasi, vol. 9, no. 3, pp. 59–63, 2017.
[8] S. Lorena and B. Ginting, “Evaluasi Algoritma CB* Untuk Konstruksi Struktur Bayesian Network Dalam Data Mining,” Konf. Nas. Sist. dan Inform. 2008, pp. 233–239, 2008.
[9] H. Vamja, “Comparative Analysis of Different Path Finding Algorithms to Study Limitations and Progress,” Int. J. Emerg. Technol. Adv. Eng., vol. 7, no. 9, pp. 68–75, 2017.
[10] Stefano, “Algoritma IDDFS (Iterative Deepening Depth First Search),” 2018. [Online]. Available:
[11] Honainah, “Optimasi Neural Network Untuk Mendeteksi Penyakit Diabetes Dengan Algoritma Genetika,” J. Tek. Inform. STT Nurul Jadid, pp. 66–82, 2017.
[12] J. Pinto, “Learning Partial Policies to Speedup MDP Tree Search via Reduction to I.I.D. Learning,” J. Mach. Learn. Res., vol. 18, pp. 1–35, 2017.
[13] G. Goisque and C. Rapine, “Polynomial Time Algorithm for Multi-Level in Series Capacitated Lot-Sizing Problems with Constant Batch Size,” in International Workshop on Lot Sizing 2016, 2017.
[14] R. P. Kumar, “Internal and External Measures of Code Quality Impact on Refactoring,” Int. J. Civ. Eng., 2017.
[15] C. Programs, “An Analysis of Object Oriented Complexity Metrics,” Int. J. Sci. Res. Comput. Sci. Eng. Inf. Technol., vol. 2, no. 4, pp. 83–92, 2017.
[16] T. Moore, “Implementing the Held-Karp Lower Bound Algorithm in Python,” in Final Report for CM2SC 4515 – Honors Option, 2015.
[17] Stefano, “Algoritma Held-Karp,” 2018. [Online]. Available:
[18] Rohit and P. Kumar, “A Survey for the Quality Assessment of Object Oriented Software,” Int. J. Inf. Futur. Res., vol. 4, no. 9, pp. 7700–7705, 2017.
[19] C. Chekuri, “Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time ∗,” 2017.
[20] N. V. K and V. K. K. S, “Automated Test Path Generation using Genetic Algorithm,” Int. J. Eng. Res. Technol., vol. 6, no. 7, pp. 469–473, 2017.