I was thinking of creating this problem (it feels like a fundamental one, but I haven’t found it on any website). Can anyone help me figure out the optimal solution, or point me to a known reference if it already exists?

Problem Statement:

You are given a directed graph with n nodes labeled 0 to n-1. A token starts at node 0. Two players play a game on this graph, taking turns alternately:

On each turn, the current player must move the token along one outgoing edge of the current node.

Player A wants the token to reach node n-1 in as few moves as possible.

Player B wants to delay this as much as possible, or prevent the token from ever reaching node n-1.

If both players play optimally, output the number of moves required for the token to reach node n-1. If Player A cannot guarantee reaching node n-1, output -1.

Note: As a variation, edge weights can be introduced but I feel the essence of this problem is that it is closer to chess than Dijkstra.

Here's why this problem seems so complicated to me:

The core difficulty is mutual anticipation; Every move A makes affects B’s control, which B can anticipate and counter, which A must then anticipate, and so on. This makes it fundamentally different from variations of shortest path algorithms, like sometimes Player A may deliberately avoid the “shortest path” if it would later hand control to Player B at a significant node. Similarly, Player B may allow a slightly faster move early if it leads into a region where A is forced into a dead end or an unavoidable delay. Player A must think several moves ahead, anticipating not just B’s immediate sabotage but also B’s longer-term counter-strategies.

Also consider Cycles and their Parity can act as a tool for the player in turn to decide in future who will get in charge later. Like If the token enters a cycle, whether it benefits Player A or B depends on the parity of the cycle length and whose turn it will be when leaving the cycle. For example, an odd-length cycle could let Player B regain control at a crucial node, while an even-length cycle might let Player A maintain control. Also, A path that looks promising might actually funnel the token into a dead end where Player B can stall indefinitely.

If edge weights are introduced, Not only cases such as Player A accepting a costlier short-term edge to avoid traps will come, but also player may prioritize parity of number of edges over weights to decide control, For example: One path may have 1 node with 6 weight while another may have 2 nodes with 3 weights each. Player might prefer second path to control the turn order again. Also sometimes, not being in control immediately may still be optimal when considering longer-term anticipation.

Due to all this the only solution I can think of is brute-forcing through all possibilities via DP. Thanks for reading! I’d really welcome any feedback, references to similar problems, or ideas toward an optimal solution.