Solving the Shortest Total Path Length Spanning Tree Problem Using the Modified Sollin and Modified Dijkstra Algorithms

Wamiliana (Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Lampung, Bandar Lampung, 35145, Indonesia)
Reni Permata Sari (Doctoral Program, Faculty of Mathematics and Natural Sciences, Universitas Lampung, Bandar Lampung, 35145, Indonesia)
Astri Reformasari (Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Lampung, Bandar Lampung, 35145, Indonesia)
Jani Suparman (Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Lampung, Bandar Lampung, 35145, Indonesia)
Akmal Junaidi (Department of Computer Science, Faculty of Mathematics and Natural Science, Universitas Lampung, Bandar Lampung, 35145, Indonesia)

Science and Technology Indonesia
Vol. 8 No. 4 (2023): October

In a weighted connected graph, the shortest total path length spanning tree problem is a problem when we need to discover the spanning tree with the lowest total cost of all pairwise distances between its vertices. This problem is also known as the minimum routing cost spanning tree (MRCST). In this study, we will discuss the Modified Sollin and Modified Dijkstra Algorithms to solve that problem which implemented on 300 problems are complete graphs of orders 10 to 100 in increments of 10, where every order consists of 30 problems. The results show that the performance of the Modified Dijkstra and the Modified Sollin Algorithms are slightly similar. On orders 10, 20, 30, 60, and 80, the Modified Dijkstra Algorithm performs better than the Modified Sollin, however on orders 40, 50, 70, 90, and 100, the Modified Sollin performs better.