Dijkstra’s Algorithm – Shortest Path (Non-negative Weights)
import heapq
from collections import defaultdict
def dijkstra(graph: dict, start: int, n: int) -> list[int]:
# graph[u] = [(v, weight), ...]
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry - skip
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
# O((V + E) log V) with binary heap
# ONLY correct for non-negative edge weights
# For negative weights: use Bellman-FordBellman-Ford – Shortest Path with Negative Weights
def bellman_ford(edges: list, n: int, src: int) -> list[int]:
# edges = [(u, v, weight), ...]
dist = [float('inf')] * n
dist[src] = 0
# Relax all edges n-1 times
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative-weight cycles
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return [] # negative cycle detected
return dist
# O(V * E) time - slower than Dijkstra but handles negative weights
# LC 787: Cheapest Flights within K Stops (bounded Bellman-Ford)Topological Sort – Kahn’s Algorithm (BFS)
from collections import deque
def topo_sort(n: int, prereqs: list[list[int]]) -> list[int]:
# prereqs = [[course, prereq], ...] (prereq must come before course)
graph = defaultdict(list)
in_degree = [0] * n
for course, prereq in prereqs:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else [] # empty = cycle detected
# O(V + E). Used for: LC 207/210 Course Schedule, build ordering, dependency resolutionStrongly Connected Components – Kosaraju’s Algorithm
def kosaraju_scc(n: int, edges: list[list[int]]) -> list[list[int]]:
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = [False] * n
finish_order = []
def dfs1(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs1(v)
finish_order.append(u)
for i in range(n):
if not visited[i]:
dfs1(i)
visited = [False] * n
sccs = []
def dfs2(u, component):
visited[u] = True
component.append(u)
for v in rev_graph[u]:
if not visited[v]:
dfs2(v, component)
for u in reversed(finish_order):
if not visited[u]:
component = []
dfs2(u, component)
sccs.append(component)
return sccs
# O(V + E). Use for: finding cycles in directed graphs, condensation graphFloyd-Warshall – All-Pairs Shortest Path
def floyd_warshall(n: int, edges: list) -> list[list[int]]:
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
for k in range(n): # intermediate node
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# O(V^3) time, O(V^2) space
# Use for small graphs (V <= 500), transitive closure, network diameter
# LC 1334: Find the City with Smallest Number of Neighbors at ThresholdWhen to Use Which Algorithm
Decision tree: Do you need shortest path from one source? -> Yes: Are weights non-negative? -> Dijkstra O((V+E) log V). Are there negative weights? -> Bellman-Ford O(VE). Do you need all-pairs shortest paths? -> Floyd-Warshall O(V^3) for small graphs, or run Dijkstra from each node O(V(V+E)logV) for sparse graphs. Do you need ordering with dependencies? -> Topological sort (Kahn’s BFS or DFS post-order). Do you need to find cycles or SCCs in directed graphs? -> Kosaraju or Tarjan SCC. Is the graph unweighted? -> BFS gives shortest path in O(V+E). Common interview patterns: network delay time (LC 743) = Dijkstra; course schedule (LC 207) = topological sort + cycle detection; number of islands variations = BFS/DFS; critical connections (LC 1192) = Tarjan’s bridges algorithm.
Meta coding interviews heavily test graph algorithms for social network traversal. Review patterns used at Meta interview: graph algorithms and social network traversal.
LinkedIn interviews test graph algorithms for connection networks and recommendations. See patterns for LinkedIn interview: graph algorithms for professional networks.
Uber interviews test shortest-path algorithms (Dijkstra, A*) for ride routing. Review common patterns for Uber interview: graph algorithms for routing and mapping.