# Graph algorithms

A path is a feasible witness; the minimum-distance claim must also exclude shorter paths.

## Definitions

- **Directed edge**: An ordered pair of vertices with a nonnegative weight.
- **Simple path**: A path visiting no vertex twice.
- **Distance**: The sum of the weights along a path.

## Acceptance procedure

1. Enumerate every simple source-to-target path in the small graph.
2. Compute the total weight of each path.
3. Find the minimum and accept any witness attaining it.
4. Check the witness edge sequence and objective.

## Complexity

Simple-path enumeration can be exponential; nonnegative weights ensure a shortest path can be chosen simple.

## Common failure

A locally cheapest outgoing edge need not belong to a globally shortest path.

## Extensions

Replace enumeration with distance-label certificates and add max-flow/min-cut records.

## Instances

- KL-FCS-028: A shortest path through an intermediate node — Minimum distance: 5
- KL-FCS-029: Two equally short paths — Minimum distance: 3
- KL-FCS-030: Zero-weight edges without negative cycles — Minimum distance: 1

## References

- https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut.html