Suppose I have a connected graph with $n$ vertices and start in some arbitrary vertex $u$. I want to visit every vertex of the graph. I do not care about returning to where I started, and I can visit a node multiple times if needed.
What is the worst possible length of the shortest path, as a function of $n$?
EDIT: The length of a path is here counted simply as the number of times you cross and edge. So we are dealing with unweighted graphs.
On
If $T$ is a spanning tree of your graph $G$, it is easy to see that the shortest walk of $G$ is at worst as big as the shortest walk of $T$. Therefore, the worst possible shortest walks are found on trees.
Say your walk of a tree $T$ has to start from $r$. You can root a given tree arbitrarily, so assign $r$ as the root. Suppose $r$ has at least 2 children.
Let's take the walk corresponding to a depth-first search (DFS) on the tree, starting from $r$.
Each time we visit a child vertex in the DFS, we take an edge, and each time we go back to a parent vertex, we take an edge.
Let $v$ be the last vertex visited by the DFS. This vertex $v$ has to be a leaf. Now, for any vertex $w$ that does not lie on the path between $v$ and $r$, the DFS has to come back to the parent of $w$. Therefore each edge except those on the $r-v$ path are visited twice. Since there is at least one such edge, the upper bound for your problem is $2(n - 2) + 1 = 2n - 3$. You can show that this bound is tight with the star tree (which, I think, is the only tree attaining this bound).
To prove that a star is the worst case, it is perhaps best to look at a spanning tree $T$. Choose any leaf $v$. By induction, you can visit all the vertices of $T - v$ in $2(n-1) - 3$ steps. Along the way, you can visit $v$ in two steps. So you can visit all of $T$ in $2(n-1) - 3 + 2 = 2n - 3$ steps.