2
$\begingroup$

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.

To summarize, I built an undirected graph with edges representing possible moves of 1's, 10's, 100's, etc to get from one value to another.

public static UndirectedGraph<int, IEdge<int>> GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph<int, IEdge<int>>();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i <= 10000; i++)
    {
        for (int j = i+1; j <= 10000; j++)
        {
            // only add edges if difference is base of 10
            if (j - i == 1 || j - i == 10 || j - i == 100 || j - i == 1000)
            {
                graph.AddVerticesAndEdge(new UndirectedEdge<int>(i, j));
            }
        }
    }
    return graph;
}

So, the minimum distance from 46 to 121 is 8 steps/moves:

  • add 100 (146) - 1 move
  • subtract 10 (136) - 1 move
  • subtract 10 (126) - 1 move
  • subtract 1 five times (121) - 5 moves

Let's say the minimum number of steps through the graph has to be greater than 8 e.g. 10, 15, etc.

For example, a game application could stipulate that you must move at least 11 times in the problem above, so a possible answer could be:

  • all steps above (8 moves)
  • add 1 - (9)
  • subtract 1 - (10)
  • add 1 - (11) (we're at the minimum number of moves here, but we're at 122)
  • subtract 1 - (12) (correct answer)

So, these "dummy" moves are allowed, but aren't there scenarios where simple dummy moves may outnumber a shorter path to the answer?

I think I found an Eppstein implementation in C# that should give k-shortest paths, but can anyone explain the meaning of the vertices with two letters? e.g. What does the vertex "A,E" mean, and how can it have a single edge between "B,I"?

g.CreateEdges("A,E", "B,I", 20, "alpha");

What if I had to specify an odd or even number of moves?

Can this be done with the existing graph, or is there another graph structure that would support it? Weights, directions? Could I build the graph differently to describe the criteria e.g. not adding edges until certain number of edges exist back to the source, but then I would need Dijkstra on every iteration at build time

$\endgroup$
  • $\begingroup$ "The minimum number of steps through the graph has to be greater than e.g. 10". For example, if we cannot reach the destination number in 11 or 12 steps but we can in 13 steps, then 13 is the answer. Right? $\endgroup$ – Apass.Jack Jun 12 at 3:16
  • $\begingroup$ @Apass.Jack I'm not sure that's correct--the graph as generated by the code is good for doing a simple Dijkstra search for shortest path, but my application (a game) may have rules that the player must make a minimum number of moves e.g. if the shortest path is technically 8, the game might stipulate they have to make at least 10 moves. I'm not sure if the current graph supports it with some kind of search, weights, directions, etc... $\endgroup$ – David Fox Jun 12 at 3:18
  • 1
    $\begingroup$ "If the shortest path is technically 8, the game might stipulate they have to make at least 10 moves." And then if we cannot reach the destination in 10, 11 or 12 steps but we can in 13 steps, then the player can play that 13 steps. Right? $\endgroup$ – Apass.Jack Jun 12 at 3:32
  • $\begingroup$ @Apass.Jack Correct. $\endgroup$ – David Fox Jun 12 at 3:33
  • $\begingroup$ Could you please elaborate on the final goal? It is not very clear. What if you know you can get $a$ to $b$ in 8 steps, then just do “dummy” actions, e.g., first add then subtract 10. This will bump number of moves to 10,12,14 and so on. Also, take a look at a $k$-path problem, which asks to find a path length $k$ between two vertices. It is known to be hard, however for your case algorithms will perform practically acceptable. $\endgroup$ – Eugene Jun 12 at 8:58
0
$\begingroup$

There is a neat way to solve this with dynamic programming. First of all we can notice that the minimal number of moves will always be at most $9 * \lg(N)$. Let's denote this number as $B$.

Now let's have the a recursive function $f(u, d)$, which returns true or false depending on whether there is a path of length exactly $d$ from $Start$ to $u$ (in our case, $Start$ is the source number):

f(u, d) { 
   if (u == Start and d == 0) {
       return true
   } 

   for (v in adj(u))
       if (d > 0 and f(v, d - 1) == true)
           return true

   return false 
}

Now to find the answer we can simply check if some of $f(Target, i)$ for $8 \leq i \leq B$, is true. Unfortunately, as it is, the function is exponential, however, we can notice that the result only depends on the pair $(u, d)$. So after computing this value once, we can store it in a $N \times B$ matrix and compute it only once. This idea is known as memoization (you can google it to find more information).

The complexity of the algorithm will be $O(N * \lg(N))$, as every cell of the matrix will be computed at most once.

Another possible approach is to use BFS/Dijkstra on the graph you described but with a tiny difference - we will also add another criteria to the vertices (the parity of the current path). Basically we will have 2 * $N$ vertices and the edges will be constructed like:

for u in range(0, 10000)
    for x in {1, 10, 100, 1000}
        v = u - x
        if v >= 0
             add_edge([u, 0], [v, 1])
             add_edge([u, 1], [v, 0])

Now if we find the shortest path from [$Start$, 0] to [$Target$, 0], we will be sure that it has an even length. If we want an odd-length path, we can find the path from [$Start$, 0] to [$Target$, 1]. Finally, if these paths are too short, we can extend them by adding +1, -1, +1, ... +1, -1. The complexity of this idea will be $O(N)$ if we use BFS.

$\endgroup$
  • $\begingroup$ Does f(u,d) run in polynomial time? It looks like d calls are made, which is exponential in log d (the size of input d). $\endgroup$ – mo2019 Jun 22 at 18:07
-1
$\begingroup$

I have an idea but I am not sure if it works. We construct a directed graph $G'$ with $V'=V \times \{0, \dots, k\}$ when $k$ is the lower bound on the path length. For every edge $uv$ in $E$ and $i<k$ we add $(u,i)(v,i+1)$ and $(u,k)(v,k)$ to $E'$.

Now we search for a shortest directed path from $(s,0)$ to $(t,k)$ in $G'$ to find the shortest path from $s$ to $t$ in the original graph $G$.

The digraph $G'$ has $(k+1)n$ vertices and $(k+1)m$ edges. Hence, the running time is still polynomial

Searching for the shortest odd (or even) path works similarly. Indeed I think that any regular (as in NFA recognizable) constraint on the path can be solved like that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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