  In this paper, we propose a deterministic algorithm that approximates the
optimal path cover on weighted undirected graphs. Based on the
1/2-Approximation Path Cover Algorithm by Moran et al., we add a procedure to
remove the redundant edges as the algorithm progresses. Our optimized algorithm
not only significantly reduces the computation time but also maintains the
theoretical guarantee of the original 1/2-Approximation Path Cover Algorithm.
To test the time complexity, we conduct numerical tests on graphs with various
structures and random weights, from structured ring graphs to random graphs,
such as Erdos-Renyi graphs. The tests demonstrate the effectiveness of our
proposed algorithm on graphs, especially those with high degree nodes, and the
advantages expand as the graph gets larger. Moreover, we also launch tests on
various graphs/networks derived from a wide range of real-world problems to
suggest the effectiveness and applicability of the proposed algorithm.
