Bellman-Ford & Minimum Spanning Trees

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • pathFinding - problem statement, Java CodeExpert template & test-cases
    • Copy the contents of the Main, custom.in and custom.out files into the corresponding files of the ”Welcome” exercise. You can run the tests by using the play button (not the flask).
  • solution

Lecture Recap

This week we moved beyond Dijkstra to handle negative edge weights and introduced the concept of Minimum Spanning Trees (MSTs).

Bellman-Ford Algorithm

Dijkstra’s greedy strategy relies on the assumption that adding edges can never make a path shorter (non-negative weights). When we have negative edges, this assumption breaks.

Bellman-Ford solves this by relaxing all edges repeatedly. Since a simple shortest path in a graph with $|V|$ vertices can have at most $|V|-1$ edges, running $|V|-1$ iterations guarantees we find the optimal distances.

• Runtime: $O(|V| \cdot |E|)$.
• Negative Cycles: If we can still successfully relax an edge after the $|V|-1$-th iteration, it implies the existence of a reachable negative cycle (a loop where total weight < 0).

Minimum Spanning Trees (MST)

An MST is a connected, acyclic subgraph that includes all vertices $V$ with minimal total edge weight.

The key property MST algorithms exploit is the Cut Property:

• For any cut $(S, V\setminus S)$, a minimum-weight edge crossing the cut must belong to an MST.

We looked at two greedy algorithms that exploit this:

1. Prim’s Algorithm: Grows a single tree from a source node, always adding the cheapest edge connecting the tree to the outside vertices. Like Dijkstra, it uses a Priority Queue and runs in $O((|V|+|E|) \log |V|)$.
2. Boruvka’s Algorithm: A parallel approach where every component simultaneously selects its cheapest outgoing edge. This halves the number of components in each phase, also achieving $O((|V|+|E|) \log |V|)$.

Exercise: Time-Dependent Routing

In this week’s exercise, you are planning a trip where locations are only open during specific windows (Morning, Noon, Evening). The trick here is to model the constraints structurally by building a Layered (or Time-Expanded) Graph.