# A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem

arXiv: https://arxiv.org/abs/2005.04095 · HTML: https://mlsanity.com/paper/2005.04095/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2020.

## Built on by (most cited first, 1 of 1)

- [A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization](https://mlsanity.com/paper/2102.09954/) (2021)

## Abstract (arXiv)

Randomized Greedy Algorithms (RGAs) are interesting approaches to solve problems whose structures are not well understood as well as problems in combinatorial optimization which incorporate the random processes and the greedy algorithms. This paper introduces a new algorithm that combines the major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the Clustered Shortest-Path Tree Problem (CluSPT). In our algorithm, SPTA is used to determine the shortest path tree in each cluster while the combination between characteristics of the RGAs and search strategy of SPTA is used to constructed the edges connecting clusters. To evaluate the performance of the proposed algorithm, Euclidean benchmarks are selected. The experimental investigations show the strengths of the proposed algorithm in comparison with some existing algorithms. We also analyze the influence of the parameters on the performance of the algorithm.