Shortest path with jumps (dynamic Bayesian network)?

Suppose I have the following graph structure:

It has the following properties:

• There are four states $\mathcal{S} = {q,s_1,s_2,s_3}$ where $q$ is some origin state where we start from (though it is not time-indexed).
• The transition cost going from node $i$ to node $j$ is given by $c^t_{i,j}$ where $t$ is the time-stamp of the destination node. So for example: $c^2_{s_1,s_1}$ is the cost of travelling between $s_1$ at time $t=1$ and $s_1$ at time $t=2$.
• Each node (black dot) is shown with it's state-label and the time index of that state e.g. $(s_2,1)$ is state $s_2$ at time index $1$.

My interest is in finding the path with the lowest cost. I am not interested in the tour i.e., not the TSP (travelling salesman problem); I am interested in going from left to right in the graph at the lowest cost.

Apart from the first time step, there are nine costs to consider at each time step.

Now my question is simply what is this type of problem called?

• It doesn't seem to be the shortest path problem because my path does not need to be contiguous. This means that e.g. $\phi = \{c^0_{q,s_1},c^1_{s_2,s_3} c^2_{s_2,s_1} \}$ is a valid path for my problem setting (if $\phi$ has the lowest cost of going left to right).
• It is not a TSP since I do not need to visit every node (just one per time index), nor do I need to return to the start.
• The Viterbi algorithm perhaps but there is nothing stochastic about my states and I know all the costs but perhaps some other sort of max-sum algorithm?
• I suppose we could use the Bellman–Ford algorithm and just specify the three states at the end, upon which we pick the one with the lowest cost.

Solution 1:

Based on our discussion, I think Viterbi algorithm is what you are looking for. I shortly highlight the most important steps needed for computation and how it can be used on a general graph with costly edges.

Define $\mu(i,t)$ as the cost of the minimum cost path to the $i$-th state at time $t$ and define $c(i,j,t)$ as the cost of going from state $i$ to state $j$ at time $t$. We will compute $\mu(i,t)$ in an iterative fashion from left to right.

1. Set $\mu(0,0)=0$ for the initial state at time $t=0$.
2. For $t = 1,2,\dots$ and for each state $j$ at time $t$, compute $$\mu(j,t) = \min_i \{ \mu(i,t-1)+c(i,j,t-1) \} , $$ where the minimum is over all states $i$ at time $t-1$ that are connected to the state $(j,t)$.
3. Once you have reached the end, you can backtrack the minimum cost path by identifying at each state the incoming edge with smallest cost.

Note that if you want to spare the backtracking, you can also track the minimum cost path with an auxiliary variable $p(i,t)$ for each state $i$ and time $t$.