If you have a one or more Hamilitonian cycles in a graph, but you remove the restriction of only being able to visit a vertex once, then is it still an NP-Complete problem?
That is, is there no efficient way to find the shortest distance between all nodes?
You can find shortest distances between all nodes just by calculating $A^n$, where $A$ is the graph adjacency matrix and $n$ is number of vertices. The time required is $O(n^4)$ if doing this naively.