Decide whether there exists a walk of weight exactly k
We start by converting your graph into an NFA $A$, by replacing the weights with strings. Positive weights $k &gt; 0$ are replaced by $a^k$, negative weights $k &lt; 0$ are replaced by $b^{-k}$, and zero weights are replaced by $\epsilon$ (the empty string). We make $v_1$ the initial state and $v_2$ the only accepting state. Consider now the context-free language $L_k = \{ w : \#_a(w) - \#_b(w) = k \}$. We construct a context-free grammar for $L_k \cap A$ and check whether $L_k \cap A = \emptyset$.

The size of the generated NFA is polynomial in $n + \sum_{ij} |w_{ij}|$ where $n$ is the number of vertices and $w_{ij}$ are the weights. The size of a grammar for $L_k$ is polynomial in $k$. In order to intersect it with $A$, we convert it to a PDA, use the product construction, and then convert back. We get a CFG of size polynomial in $n + \sum_{ij} |w_{ij}| + k$. Checking emptyness takes polynomial time, so the entire algorithm takes time polynomial in $n + \sum_{ij} |w_{ij}| + k$, showing that the problem is in NP if the weights and the target sum are encoded in unary (otherwise the bound we get is only NEXP).

Interestingly, this argument doesn't work for real weights. The natural extension would be to find a basis for the weights over $\mathbb{Q}$, clear off the denominators, and have a pair of symbols $(a_i,b_i)$ for each element in the basis. The argument fails since $L_{\mathbf{k}} = \{ w : \forall i \#_{a_i}(w) - \#_{b_i}(w) = k_i \}$ is not context-free if there is more than one pair of symbols.


  Is the problem with real weights (given as linear combinations over $\mathbb{Q}$ of some $\mathbb{Q}$-linearly independent set) decidable?