White-Box Basis Path Testing of the Bellman-Ford Algorithm in a Package Delivery Application

Abdi Pandu Kusuma; Ayuna Rahim Imannur

doi:10.32664/smatika.v16i03.2576

Penulis

Abdi Pandu Kusuma Universitas Islam Balitar
Ayuna Rahim Imannur Universitas Islam Balitar

DOI:

https://doi.org/10.32664/smatika.v16i03.2576

Kata Kunci:

Basis Path Testing, Bellman-Ford Algorithm, Cyclomatic Complexity, Software Testing, White-Box Testing

Abstrak

Route determination applications based on the Bellman-Ford algorithm are widely adopted because they handle weighted graphs iteratively, including negative weights. However, testing that only checks output correctness, such as black-box testing, cannot guarantee that every execution path, particularly inside the nested loops of the edge-relaxation process, behaves as intended, so hidden logical errors may remain undetected. This study verifies the structural correctness of the nearest delivery-distance module of a web-based package delivery application that implements the Bellman-Ford algorithm, using white-box testing with the basis path technique: flowgraph construction, cyclomatic complexity calculation, independent path determination, and the design and execution of test cases. The flowgraph consists of 15 nodes, 18 edges, and 4 decision nodes, giving a cyclomatic complexity V(G) of 5, which is classified as simple and low-risk; five independent paths cumulatively cover all 18 edges. Executing the five path-based test cases, together with one supplementary test on a larger sample graph, produced outputs identical to the expected results in every case, so the implementation is structurally valid within the scope of the basis path coverage criterion. Nested loops do not by themselves raise V(G): the number of independent paths depends on the number of decision points rather than on the number of iterations, so V(G) should not be read as a proxy for the O(|V||E|) running time of Bellman-Ford. Path-based testing additionally reached three paths, namely an empty edge set, negative-weight cycle detection, and an inner loop that is never entered, which the earlier black-box testing had not exercised. The five-path test set provides a replicable structural testing procedure for similar graph algorithm implementations, to be complemented by loop and boundary testing.

Referensi

[1] R. Bellman, “On a routing problem,” Q. Appl. Math., vol. 16, no. 1, pp. 87–90, 1958, doi: 10.1090/qam/102435.

[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009.

[3] S. Farhan, S. Andryana, and N. Hayati, “Implementasi Bellman-Ford dan Floyd-Warshall dalam Menentukan Jalur Terpendek Menuju Universitas Nasional Berbasis Android,” JIPI (J. Ilm. Penelit. dan Pembelajaran Inform.), vol. 5, no. 2, pp. 123–132, 2020, doi: 10.29100/jipi.v5i2.1812.

[4] D. Wintana, D. Pribadi, and M. Y. Nurhadi, “Analisis Perbandingan Efektifitas White-Box Testing dan Black-Box Testing,” J. Larik Ldng. Artik. Ilmu Komput., vol. 2, no. 1, pp. 8–16, Jul. 2022, doi: 10.31294/larik.v2i1.1382.

[5] H. Nurfauziah and I. Jamaliyah, “Perbandingan Metode Testing antara Blackbox dengan Whitebox pada Sebuah Sistem Informasi,” J. Vis., vol. 8, no. 2, pp. 105–113, Oct. 2022.

[6] M. E. Khan, “Different approaches to white box testing technique for finding errors,” Int. J. Softw. Eng. Its Appl., vol. 5, no. 3, pp. 1–14, Jul. 2011.

[7] M. F. Londjo, “Implementasi White Box Testing dengan Teknik Basis Path pada Pengujian Form Login,” J. Siliwangi Seri Sains dan Teknol., vol. 7, no. 2, pp. 35–40, 2021, doi: 10.37058/jssainstek.v7i2.4086.

[8] M. I. Shiddiq, “Implementasi White Box Testing Berbasis Path pada Form Login Aplikasi Berbasis Web,” J. Siliwangi Seri Sains dan Teknol., vol. 8, no. 1, pp. 1–6, 2022, [Online]. Available: https://doi.org/10.37058/jssainstek.v8i2.4098

[9] Y. J. Solissa, F. Putra, A. N. Putri, and S. R. C. Nursari, “Pengujian White Box Berbasis Path pada Form Daftar Jobstreet.co.id,” KONSTELASI Konvergensi Teknol. dan Sist. Inf., vol. 3, no. 2, pp. 353–362, Dec. 2023, doi: 10.24002/konstelasi.v3i2.8287.

[10] M. G. A. Khamaeni, “Implementasi White Box Testing Berbasis Path pada Aplikasi Berbasis Web,” J. Siliwangi Seri Sains dan Teknol., vol. 9, no. 1, pp. 8–13, 2023, doi: 10.37058/jssainstek.v9i1.4109.

[11] C. T. Pratala, E. M. Asyer, I. Prayudi, and A. Saifudin, “Pengujian White Box pada Aplikasi Cash Flow Berbasis Android Menggunakan Teknik Basis Path,” J. Inform. Univ. Pamulang, vol. 5, no. 2, p. 111, 2020, doi: 10.32493/informatika.v5i2.4713.

[12] R. I. Ndaumanu, “Pengujian Sistem Informasi Perpustakaan Berbasis Website dengan Basis Path Testing,” Justek J. Sains dan Teknol., vol. 6, no. 1, p. 123, 2023, doi: 10.31764/justek.v6i1.13808.

[13] J. B. Sie, I. A. Musdar, and S. Bahri, “Pengujian White Box Testing terhadap Website Room Menggunakan Teknik Basis Path,” KHARISMA Tech, vol. 17, no. 2, pp. 45–57, 2022, doi: 10.55645/kharismatech.v17i2.235.

[14] Y. Pratiwi and L. W. Widianti, “Implementasi Whitebox Testing Dengan Teknik Basis Path Pada Pengujian Halaman Pencarian Program Promo,” J. Kecerdasan Buatan dan Teknol. Inf., vol. 4, no. 2, pp. 173–180, May 2025, doi: 10.69916/jkbti.v4i2.280.

[15] T. J. McCabe, “A complexity measure,” IEEE Trans. Softw. Eng., vol. SE-2, no. 4, pp. 308–320, Dec. 1976, doi: 10.1109/TSE.1976.233837.

[16] A. H. Watson and T. J. McCabe, “Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric,” Gaithersburg, MD, USA, 1996. doi: 10.6028/NIST.SP.500-235.

[17] I. G. S. Rahayuda and N. P. L. Santiari, “Basis path testing of iterative deepening search and Held-Karp on pathfinding algorithm,” Kursor, vol. 9, no. 2, pp. 39–48, 2018, [Online]. Available: https://doi.org/10.28961/kursor.v9i2.129

[18] C. Wei, X. Peng, Y. Yan, M. Luo, and T. Cai, “Rethinking basis path testing: Mixed integer programming approach for test path set generation,” Jan. 2026. doi: 10.48550/arXiv.2601.05463.

[19] B. Sun, L. Gong, Y. Guo, and D. Gong, “Basis path coverage testing of MPI programs based on multi-task evolutionary optimization,” Expert Syst. Appl., vol. 255, p. 124557, 2024, doi: 10.1016/j.eswa.2024.124557.

[20] C. Ebert, J. Cain, G. Antoniol, S. Counsell, and P. Laplante, “Cyclomatic complexity,” IEEE Softw., vol. 33, no. 6, pp. 27–29, Nov. 2016, doi: 10.1109/MS.2016.147.

[21] Sugiyono, Metode Penelitian dan Pengembangan (R&D). Bandung, Indonesia: Alfabeta, 2019.

[22] D. E. Tawape, A. Y. Dako, R. D. R. Dako, W. Musa, W. Ridwan, and I. Z. Nasibu, “Research and Development (RnD) pada pengembangan sistem informasi manajemen PKK Desa Dunggala Kecamatan Tibawa Kabupaten Gorontalo,” J. Tek. Elektro dan Komput. TRIAC, vol. 10, no. 2, 2023, [Online]. Available: https://doi.org/10.21107/triac.v10i2.20542

[23] M. Shepperd, “A critique of cyclomatic complexity as a software metric,” Softw. Eng. J., vol. 3, no. 2, pp. 30–36, Mar. 1988, doi: 10.1049/sej.1988.0003.

[24] P. Ammann and J. Offutt, Introduction to Software Testing, 2nd ed. Cambridge, U.K.: Cambridge University Press, 2016. [Online]. Available: https://doi.org/10.1017/9781316771273