Graph Algorithms: Paths, Trees, and Network Flows

TAKEAWAYS:

• Graphs model relationships: Use vertices for entities (e.g., cities, users) and edges for connections (e.g., roads, friendships) with weights for costs/durations.
• Shortest paths: Dijkstra’s algorithm finds the quickest route from a source (e.g., Pathao’s delivery optimization), while Floyd-Warshall computes all-pairs shortest paths (e.g., NTC’s network traffic routing).
• Minimum spanning trees (MST): Kruskal’s and Prim’s algorithms connect all nodes with minimal total edge weight (e.g., Ncell’s base station network design).
• Topological sorting: Orders tasks with dependencies (e.g., course prerequisites at TU/PU or app installation sequences on Android).
• Network flows: Ford-Fulkerson solves max-flow/min-cut problems (e.g., eSewa’s load balancing across servers or Daraz’s warehouse distribution).
• Time complexity matters: Memorize $O(E\log V)$ for Kruskal, $O(V^2)$ for Floyd-Warshall, and $O(VE)$ for Ford-Fulkerson to match exam questions.

1. Graph Basics: Representations and Traversals

Graphs are non-linear data structures consisting of vertices (nodes) and edges (connections). They model relationships like roads, social networks, or computer networks.

Key Definitions

• Directed vs. Undirected: Edges have a direction (e.g., one-way roads) or not (e.g., friendships).
• Weighted vs. Unweighted: Edges may have values (e.g., distance, cost) or not.
• Adjacency Matrix: A $V\times V$ matrix where $A[i][j]=\text{weight}$ if edge $(i,j)$ exists. Space: $O(V^2)$.
• Adjacency List: Each vertex stores a list of connected vertices and edge weights. Space: $O(V+E)$.

Traversals

• BFS (Breadth-First Search): Explores all neighbors at the present depth before moving deeper. Use case: Shortest path in unweighted graphs (e.g., finding the fastest route in Kathmandu’s traffic without considering road lengths).

  from collections import deque
  def BFS(graph, start):
      visited = {start: True}
      queue = deque([start])
      while queue:
          vertex = queue.popleft()
          for neighbor in graph[vertex]:
              if neighbor not in visited:
                  visited[neighbor] = True
                  queue.append(neighbor)
      return visited
  

  Trace for Graph {0: [1,2], 1: [2], 2: [3], 3: [4]} (start=0):

  Step	Queue	Visited
  1	[0]	{0}
  2	[1,2]	{0,1,2}
  3	[3]	{0,1,2,3}
  4	[4]	{0,1,2,3,4}

• DFS (Depth-First Search): Explores as far as possible along a branch before backtracking. Use case: Topological sorting (e.g., course prerequisites at TU).

  def DFS(graph, start, visited=None):
      if visited is None:
          visited = set()
      visited.add(start)
      for neighbor in graph[start]:
          if neighbor not in visited:
              DFS(graph, neighbor, visited)
      return visited
  

2. Shortest Path Algorithms

Dijkstra’s Algorithm

Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edges. Steps:

1. Initialize distances: $\text{dist}[source]=0$, others $\infty$.
2. Use a priority queue to pick the vertex $u$ with the smallest tentative distance.
3. Relax edges: For each neighbor $v$ of $u$, update $\text{dist}[v]=\min (\text{dist}[v],\text{dist}[u]+\text{weight}(u,v))$.

Example: Pathao’s delivery optimization. Graph:

S --5--> T
|      / \
10    3   1
|   /     \
A --2--> C

• Shortest path from S to C: $S\to T\to C$ (cost = 5 + 1 = 6).
• Why not $S\to A\to C$? Because $10+2=12>6$.

Time Complexity:

• With binary heap: $O((V+E)\log V)$.
• With Fibonacci heap: $O(E+V\log V)$.

Floyd-Warshall Algorithm

Computes all-pairs shortest paths in a graph (even with negative weights, but no negative cycles). Dynamic Programming Approach:

• Let $\text{dist}[i][j]$ = shortest distance from $i$ to $j$.
• Initialize $\text{dist}[i][j]=\text{weight}(i,j)$ if edge exists, else $\infty$.
• For each intermediate vertex $k$, update: $\text{dist}[i][j]=\min (\text{dist}[i][j],\text{dist}[i][k]+\text{dist}[k][j])$.

Example: NTC’s network traffic routing between 3 cities. Graph:

      A
    / | \
  1/  |2\5
  /   | \
B-----3--C

Initial Distances:

A: [0, 1, 5]
B: [1, 0, 3]
C: [5, 3, 0]

After considering A as intermediate:

A: [0, 1, 4]  (B→A→C = 1+5=6 > B→C=3, so no update)
B: [1, 0, 3]
C: [4, 3, 0]  (A→C=5 > A→B→C=1+3=4)

Final Shortest Paths:

• $A\to C$: Direct (5) vs. $A\to B\to C$ (1 + 3 = 4). Choose 4.

Time Complexity: $O(V^3)$.

3. Minimum Spanning Trees (MST)

Connects all vertices with the minimum total edge weight (no cycles). Applications:

• Ncell’s base station network (minimize cable cost).
• TU’s campus Wi-Fi setup (connect buildings with least fiber).

Kruskal’s Algorithm

1. Sort all edges by weight.
2. Add edges one by one, skipping those that form a cycle (use Union-Find/Disjoint Set).
3. Stop when $V-1$ edges are added.

graph TD
    A["Sort edges: (A-B,2), (B-C,3), (A-C,5), (A-D,6), (C-D,7)"]
    A --> B["Add A-B (2)"]
    B --> C["Add B-C (3)"]
    C --> D["Add A-C (5) → Cycle! Skip"]
    D --> E["Add A-D (6)"]
    E --> F["MST: A-B-C-D, Total=2+3+6=11"]

Example: Daraz’s warehouse distribution. Graph:

A --2-- B
| \    / |
5   3  1
|   \/  |
C --7-- D

MST Edges: $(A-B,2)$, $(B-D,1)$, $(B-C,3)$. Total cost = 6.

Time Complexity: $O(E\log E)$ (due to sorting).

Prim’s Algorithm

1. Start with any vertex and add the smallest edge connecting the MST to a new vertex.
2. Repeat until all vertices are included.

Time Complexity:

• With binary heap: $O(E\log V)$.
• With Fibonacci heap: $O(E+V\log V)$.

4. Topological Sorting

Orders vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $(u,v)$, $u$ comes before $v$. Applications:

• Course prerequisites at TU/PU (e.g., "Algorithms" must be taken before "Advanced Algorithms").
• Task scheduling in Android app installations.

Algorithm (Kahn’s):

1. Compute in-degree (number of incoming edges) for each vertex.
2. Enqueue vertices with in-degree 0.
3. For each dequeued vertex, reduce in-degree of its neighbors. If in-degree becomes 0, enqueue it.

Example: TU’s course prerequisites. Graph:

Algorithms → Advanced Algorithms
Data Structures → Algorithms
OS → Advanced Algorithms

Topological Order: Data Structures, OS, Algorithms, Advanced Algorithms.

Time Complexity: $O(V+E)$.

5. Network Flow: Ford-Fulkerson Algorithm

Solves max-flow/min-cut problems (e.g., eSewa’s server load balancing). Key Definitions:

• Flow Network: Directed graph with source $s$, sink $t$, and capacities on edges.
• Residual Graph: Shows remaining capacity after pushing flow.
• Augmenting Path: Path from $s$ to $t$ in the residual graph with available capacity.

Algorithm:

1. Initialize flow $f(e)=0$ for all edges.
2. Find an augmenting path $P$ in the residual graph.
3. Push flow along $P$: $f(e)=\min (\text{residual capacity})$.
4. Update residual capacities.
5. Repeat until no augmenting path exists.

Example: eSewa’s server load balancing. Graph:

s --3--> a --3--> t
|       /
2      /
|     /
b --2--> t

• Max flow: $s\to a\to t$ (3) + $s\to b\to t$ (2) = 5.
• Min cut: $\{s,a,b\}$ and $\{t\}$, capacity = 3 (s→a) + 2 (s→b) = 5.

Time Complexity:

• $O(f\cdot E)$, where $f$ is the max flow (can be $O(V\cdot E^2)$ with BFS for augmenting paths).

In the Real World

1. Pathao’s Delivery Optimization
   • Idea Used: Dijkstra’s algorithm for shortest paths.
   • How: Pathao’s backend calculates the fastest route for delivery partners from the restaurant to the customer’s location, avoiding traffic-heavy roads in real-time. The graph represents streets as edges with weights = travel time, and restaurants/customers as vertices.

2. Ncell’s Base Station Network

   • Idea Used: Minimum Spanning Tree (Prim’s/Kruskal’s).
   • How: Ncell connects its base stations across Nepal with the least amount of fiber optic cable. The graph’s vertices are base stations, and edges are possible cable routes with weights = cable cost. MST ensures full coverage at minimal expense.

3. eSewa’s Server Load Balancing

   • Idea Used: Ford-Fulkerson max-flow algorithm.
   • How: During peak hours (e.g., Dashain/Tihar), eSewa distributes transactions across multiple servers to prevent overload. The flow network models servers as nodes, transaction capacity as edge weights, and the algorithm ensures no server is overloaded beyond its capacity.

4. NTC’s Internet Routing

   • Idea Used: Floyd-Warshall for all-pairs shortest paths.
   • How: NTC’s backbone network must route data packets between all major cities (Kathmandu, Pokhara, Biratnagar) efficiently. Floyd-Warshall precomputes the shortest path between every pair of cities, updating routes dynamically if a link fails.

5. TU/PU Course Prerequisites

   • Idea Used: Topological sorting.
   • How: The university’s course catalog is a DAG where edges represent prerequisites. Topological sorting ensures students register for courses in the correct order (e.g., "Data Structures" before "Algorithms").

6. Exam Tip

1. Graph Representations:

   • Always compare adjacency matrix vs. list in terms of space and query time. Matrix is $O(1)$ for edge checks but wastes space for sparse graphs.
   • Exam Question: "When would you use an adjacency list over a matrix?" → Answer: For sparse graphs ($E\ll V^2$).

2. Shortest Paths:

   • Dijkstra’s is for single-source shortest paths in graphs with non-negative weights.
   • Floyd-Warshall is for all-pairs shortest paths (even with negative weights, but no negative cycles).
   • Trace steps: Show the priority queue or distance table after each iteration (like the examples above).

3. MST Algorithms:

   • Kruskal’s uses Union-Find to detect cycles. Prim’s uses a priority queue.
   • Exam Pitfall: Forgetting to sort edges in Kruskal’s or missing the cycle check.
   • Worked Example: For a graph with 4 vertices and 5 edges, draw the MST and label the total weight.

4. Topological Sorting:

   • Kahn’s algorithm (BFS-based) is easier to trace than DFS-based methods.
   • Exam Question: "Can a graph with a cycle be topologically sorted?" → Answer: No, because it violates the acyclic property.

5. Network Flow:

   • Residual graph is critical. Always update capacities in both directions.
   • Min-cut = Max-flow: This is a theorem, not just a coincidence. Prove it for small graphs in exams.

6. Time Complexities:

   • Memorize these for quick marks:
     • Dijkstra (binary heap): $O((V+E)\log V)$.
     • Floyd-Warshall: $O(V^3)$.
     • Kruskal: $O(E\log E)$.
     • Prim: $O(E\log V)$.
     • Ford-Fulkerson: $O(f\cdot E)$.

7. Practical Scenarios:

   • Bank Loan Interest: Model as a flow network where the source is the bank, the sink is the borrower, and edges represent loan amounts and interest rates.
   • Traffic Routes in Kathmandu: Use Dijkstra’s to find the fastest route avoiding congested areas (edges with high "traffic weight").
   • Daraz’s Order Fulfillment: Topological sort to sequence tasks (pick, pack, ship) with dependencies (e.g., "pack" depends on "pick").

Final Advice:

• Draw graphs: Even if the exam provides a figure, redraw it to visualize steps.
• Trace algorithms: Show state after each step (like the tables/mermaid diagrams above).
• Relate to real life: Examiners love answers that connect theory to Nepalese contexts (e.g., NTC, Pathao, Ncell).