1
$\begingroup$

Let's say I have :

  1. a Graph g
  2. v vertices. Each vertex is associated to a cost c.
  3. 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.

enter image description here

$\endgroup$
9
  • $\begingroup$ Have you tried dynamic programming? For every vertex, solve your problem for every length which is at most 10. $\endgroup$ Apr 22, 2021 at 13:25
  • $\begingroup$ @YuvalFilmus I do not have any experience with that but thks for the suggestion $\endgroup$
    – hans glick
    Apr 22, 2021 at 13:40
  • $\begingroup$ Can you visit a vertex multiple times? If not, don't expect an efficient algorithm for large $k$ -- solving this problem with $k=n$ and $c=1$ for every vertex is equivalent to finding a Hamiltonian path starting at $vs$, which is NP-complete. $\endgroup$ Apr 22, 2021 at 14:06
  • $\begingroup$ @j_random_hacker We can visit a vertex multiple times, but we will count its cost c only one time. I'm ok with a solution that is "ok". Do not care if the solution is not the best one. I need something somewhat close. $\endgroup$
    – hans glick
    Apr 22, 2021 at 14:11
  • 1
    $\begingroup$ Please edit your question to incorporate that information, so it is clear to people encounter it for the first time. We want people to be able to tell what is being asked by reading just the question, without having to read the comments. $\endgroup$
    – D.W.
    Apr 23, 2021 at 0:06

1 Answer 1

1
$\begingroup$

A brute-force approach is to do a backtracking search starting from $s$. Something like:

Search($s$, $n$, $S$):

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

  2. 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.

$\endgroup$
1
  • $\begingroup$ Thk you @D.W. , I try to understand your approach $\endgroup$
    – hans glick
    Apr 23, 2021 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.