Queries for minimum fuel needed to travel from U to V

This answer will explain my matrix group comment in detail and then sketch the standard data structures needed to make it work.

Let’s suppose that we’re carrying Gold and have burned Fuel so far. If we traverse an edge with parameters Distance, Toll, then the effect is

Gold -= Toll
Fuel += Gold * Distance,

or as a functional program,

Gold' = Gold - Toll
Fuel' = Fuel + Gold' * Distance.
= Fuel + Gold * Distance - Toll * Distance.

The latter code fragment defines what mathematicians call an action: each Distance, Toll gives rise to a function from Gold, Fuel to Gold, Fuel.

Now, whenever we have two functions from a domain to that same domain, we can compose them (apply one after the other):

Gold' = Gold - Toll1
Fuel' = Fuel + Gold' * Distance1,

Gold'' = Gold' - Toll2
Fuel'' = Fuel' + Gold'' * Distance2.

The point of this math is that we can expand the definitions:

Gold'' = Gold - Toll1 - Toll2
= Gold - (Toll1 + Toll2),

Fuel'' = Fuel' + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + (Gold - Toll1) * Distance1 + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + Gold * (Distance1 + Distance2) - (Toll1 * Distance1 + (Toll1 + Toll2 ) * Distance2).

I’ve tried to express Fuel'' in the same form as before: the composition has “Distance” Distance1 + Distance2 and “Toll” Toll1 + Toll2, but the last term doesn’t fit the pattern. What we can do, however, is add another parameter, FuelSaved and define it to be Toll * Distance for each of the input edges. The generalized update rule is

Gold' = Gold - Toll
Fuel' = Fuel + Gold * Distance - FuelSaved.

I’ll let you work out the generalized composition rule for Distance1, Toll1, FuelSaved1 and Distance2, Toll2, FuelSaved2. Suffice it to say, we can embed Gold, Fuel as a column vector {1, Gold, Fuel}, and parameters Distance, Toll, FuelSaved as a unit lower triangular matrix {{1, 0, 0}, {-Toll, 1, 0}, {-FuelSaved, Distance, 1}}. Then composition is matrix multiplication.

Now, so far we only have a semigroup. I could take it from here with data structures, but they’re more complicated when we don’t have an analog of subtraction (for intuition, compare the problems of finding the sum of each length-k window in an array with finding the max). Happily, there is a useful notion of undoing a traversal here (inverse). We can derive it by solving for Gold, Fuel from Gold', Fuel':

Gold = Gold' + Toll
Fuel = Fuel' - Gold * Distance + FuelSaved,
Fuel = Fuel' + Gold' * (-Distance) - (-FuelSaved - Toll * Distance)

and reading off the inverse parameters.

I promised a sketch of the data structures, so here we are. Root the tree anywhere. It suffices to be able to

• Given nodes u and v, query the leafmost common ancestor of u and v;
• Given a node u, query the parameters to get from u to the root;
• Given a node v, query the parameters to get from the root to v;
• Update the toll on an edge.

Then to answer a query u, v, we query their leafmost common ancestor w and return the fuel cost of the composition (u to root) (w to root)⁻¹ (root to w)⁻¹ (root to v) where ⁻¹ means “take the inverse”.

The full-on sledgehammer approach here is to implement dynamic trees, which will do all of these things in amortized logarithmic time per operation. But we don’t need dynamic topology updates and can probably afford an extra log factor, so a set of more easily digestable pieces would be leafmost common ancestors, heavy path decomposition, and segment trees (one per path; Fenwick is potentially another option, but I’m not sure what complications a noncommutative operation might create).

I told in the comments that a Dijkstra algorithm was necessary, but thinking better the DFS is really enough because there is only one path for each pair of vertices, we will always need to go from the starting point to the endpoint.

Using a priority queue instead of a stack would only change the order that the graph is explored, but in the worst case it would still visit all the vertices.

Using a queue instead of a stack would make the algorithm a breadth first search, again would only change the order in which the graph is explored.

Assuming that the number of nodes in a given distance increases exponentially with the threshold. An improvement for the typical case could be achieved by doing two searches and meeting in the middle. But only a constant factor.

So I think it is better to go with the simple solution, implementing this in C/C++ will result in a program dozens of times faster.

Solution

Prepare adjacency lists, and also makes the graph undirected

from collections import defaultdict
def process_edges(rows):
  edges = defaultdict(list)
  for u,v,D,T in rows:
    edges[u].append((v,(D,T)))
    edges[v].append((u,(D,T)))
  return edges

It is interesting to do the search backwards because the amount of gold is fixed at the destination, and unknown at the origin, then we can calculate the exact amount of gold and fuel required for each node going backwards.

Of course you can remove the print statement I left there

def dfs(edges, a, b, G):
    Q = [((0,G),b)]
    visited = set()
    while len(Q) != 0:
        ((Fu,Gu), current_vertex) = Q.pop()
        visited.add(current_vertex)
        for neighbor,(D,T) in edges[current_vertex]:
            if neighbor in visited:
              continue; # avoid going backwards
            Gv = Gu + T # add the tax of the edge to the gold budget
            Fv = Fu + Gv * D # compute the required fuel
            print(neighbor, (Fv, Gv))
            if neighbor == a:
              return (Fv, Gv)
            Q.append(((Fv,Gv), neighbor))

Running your example

edges = process_edges([
    [6,4,1,4],
    [5,4,2,2],
    [4,2,2,3],
    [3,2,1,2],
    [1,2,2,1]
])
dfs(edges,3,6,2)

Will print:

4 (6, 6)
5 (22, 8)
2 (24, 9)
3 (35, 11)

and return (35, 11). It means that for rounte from 3 to 6, it requires 11 gold, and 35 is the fuel used.