Comparative studies between minimum spanning tree algorithms and shortest paths tree algorithms

Abstract

This paper solves the problem of optimal modelling in a transmission network based on the minimum weight spanning tree method while comparing these results with those obtained by the shortest path method. More precisely, we have modelled the electrical transmission network passing through the twenty-six provinces of the Democratic Republic of Congo, based on the PRIM and KRUSKAL algorithms, which allow the calculation of the minimum weight spanning tree while comparing these results with those obtained by the DIJKSTRA algorithm, which is based on the calculation of shortest paths between the nodes of the network. The aim is to minimize the investment in defining the overall architecture of the DRC's electricity transmission network. The results of this work show that the cost of a network optimized by the minimum spanning tree algorithm is limited to a maximum of 36% of the cost of any other implementation of the same network. The savings that can be made by using the right optimization method when implementing power networks are not negligible and it is well worthwhile for decision-makers in this sector to keep this in mind.

Keywords

• minimum weight spanning tree
• pim's algorithm
• dijkstra's algorithm
• kruskal's algorithm
• graph theory
• optimal modelling