We investigate the shortest path improvement problems (Imp-SPs) under different norms. We explore the intricacies of enhancing existing shortest paths in a graph by strategically modifying edge weights to improve the length of the shortest path. We introduce the problem (Imp, SP, Bounded, \(l_1\) ) and its complexity, presenting a polynomial-time solution for specific cases. Furthermore, we extend the analysis to (Imp-SPs) under weighted sum Hamming distance, establishing its strong \(\mathcal {N}\mathcal {P}\) -hardness and proposing effective heuristic algorithms. This chapter culminates in an exploration of (Imp-SPs) in tree networks, offering a combinatorial algorithm tailored to exploit the tree’s structure. This work provides a significant contribution to the field, presenting both theoretical insights and practical algorithms for solving (Imp-SPs) efficiently.