Solving Minimum Steiner Tree on Grid using Dynamic Programming and Shortest Path First Algorithm

The Steiner Tree plays a significant role in VLSI chip modeling, routing problems, and networking, and the critical challenge is the efficient computation of the Minimum Steiner Tree due to its NP-hard nature. This problem requires solutions that are not only fast but also reliable, given the complexity and large-scale nature of practical applications, such as circuit design and network infrastructure. This paper explores the application of the Shortest Path Faster Algorithm (SPFA) to effectively solve the Minimum Steiner Tree problem, particularly in the context of the E-Olymp problem 1445-Road Network. By modeling the graph as a Steiner Tree, the SPFA algorithm demonstrated notable efficiency under the given constraints, achieving a minimum execution time of 43.0 ms on the E-Olymp platform and a maximum execution time of 93.533 ms in local testing. This performance indicates the algorithm’s ability to handle various operational scenarios effectively. The algorithm’s memory usage was significantly optimized, consuming only 3.284 MB, or approximately 5.1% of the allowed 64-MB limit. This optimization is crucial in real-world applications where resources are often limited, and memory efficiency is a key factor in successful implementation.