Skip to content
All tags

#shortest-path

2 posts
learningdeep-diveReading Stanford CS161 Design and Analysis of Algorithms

Dijkstra, Bellman-Ford, and Two Orders of Relaxation | Stanford CS161 Lecture 11

Dijkstra finalizes the minimum estimate and relies on nonnegative weights; Bellman-Ford repeatedly relaxes every edge, spending O(nm) to support negative edges and detect a negative cycle reachable from the source.

#cs161#algorithms#stanford#shortest-path#graph-algorithms
learningdeep-diveReading Stanford CS161 Design and Analysis of Algorithms

Dynamic Programming with Bellman–Ford and Floyd–Warshall | Stanford CS161 Lecture 12

Dynamic programming starts by defining subproblems, derives a recurrence from optimal substructure, and evaluates states in dependency order; Bellman–Ford layers by edge count, while Floyd–Warshall layers by allowed intermediate vertices.

#cs161#algorithms#stanford#dynamic-programming#shortest-path