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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should you use Dijkstra vs Bellman-Ford for shortest path?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use Dijkstra when all edge weights are non-negative: it runs in O((V+E) log V) with a binary heap. Use Bellman-Ford when there are negative edge weights or you need to detect negative-weight cycles: it runs in O(V*E), slower but correct for negative weights. If the graph is unweighted, use BFS for O(V+E) shortest path. LC 787 (Cheapest Flights within K Stops) uses a bounded variant of Bellman-Ford.”}},{“@type”:”Question”,”name”:”How does Kahn's algorithm detect cycles in a directed graph?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Kahn's algorithm processes nodes in topological order by repeatedly removing nodes with in-degree 0. If the graph has a cycle, the nodes in the cycle never reach in-degree 0 and cannot be processed. After the algorithm completes, if the output order contains fewer than V nodes, the graph has a cycle. If it contains all V nodes, the graph is a DAG. This is the standard approach for LC 207 (Course Schedule).”}},{“@type”:”Question”,”name”:”What are Strongly Connected Components (SCCs) and when are they used?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”An SCC is a maximal set of vertices where every vertex is reachable from every other vertex. In a directed graph, SCCs partition the graph. SCCs are used for: detecting cycles (each SCC with 2+ nodes contains a cycle), condensation graphs (contracting each SCC to a single node gives a DAG), analyzing web page link graphs, and solving 2-SAT problems. Kosaraju's algorithm finds all SCCs in O(V+E) using two DFS passes.”}},{“@type”:”Question”,”name”:”What is the time complexity of Floyd-Warshall and when should you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Floyd-Warshall runs in O(V^3) time and O(V^2) space. Use it when V is small (V <= 500) and you need shortest paths between all pairs of vertices. It handles negative edge weights (but not negative cycles). For sparse graphs or large V, running Dijkstra from each source node is faster: O(V * (V+E) log V). Floyd-Warshall is also used for transitive closure and finding the network diameter.”}},{“@type”:”Question”,”name”:”How do you implement topological sort with DFS?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”DFS-based topological sort: mark each node as WHITE (unvisited), GRAY (in progress), or BLACK (done). DFS from each unvisited node. When you first visit a node, mark it GRAY. When DFS finishes for a node, mark it BLACK and prepend it to the result list. If you encounter a GRAY node during DFS, there is a cycle. The result list (reversed post-order) is the topological sort. Both Kahn's and DFS approaches have O(V+E) time complexity.”}}]}
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.