The Longest Path Problem

In the travelling salesman problem, the pattern was an approximate solution, and being wrong was expected of it. This lesson looks at a more unsettling situation: the pattern is a proven procedure, its code is correct, it contains no bug, and it still gives a wrong answer. The only thing that changes is the problem it is applied to.

The shortest-path problem was built in the Algorithms course’s Graph Algorithms topic. The Dijkstra’s Algorithm and Bellman–Ford Algorithm lessons measured the relaxation operation, the algorithm’s invariant, and the negative-weight constraint; this lesson does not rebuild those procedures. Here, a single change is made: the comparison in the relaxation is turned from less than to greater than, and the same procedure is set to search for the longest path. What is asked is how many graphs this one-character change produces a wrong answer on.

• CP20. Graphs come from the shared definition’s generator: 8 nodes, each directed edge present with a 45 percent share, weight between 1 and 9. Seed 20260218, second pool 20260219.
• CP21. Two graph families are used. In the acyclic family, an edge only goes from a lower-numbered node to a higher one, so no cycle can form. In the cyclic family, this restriction does not exist.
• CP22. The question asked is the same in both families: the heaviest simple path from node zero to node seven. A simple path is a path that repeats no node.
• CP23. The oracle scans every simple path with depth-first search and takes the heaviest. This is the direct counterpart of the problem’s definition.
• CP24. The pattern is the shortest-path relaxation turned toward the longest: every edge is passed over node-count-minus-one times, and at each pass the larger value is accepted.
• CP25. The measure is steps. In the oracle a step is a node visit; in the pattern, an edge relaxation. The two numbers are not in the same unit, and are read that way.
• CP26. The split-input count is out of 40; a difference below 3 counts as unmeasured.
• CP27. If there is no path to the target node at all, both procedures return no answer; this does not count as a split, since both give the same answer.
• CP28. Node count is also swept. That the oracle is expensive is not an assumption but a measured threshold.
• CP29. The six-node graph that shows the loss of optimal substructure is built by hand; it does not come from the generator. It is chosen to show a single mechanism in its smallest form.

The Same Procedure, Two Graph Families

The block below generates both families, runs the oracle and the pattern side by side on every graph, and prints the split count separately for both pools.

SEED = 20260218
N = 8


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def graphs(seed=SEED, samples=40, cyclic=False, n=N):
    """Directed graph: in the acyclic version, edges only go from a lower number to a higher one."""
    r = generator(seed)
    pool = []
    for _ in range(samples):
        edges = []
        for i in range(n):
            for j in range(n):
                if i == j or (not cyclic and j < i):
                    continue
                if r(100) < 45:
                    edges.append((i, j, r(9) + 1))
        pool.append(edges)
    return pool


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def oracle_longest(edges, c, n=N):
    """Every simple path is scanned: from 0 to n-1, with no node repeated."""
    neighbors = {}
    for i, j, w in edges:
        neighbors.setdefault(i, []).append((j, w))
    best = None

    def walk(v, seen, weight):
        nonlocal best
        c.count()
        if v == n - 1:
            if best is None or weight > best:
                best = weight
            return
        for j, w in neighbors.get(v, []):
            if j not in seen:
                walk(j, seen | {j}, weight + w)
    walk(0, {0}, 0)
    return best


def pattern_relaxation(edges, c, n=N):
    """The shortest-path relaxation turned toward the longest: greater instead of smaller."""
    best = [None] * n
    best[0] = 0
    for _ in range(n - 1):
        for i, j, w in edges:
            c.count()
            if best[i] is not None and (best[j] is None or best[i] + w > best[j]):
                best[j] = best[i] + w
    return best[n - 1]


for name, cyclic in (("acyclic", False), ("cyclic ", True)):
    for seed in (20260218, 20260219):
        split, pk, ok, overshoot = [], 0, 0, 0
        for no, edges in enumerate(graphs(seed, cyclic=cyclic), 1):
            s1, s2 = Counter(), Counter()
            a = pattern_relaxation(edges, s1)
            b = oracle_longest(edges, s2)
            pk, ok = pk + s1.steps, ok + s2.steps
            if a != b:
                split.append(no)
                if a is not None and b is not None:
                    overshoot = max(overshoot, a - b)
        print(name, seed, "| split", len(split), "/40", split[:6],
              "| pattern steps", pk, "| oracle steps", ok, "| worst overshoot", overshoot)

acyclic 20260218 | split 0 /40 [] | pattern steps 3626 | oracle steps 562 | worst overshoot 0
acyclic 20260219 | split 0 /40 [] | pattern steps 3696 | oracle steps 536 | worst overshoot 0
cyclic  20260218 | split 38 /40 [1, 2, 3, 4, 5, 6] | pattern steps 7210 | oracle steps 3235 | worst overshoot 228
cyclic  20260219 | split 39 /40 [1, 2, 3, 4, 5, 6] | pattern steps 7203 | oracle steps 3272 | worst overshoot 226

Correct on Acyclic Graphs, Not on Cyclic Ones

On the acyclic family, the split count is 0. The same procedure, the same code, matches the oracle on 40 of 40 graphs, and stays at 0 on the second pool too. On the cyclic family, the split count is 38, and 39 on the second pool. The procedure did not break; the graph changed.

The direction of the split is measured too: the pattern’s value is never smaller than the oracle’s, and the largest difference is 228 weight units. The pattern overestimates — it reports the weight of a path that does not exist. This is direct proof that the two procedures are searching for different objects.

What the relaxation procedure computes is the heaviest walk: going from one node to another by following edges, allowing nodes to repeat. What is asked for is the heaviest simple path: repeating a node is forbidden. On an acyclic graph, these two objects coincide, because without a cycle no walk can visit a node twice. Once a cycle exists, the coincidence ends, and the relaxation starts circling the cycle, accumulating weight.

The only reason this accumulation does not run forever is that the number of passes is limited. But that limit is not as narrow as it seems: because edges are processed in a fixed order within a single pass, the value one edge produces can chain into later edges in the same pass. The resulting walk can therefore be far longer than the pass count, and this is why the overestimate reaches as high as 228. If the order edges are processed in changes, the wrong value returned changes too — the wrong answer is not even stable.

The Loss of Optimal Substructure

The proof of shortest path rests on a single property: every segment of a shortest path is itself a shortest path. Thanks to this property, a node’s best value can be built from its neighbors’ best values, and relaxation works.

For the longest simple path, this property fails. The longest simple path from node zero to node five, and the longest simple path from node five to node seven, can each be found separately; but joining the two end to end may not give a simple path, because the two segments may pass through a shared node. If the join is forbidden, the subproblems’ solutions do not carry over into the main problem’s solution, and the ground the relaxation stands on is gone.

This loss can be shown clearly on a single six-node graph. The block below prints three numbers side by side: the sum of the two subproblems’ separately best solutions, the actual best solution, and the value the relaxation gives.

EDGES = [(0, 1, 5), (1, 2, 5), (2, 3, 5), (0, 3, 1),
         (3, 2, 5), (2, 4, 5), (4, 5, 5), (3, 5, 1)]
N = 6


def oracle_path(edges, start, end):
    """Every simple path is scanned; the heaviest is returned along with its path."""
    neighbors = {}
    for i, j, w in edges:
        neighbors.setdefault(i, []).append((j, w))
    best = (None, None)

    def walk(v, path, weight):
        nonlocal best
        if v == end:
            if best[0] is None or weight > best[0]:
                best = (weight, tuple(path))
            return
        for j, w in neighbors.get(v, []):
            if j not in path:
                walk(j, path + [j], weight + w)
    walk(start, [start], 0)
    return best


def pattern_relaxation(edges, end, n=N):
    best = [None] * n
    best[0] = 0
    for _ in range(n - 1):
        for i, j, w in edges:
            if best[i] is not None and (best[j] is None or best[i] + w > best[j]):
                best[j] = best[i] + w
    return best[end]


a, b, c = oracle_path(EDGES, 0, 3), oracle_path(EDGES, 3, 5), oracle_path(EDGES, 0, 5)
print("longest simple path from 0 to 3:", a)
print("longest simple path from 3 to 5:", b)
print("sum of the two segments        :", a[0] + b[0],
      "| shared node:", sorted(set(a[1]) & set(b[1])))
print("longest simple path from 0 to 5:", c)
print("what the relaxation gives      :", pattern_relaxation(EDGES, 5))

longest simple path from 0 to 3: (15, (0, 1, 2, 3))
longest simple path from 3 to 5: (15, (3, 2, 4, 5))
sum of the two segments        : 30 | shared node: [2, 3]
longest simple path from 0 to 5: (20, (0, 1, 2, 4, 5))
what the relaxation gives      : 70

The three numbers must be read separately. The subproblems’ best solutions are 15 and 15; their sum is 30. This 30 is not the weight of any path, because the two segments share nodes 2 and 3. The actual answer is 20, and the path it corresponds to contains neither of the two sub-solutions. The value the relaxation gives is 70: the weight of a walk accumulated by circling the cycle multiple times.

The gap between thirty and seventy matters. When optimal substructure fails, it is not just that “the sub-solutions cannot be joined”; the relaxation goes further, past the unjoinable segments, and starts measuring an entirely different object. Someone looking only at the output cannot tell this: the value returned is an integer, unmarked, carrying no warning. The course’s rule holds here too — wrongness cannot be picked out by looking at the output, only seen with the oracle.

Reading the same observation the other way around gives a useful rule: when carrying a procedure over to a new problem, the question to ask is not “does the code run” but “does the property the proof rests on still hold”. In this lesson, the acyclicity constraint is exactly the condition that keeps that property standing.

When the Oracle Is Expensive

There is a striking anomaly in the output above: at eight nodes the oracle spends 562 steps, the pattern 3626 steps. The oracle is cheaper than the pattern. The shared definition’s reading that “the oracle is always expensive” does not match the number measured here, and the number is not hidden. Being expensive is not a definition but a function of scale. Sweeping node count makes the threshold visible.

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def graphs(n, seed=SEED, samples=10):
    r = generator(seed)
    return [[(i, j, r(9) + 1) for i in range(n) for j in range(n)
             if i != j and r(100) < 45] for _ in range(samples)]


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def oracle_longest(edges, n, c):
    neighbors = {}
    for i, j, w in edges:
        neighbors.setdefault(i, []).append((j, w))
    best = None

    def walk(v, seen, weight):
        nonlocal best
        c.count()
        if v == n - 1:
            best = weight if best is None or weight > best else best
            return
        for j, w in neighbors.get(v, []):
            if j not in seen:
                walk(j, seen | {j}, weight + w)
    walk(0, {0}, 0)
    return best


def pattern_relaxation(edges, n, c):
    best = [None] * n
    best[0] = 0
    for _ in range(n - 1):
        for i, j, w in edges:
            c.count()
            if best[i] is not None and (best[j] is None or best[i] + w > best[j]):
                best[j] = best[i] + w
    return best[n - 1]


print(" n | oracle steps | pattern steps | ratio")
for n in (6, 8, 10, 12, 13):
    ah = ak = 0
    for edges in graphs(n):
        s1, s2 = Counter(), Counter()
        pattern_relaxation(edges, n, s1)
        oracle_longest(edges, n, s2)
        ak, ah = ak + s1.steps, ah + s2.steps
    print(f"{n:2d} | {ah:10d} | {ak:10d} | {round(ah / ak, 2)}")

 n | oracle steps | pattern steps | ratio
 6 |        102 |        655 | 0.16
 8 |        746 |       1785 | 0.42
10 |      10210 |       3762 | 2.71
12 |     196705 |       6677 | 29.46
13 |     747243 |       8652 | 86.37

The threshold is at ten nodes. At six nodes, the oracle spends about a sixth of the pattern’s steps; at thirteen nodes, it spends 86.37 times more. The pattern’s steps rise from 655 to 8652, a factor of thirteen; the oracle’s steps rise from 102 to 747,243, a factor of roughly seven thousand. This gap does not change the fact that the pattern is still wrong on cyclic graphs: what becomes cheap is not the correct answer but the wrong one.

This table should be read together with the previous lesson. In the travelling salesman problem, the oracle could be run on small input and could not be run on large input; here, the oracle is cheaper than the pattern on small input. In both cases, the oracle’s cost has been measured, not assumed.

Summary

• The longest simple path is not the shortest path reversed; the relaxation procedure finds the heaviest walk, while the problem asks for the heaviest simple path.
• On an acyclic graph the two objects coincide, and the pattern matches the oracle on 40 of 40 inputs; the split count is also 0 on the second pool.
• On a cyclic graph, the pattern splits on 38 of 40 inputs, 39 on the second pool, with the worst overestimate at 228 weight units.
• The source of the split is the loss of optimal substructure: joining two sub-paths may not give a simple path, since they can share a node.
• The oracle’s expense comes with scale; at eight nodes the oracle is cheaper than the pattern, at thirteen nodes it is 86.37 times more expensive. A procedure cannot be called expensive without measuring it.

Next Step

In this lesson, the pattern gave a wrong answer, the oracle gave the correct one, and the oracle’s cost was measured. The next lesson takes up speeding up the oracle itself. In the n-queens problem, backtracking cuts conflicting branches instead of scanning every placement; the shared definition already gave the numbers for this. The new question to ask is: how much does eliminating the board’s symmetries shrink the search space, and does that shrinkage change the exponential growth.