  The degree centrality of a node, defined as the number of nodes adjacent to
it, is often used as a measure of importance of a node to the structure of a
network. This metric can be extended to paths in a network, where the degree
centrality of a path is defined as the number of nodes adjacent to it. In this
paper, we reconsider the problem of finding the most degree-central shortest
path in an unweighted network. We propose a polynomial algorithm with the
worst-case running time of $O(|E||V|^2\Delta(G))$, where $|V|$ is the number of
vertices in the network, $|E|$ is the number of edges in the network, and
$\Delta(G)$ is the maximum degree of the graph. We conduct a numerical study of
our algorithm on synthetic and real-world networks and compare our results to
the existing literature. In addition, we show that the same problem is NP-hard
when a weighted graph is considered. Furthermore, we consider other centrality
measures, such as the betweenness and closeness centrality, showing that the
problem of finding the most betweenness-central shortest path is solvable in
polynomial time and finding the most closeness-central shortest path is
NP-hard, regardless of whether the graph is weighted or not.
