Shortest Path Algorithms and Graph Complexities

This flashcard set covers SSSP algorithms like Dijkstra's and Bellman-Ford, their various implementation complexities based on data structures (Binary Heap, Sorted/Unsorted Lists), and Minimum Spanning Trees (MST).

Dijkstra's Algorithm

A greedy Single Source Shortest Path (SSSP) algorithm that does not allow negative weights.

Edge Relaxation

A process where if the next edge is smaller, the path is relaxed and replaced with the smaller value to check if it offers a better path.

Dijkstra's Complexity (Adjacency List + Binary Heap)

Building PQ: $O(V)$; Popping all V: $O(V \times \text{log}(V))$; Relaxing all E: $O(E \times \text{log}(V))$; Total: $O((V + E) \times \text{log}(V))$.

Dijkstra's Complexity (Adjacency List + Sorted List)

Building PQ: $O(V)$; Popping all V: $O(V)$ (Total $O(V \times V)$, transcript implies $V^*$); Relaxing all E: $O(E)$ (Total $O(E \times V)$, transcript implies $E^*$); Total: $O(EV)$.

Dijkstra's Complexity (Adjacency List + Unsorted List)

Building PQ: $O(V)$; Popping all V: $O(V \times V)$; Relaxing all E: $O(E \times 1)$; Total: $O(V^2)$.

Dijkstra's Complexity (Adjacency Matrix + Binary Heap)

Building PQ: $O(V)$; Popping all V: $O(V \times \text{log}(V))$; Relaxing all E: $O(V^2 \times \text{log}(V))$; Total: $O(V^2 \times \text{log}(V))$.

Dijkstra's Complexity (Adjacency Matrix + Sorted List)

Building PQ: $O(V)$; Popping all V: $O(V)$; Relaxing all E: $O(V^2 \times V)$; Total: $O(V^3)$.

Dijkstra's Complexity (Adjacency Matrix + Unsorted List)

Building PQ: $O(V)$; Popping all V: $O(V \times V)$; Relaxing all E: $O(V \times V)$; Total: $O(V^3)$.

Bellman Ford

A shortest path algorithm that works with negative weights but cannot be used with negative cycles; it produces up to $N - 1$ passes.

BFS Complexity

$$O(V + E)$$

DFS Complexity

$$O((V + E) \times \text{log}(V))$$

Bellman-Ford Complexity

$$O(V \times E)$$

MST (Minimum Spanning Tree)

A graph objective that is not a shortest path, but aims to minimize the total sum of ALL edges; implemented via the Prim Algorithm.