Graph Algorithms: Single-Source Shortest Path Flashcards

A collection of practice questions and answers covering SSSP algorithms including Dijkstra's, Bellman-Ford, and general graph properties based on lecture notes.

What is the primary objective of the Single-Source Shortest Path (SSSP) problem?

To find the minimum-cost paths from a single source vertex $s$ to all other vertices $v$ in a given graph $G(V,E)$.

Define the RELAX operation for an edge $(u, v)$ with weight $w(u,v)$.

The operation checks if a shorter path to $v$ exists through $u$: if $d[v] > d[u] + w(u,v)$, update $d[v] = d[u] + w(u,v)$ and set the predecessor $\pi[v] = u$.

What is the core strategy and constraint of Dijkstra's Algorithm?

Dijkstra's uses a greedy strategy and a priority queue to finalize vertices. It only works on graphs with non-negative edge weights ($w \geq 0$).

What is the time complexity of Dijkstra's Algorithm when using a binary heap?

$$O(E \log V)$$

What is the time complexity of Dijkstra's Algorithm when using a Fibonacci heap?

$$O(E + V \log V)$$

How many times does the Bellman-Ford Algorithm relax all edges in the graph?

It relaxes every edge $(u,v) \in E$ exactly $|V|-1$ times.

How is a negative-weight cycle detected in the Bellman-Ford Algorithm?

If after $|V|-1$ relaxation passes, any edge still satisfies the condition $d[u] + w(u,v) < d[v]$, a negative-weight cycle exists.

What are the primary differences between Dijkstra's and Bellman-Ford?

Dijkstra's is greedy, faster ($O(E \log V)$), but requires non-negative weights. Bellman-Ford uses dynamic programming principles, is slower ($O(VE)$), but handles negative weights and detects negative cycles.

What is the time complexity of the Floyd-Warshall Algorithm, and what type of problem does it solve?

It solves the All-Pairs Shortest Path problem with a time complexity of $O(V^3)$.

What is the fastest algorithm for Shortest Path in Directed Acyclic Graphs (DAGs)?

An algorithm using topological sort followed by relaxation, with a time complexity of $O(V+E)$.

What are the time complexities for Prim's and Kruskal's Minimum Spanning Tree (MST) algorithms?

Prim's Algorithm is $O(E \log V)$, and Kruskal's Algorithm is $O(E \log E)$.

What is the initialization step for shortest path algorithms like Dijkstra and Bellman-Ford?

Set $d[s] = 0$, $d[v] = \infty$ for all $v \neq s$, and $\pi[v] = NIL$ for all $v$.