Algorithm for fewest number of moves with artificial minimum 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&lt;int, IEdge&lt;int&gt;&gt; GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph&lt;int, IEdge&lt;int&gt;&gt;();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i &lt;= 10000; i++)
    {
        for (int j = i+1; j &lt;= 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&lt;int&gt;(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
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&lt;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$.