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