Find the k length path that maximize a node associate metric Let's say I have :

a Graph g
v vertices. Each vertex is associated to a cost c.
A special vertex called the starter vertex or vs.

I want to find the path p of length 10 (for example), that start from vs and that maximize the sum of the 10 seens nodes costs. I need to tell you that my graph represent a road network which means it has a big diamater, and the degree of each node is never above 6 or 7. Here is an example of the kind of a graph that I have. Obviously, I got way more nodes.
A brute-force approach is to do a backtracking search starting from $s$.  Something like:
Search($s$, $n$, $S$):

If $n=1$, yield $S \cup \{s\}$ and return.  Otherwise:

For each vertex $v$ that is adjacent to $s$, do:
a. Call Search($v$, $n-1$, $S \cup \{s\}$).


If you invoke Search($vs$, $10$, $\emptyset$), this will generate all possible sets of vertices that can arise from a path of length 10; now calculate the cost of each such subset, and keep the largest one.
$6^{10}$ is about 60 million, so this might complete within a few seconds on most graphs.