Introduction

Standard shortest-path algorithms assume the cost of an edge depends only on the current node and the chosen edge. Once the price of the next step depends on what happened earlier in the route, the problem changes shape. The usual fix is not to abandon Dijkstra's algorithm entirely, but to run it on a larger state space that includes the relevant history.

Turn the History Into State

The key question is: what part of the past actually matters for future cost?

If the next edge cost depends only on a small, finite summary of the path, then you can include that summary in the node state. Instead of searching over node, you search over (node, state).

Examples:

• if the price depends on the last edge color, state is the last color
• if one coupon can be used once, state is whether the coupon is already spent
• if revisiting nodes is forbidden, state may be a visited-set bitmask for small graphs

This technique is often called an expanded graph or layered graph. It works because once the summary state is known, the future cost becomes Markovian again.

A Concrete Example

Suppose each edge has a travel mode, and switching modes costs an extra 2 units. The cost of the next step depends on the previous step, so plain Dijkstra on node IDs alone is wrong.

We can solve it by tracking the last mode in the priority queue state.

1import heapq
2
3graph = {
4    "A": [("B", 3, "road"), ("C", 2, "rail")],
5    "B": [("D", 2, "road"), ("C", 1, "rail")],
6    "C": [("D", 2, "rail")],
7    "D": [],
8}
9
10SWITCH_PENALTY = 2
11
12
13def shortest_path_with_history(start, goal):
14    pq = [(0, start, None)]
15    dist = {(start, None): 0}
16    parent = {(start, None): None}
17
18    while pq:
19        cost, node, last_mode = heapq.heappop(pq)
20        if cost != dist[(node, last_mode)]:
21            continue
22        if node == goal:
23            path = []
24            state = (node, last_mode)
25            while state is not None:
26                path.append(state[0])
27                state = parent[state]
28            return cost, list(reversed(path))
29
30        for nxt, weight, mode in graph[node]:
31            extra = 0 if last_mode in (None, mode) else SWITCH_PENALTY
32            new_cost = cost + weight + extra
33            state = (nxt, mode)
34            if new_cost < dist.get(state, float("inf")):
35                dist[state] = new_cost
36                parent[state] = (node, last_mode)
37                heapq.heappush(pq, (new_cost, nxt, mode))
38
39    return None
40
41
42print(shortest_path_with_history("A", "D"))

The priority queue now distinguishes reaching node C by road from reaching C by rail. Those are different states because they lead to different future costs.

When Dijkstra Still Works

Dijkstra's algorithm still works on the expanded graph if all effective transition costs are non-negative. That is the same condition as usual. You are not changing the algorithm's logic. You are changing what counts as a node.

Bellman-Ford or dynamic programming variants are useful when negative transitions exist, but in many practical history-dependent problems the expanded-state Dijkstra approach is enough.

The complexity depends on how many distinct states each physical node can have. If you track only the last color, the blow-up is small. If you track the full visited set, the blow-up can be exponential.

When the Problem Becomes Much Harder

Some history-dependent costs are easy to summarize. Others are not.

For example, if the cost depends on exactly which subset of nodes has been visited, then the state might be (node, visited_mask). That is manageable only for small graphs.

def mask_with(node_index, mask):
    return mask | (1 << node_index)

That kind of state appears in problems related to the traveling-salesperson family. Once the relevant history cannot be compressed into a small finite state, you should expect a sharp increase in complexity.

A good rule is: if you cannot write a compact state summary, you probably do not have a polynomial-time shortest-path problem anymore.

Modeling Matters More Than the Algorithm Name

People often ask whether there is a "special algorithm" for history-dependent path cost. Usually the deeper issue is modeling. You need to define the smallest state that preserves future decisions.

Once you do that, the algorithm choice becomes clearer:

• expanded-state Dijkstra for non-negative costs
• dynamic programming for bounded finite state
• A-star on the expanded graph if you have an admissible heuristic
• exact combinatorial search when the state includes large visited subsets

The wrong move is to run ordinary Dijkstra on the original nodes and hope the path history sorts itself out. It will not.

Common Pitfalls

The most common mistake is storing one distance per node instead of one distance per node-state pair. That merges states that have different future costs and produces incorrect answers.

Another mistake is encoding too much history. If you track information that does not affect future transitions, you make the state space larger for no gain.

Developers also sometimes forget that the goal test may depend on state. Reaching the destination with one mode or resource balance may not be equivalent to reaching it with another.

Finally, do not assume "history-dependent" automatically means Dijkstra is unusable. If the dependency can be summarized with a finite state, the classic machinery still applies after state expansion.

Summary

• A history-dependent shortest path is usually solved by expanding the state space.
• Search over (node, state) rather than over node alone.
• Dijkstra still works when the effective transition costs remain non-negative.
• The real difficulty is finding the smallest state summary that preserves future cost decisions.
• If the needed history is large, the problem can grow exponentially and may need a different class of algorithms.