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$ – John L. Jun 12 '19 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 '19 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$ – John L. Jun 12 '19 at 3:32
  • $\begingroup$ @Apass.Jack Correct. $\endgroup$ – David Fox Jun 12 '19 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 '19 at 8:58
1
$\begingroup$

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.

Edit: Note that the second entry in the tuples stays the same. To be more precise, consider any path $P=v_0v_1…v_kv_{k+1}…v_n$ on $G$ with length $≥k$. Then there is a corresponding path $P'=(v_0,0)(v_1,1)…(v_k,k)(v_{k+1},k)…(v_n,k)$ on $G'$. Similarly, every path on $G'$ induces a path on $G$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is not necessary since for every edge $uv \in E$ there exists an edge $(u,k)(v,k) \in E'$. Note that the second entry in the tuples stays the same. To be more precise, consider any path $P = v_0 v_1 \dots v_k v_{k+1} \dots v_n$ on $G$ with length $\ge k$. Then there is a corresponding path $P' = (v_0,0) (v_1,1) \dots (v_k, k) (v_{k+1}, k) \dots (v_n, k)$ on $G'$. $\endgroup$ – Daniel Dec 12 '19 at 15:57
  • $\begingroup$ Oh, right! I think this is a beautiful solution. Seems to work to me! I'm not sure why it was downvoted - it's great. $\endgroup$ – D.W. Dec 12 '19 at 17:21
  • $\begingroup$ I think that this result could be generalized. Are you maybe familiar with this variation of the shortest path problem and do you know if there is a framework which deals with this problem in a similar way? $\endgroup$ – Daniel Dec 13 '19 at 19:19
  • $\begingroup$ The problem is known as Regular language constraint shortest path problem (RegLCSP) and is part of the formal language CSP. $\endgroup$ – Daniel Dec 13 '19 at 19:30
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.

| cite | improve this answer | |
$\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 '19 at 18:07
0
$\begingroup$

You can solve your problem using two applications of Dykstra's algorithm. Suppose we want to find the shortest path from $s$ to $t$ with $\ge \ell$ edges. This can be decomposed into a shortest path with exactly $\ell$ edges from $s$ to some vertex $v$, followed by a shortest path from $v$ to $t$ of any number of edges.

So, first build a graph that computes for each $v$ the length of the shortest path from $s$ to $v$ using exactly $\ell$ edges. This can be done by computing the answer for all $v$ for paths with 1 edge, then for all $v$ for paths with 2 edges, and so on.

Second, we'll compute for each $v$ the shortest path from $v$ to $t$. This can be done by running Dykstra's algorithm, starting from $t$, on the reverse of your graph (after flipping the orientation of all edges).

Finally, iterate over all $v$, and sum up the length of the shortest path from $s$ to $v$ and from $v$ to $t$, and take the shortest one found.

The total running time is $O(|V| \cdot |E|)$. The first stage can be done in $O(|V| \cdot |E|)$ time. The second stage uses Dykstra's algorithm, so it can be done in $O(|E| \log |V|)$ time. The third stage can be done in $O(|V|)$ time. The time to do the first stage dominates.

| cite | improve this answer | |
$\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.