Judging from the link you provide, you have three distinct vertices s,t,d and want to compute the number of shortest walks P(s,d,t) from s to d that contain t. The reason I use "walks" instead of "paths" is because of graphs like:
s----d----t
where we must reuse edges.
If you really mean acyclic graph, then P(s,d,t)=1 if there is a path containing vertices s,t and d and P(s,d,t)=0 otherwise.
Let P(s,t) be the number of shortest walks between s and t and P(s,s)=1. If s, d and t are all distinct then P(s,d,t)=P(s,t)P(d,t).
In Section 2.4 of the paper you link to, they describe the algorithm for finding P(s,t). That is $P(s,t)=\sum_{v \in V} P(s,v)$ where V is the set of neighbours of t for which P(s,v) is minimal. The difficulty is identifying which neighbours of t minimise P(s,v).
One way is to construct a set Sn of paths of length n=1,2,... (this can be done recursively), from t until you find some neighbour of s. Then count 1 for each path that ends in a neighbour of s and 0 otherwise. Another way would be to compute P(s,t) and then use a backtracking algorithm.
There's not going to be an exciting formula for P(s,d,t) in general, since it depends on the graphs' structure. This is much like how there's not going to be an exciting formula for the number of edges in a graph (unless you restrict to some specific class of graphs).
I will try to contribute a partial answer. First I want to comment on the Lindstrom-Gessel-Viennot determinant coming from quantum mechanics stuff, in physics this is known as the Slater determinant, giving the formula for the wavefunction of a multi-fermionic system. This gives a nice picture to think of LGV as yet another instance of the Boson-Fermion correspondence. In the boson case, one allows all paths and obtains the total number as the permanent of the LGV matrix (this is obvious from the definition of the permanent), and in the fermion case one gets a system with states counted by the determinant of the LGV matrix. Of course the non-intersecting part comes into play because fermions in addition satisfy the Pauli exclusion principle, therefore they cannot occupy the same site at the same time.
Now, LGV and related results have an interesting history even in fields other than combinatorics. Fisher, in "Walks Walls, Wetting and Melting" 1984, considered the vicious walkers model in statistical mechanics, which considers mutually avoiding directed lattice paths. From this perspective it is interesting to look at some configurations which aren't solved by the usual LGV theorem, for instance when the paths are allowed to intersect at vertices but not edges, or when two paths are allowed to intersect in at most 2 consecutive vertices (the terminology for this classification is $n$-friendly walkers, see here). Viennot and others considered such variants after the relation between the combinatorics of lattice paths and statistical mechanics was established, it turns out that some of these models also have determinantal formulas associated to them. One main article is "From the Bethe Ansatz to the Gessel-Viennot Theorem" by R. Brak, J. W. Essam, and A. L. Owczarek, the point here is that LGV related results can be proven using transfer matrix methods as well, which is a powerful point of view in light of the models I mentioned above where the usual LGV fails (i.e. outside of the six vertex model).
Now if you need something more rigorous relating LGV matrices to fermion models, this can be done, but it doesn't seem to have been written nicely anywhere. Sometimes this is mentioned in the literature in the case of graphs like $\mathbb Z^2$, see for example "Domino tilings and the six-vertex model at its free fermion point" by P.L. Ferrari and H. Spohn, but I believe there should be a more general setting to talk about this. If you take the point of view that Greg Kuperberg mentioned in his answer to this previous MO question, that Kasteleyn-Percus matrices are essentially equivalent to LGV matrices, then I believe there is more literature on interpreting these as models of Majorana fermions living on the graph. The article I'm thinking of is "Dimer Models, Free Fermions and Super Quantum Mechanics" by Dijkgraaf, Orlando and Reffert.
As a last note, I wanted to say that I don't fully understand your motivation to want to identify every occurrence of the determinant with a LGV (or Kasteleyn-Percus) context, given that even within graph theory there are families of objects (even paths or random walks, as mentioned above) which are counted by determinants of a different sort of flavor. As to the question about non-commutative weights to LGV, I can't offer any insight, except perhaps to suggest looking at previous work on non-commutative extensions of the LGV theorem, such as the extension proved in "Noncommutative Schur Functions and their Applications" by Fomin and Greene (available from Fomin's website). But this is probably not very useful since even in their case the ring is almost commutative.
With regard to your question on rank and signature, there is a lot one could explore. As a start, if you look at the Laplacian matrix associated to a graph, then the rank has a clear combinatorial meaning, it measures the number of connected components of the graph (well, the maximum number of edges in an acyclic spanning subgraph, to be more precise), but there is not much to say about the signature since all eigenvalues of the Laplacian are nonnegative. When it comes to the adjacency matrix of the graph, the connection to combinatorial quantities gets even weaker (but it is an area of research), for example the rank of the adjacency matrix was conjectured to have something to do with the chromatic number of the graph, but the relation can not be so nice as was shown by Alon and Seymour. There has been some work on interpreting the signature of the adjacency matrix as well, with some early articles by Torgasev (for example here), but it is of similar nature. One can compute rank and signature easily by linear algebra methods and therefore hopes to use these to bound graph-theoretic quatities, but apparently not the other way around.
Best Answer
The problem is and is not NP-hard. If the length of the input is defined by writing the weights in binary, then it is indeed NP-hard and in fact #P-complete. Say that the target weight $W$ is written in base 10. Suppose further that the graph is a string, as in Reid's construction, with two edges from $i$ to $i+1$, one weight 0 and the other with weight some integer in base 10 with only 0s and 1s in its digits. Also, choose all of the weights so that they cannot add together with any carries. Then the $k$th digit $d$ of the target weight $W$ is a Boolean clause, which says that of those edges that have a non-zero $k$th digit, exactly $d$ are used used. It is not hard to build general Boolean circuits with these clauses.
Also, to clarify a couple of points about this: You can convert from weight at most $W$ to weight exactly $W$ by subtracting off weight at most $W-1$; so in this quick argument it is only #P-hard with a Turing reduction and not a Cook reduction. And of course I'm really showing that the knapsack counting problem is #P-hard.
On the other hand, if the length is defined by writing the weights in unary, to favor small integer values of the weights, then the dynamic programming algorithm given in the question is polynomial time.
Which complexity model is more appropriate depends on the context of the problem, which was not given.