Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest paths from a single source to all other nodes in a weighted graph.
Key Constraint: It requires that there are no negative weighted edges (use Bellman-Ford for graphs with negative edges).
Example where Dijkstra fails:
B Set d[A]=0. [A:0, B:inf, C:inf, D:inf]
3/ \-2 Visit A.
A D
1\ /7
C
Topological Sort
Topological sorting is applicable only to Directed Acyclic Graphs (DAGs). It orders the vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.
BFS-based Topological Sort: Construct from Start to End
Idea: Initialize a queue with nodes that have indegree = 0. Process nodes from the queue, and for each processed node, reduce the indegree of its neighbors. When a neighbor’s indegree becomes 0, add it to the queue.
Components:
- queue[]: to hold 0-indegree nodes
- indegree[V]: holds indegree of each node
Time Complexity: O(n + m), since we order n nodes and process each of the m edges while reducing indegrees Space Complexity: O(n), due to the queue and indegree array
DFS-based Topological Sort: Construct from End to Start
Idea: Ensure that every follow-up node is visited AFTER the current node.
So, we follow: dfs(node): for all neighbors {dfs(neighbor)}; res.append(node)
def dfs(node):
visited[node] = True
for neighbor in adj[node]: # 1. First, visit all following nodes
if not visited[neighbor]:
dfs(neighbor)
res.append(node) # 2. Then, add the current node
-----------------------------------------------------------------------
for node in adj: # Call dfs from every node
if not visited[node]:
dfs(node)
res.reverse() # List is in reverse, so reverse it!
return res
Components:
- visited[V]: tracks which vertices have been visited
- res[]: holds the topological sort in reverse order
Time Complexity: O(n + m), since we create a visited set of size O(n) and process each of the O(m) edges Space Complexity: O(n), due to recursion stack and visited set