I am trying to solve the following kind of problem.  I do not know if there is already a name for this, or a solution; however, I'm willing to bet there is.  I was hoping someone could point me in the direction of implementing a solution for it, or at least tell me the name of the problem?Suppose a traveler has a certain amount of Gold coins, and some Bronze coins.  He must start a city A, and go to city B, then city C, and finally city D.There are two (or more) roads that pass from A to B, labeled AB1, and AB2 (etc.).Road AB1 has a toll of 5 gold coins, and AB2 has a toll of 5 bronze coins.Roads from city B to C: BC1 has a toll of 10 coins, which can be either currency.  BC2 requires 8 gold coins.Roads from C to D have some sort of similar setup.Assuming that we know how much money the traveler has, and that there is no possible exchange between bronze and gold coins: is there a method to determine if the traveler has enough money to pass through from A to B, to C, and finally to D?This is the kind of problem I need a solution to...  Is there a name for this problem?  Is there a solution to this problem (other than brute force)?  I'm assuming this is a similar problem to flow problems, but I don't know quite how to approach it.
Graph theory problem (name unknown)
graph traversal
If I'm reading your question correctly, your problem has a two interesting properties:The graph is connected sequentially, A->B->C->D. There may be multiple edges between nodes, but there are never edges that skip nodes (A->C, B->D) or loop back (C->A).The ultimate goal is feasibility versus optimality. That is, you want to know if a traveler has enough money versus which path costs the absolute least.Is that correct? If so, there are a few tricks available. First, calculate the expected value in both gold and bronze between each city. The expected value would be the minimum you would expect to pay. Given AB1 = 5 gold, AB2 = 5 bronze, and AB3 = 10 gold or bronze (I'm adding the road to illustrate a point), you would never select AB3. AB1 or AB2 give you a better solution regardless of the coin you use. Therefore, the expected value between A and B is 5 gold and 5 bronze. The expected value between B and C is 8 gold and 10 bronze. Again, we would never select BC1 (10 gold or bronze) when spending gold as BC2 (8 gold) is always cheaper. Continue calculating the expected values for the rest of your path.Next, total your expected values for each coin. You're basically acting as if you paid all tolls using one coin type, but you're doing it for both types in one pass. If your expected values are:A->B 5 gold, 5 bronzeB->C 8 gold, 10 bronzeC->D 10 gold, 7 bronzeYour totals are 23 gold and 22 bronze. If you started with 23 or more gold and 22 or more bronze, you're done. You know that a feasible solution exists. More likely, your expected totals will be greater than your coins available.In that case, make a choice between expected value pairs versus considering both options. If you're short on gold, spend bronze where it returns the most gold. For example, if I start with 13 gold, I can select the bronze payment option between C->D to create a feasible solution. If I start with 5 bronze, I can select the gold payment option between B->C and C->D to create a feasible solution. Again, that's probably wishful thinking. It's likely you'll be short both gold and bronze. If that's the case, start with a heuristic to resolve expected values: if you have a larger gold deficit, select expected values that yield the greatest savings in gold before resolving bronze, try to make up the deficit with the fewest choices possible, etc... In the end, you may still have to try every combination of expected values to prove a feasible solution does or does not exist.Note that this doesn't account for tolls that involve both currencies. A toll of 2 gold and 5 bronze ruins my expected value trick.