BFS, Dijkstra & Shortest Paths

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations
• Code:
  • pathCounting - 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 looked at Breadth-First Search (BFS) and shortest path algorithms for weighted graphs.

Breadth-First Search (BFS)

BFS explores level-by-level—processing all vertices at distance $k$ before moving to distance $k+1$. Using a queue (FIFO), BFS runs in $O(|V| + |E|)$ time and finds shortest paths in unweighted graphs by visiting vertices in order of increasing distance.

Shortest Paths in Weighted Graphs

Once we add edge weights, computing shortest paths gets a little more complicated… We started by looking at Directed Acyclic Graphs (DAGs).

Because DAGs have no cycles, we can linearize the graph using a topological sort. By processing vertices $v_1, …, v_n$ in topological order (starting with $v_1​=s$), we can find shortest paths using Dynamic Programming: $$d(s, v_k) = \min_{\substack{(v_i, v_k) \ i < k}} {d(s, v_i) + c(v_i, v_k)}$$ This produces a runtime of $O(|V| + |E|)$ in total.

Dijkstra’s Algorithm

For general graphs, we don’t have a topological ordering. Dijkstra’s algorithm builds a distance-based ordering greedily: always process the closest unprocessed vertex next, maintaining tentative distances and relaxing edges as we go.

Runtime: $O((|V| + |E|) \log |V|)$ with a min-heap.

Critical assumption: Edge weights must be non-negative! With negative edges, the greedy choice can fail.

In this week’s coding exercise, you’ll use a modified BFS to count the number of shortest paths between two vertices. Try to prove the correctness and runtime as well (see slides).