Design and Analysis of Algorithms

Answer: (iv) parallel edges

Adjacency matrix A[i][j]=1 if edge exists. It shows node count (dimension), edges, direction (asymmetry for digraph). Simple 0/1 matrix cannot represent multiple edges between same pair (multigraph) without counts.

Answer: (i) 2

Graph with >3 vertices but only 2 edges is disconnected forest; at most needs 2 colors (bipartite, no odd cycle). Unless edge is loop, 2 colors suffice.

Answer: (ii) Kruskal's algorithm (also Prim's)

Kruskal (edge greedy) and Prim (vertex greedy) both find MST. Dijkstra is shortest path, Bellman-Ford handles negatives, Floyd all-pairs.

Answer: (i) O(|V|+|E|)

BFS visits each vertex and edge once using adjacency list.

Answer: (iii) Breadth First Search

BFS gives shortest path in unweighted graph (by levels). DFS not guaranteed, MST algorithms not for shortest path.

Answer: (ii) Stack

DFS uses stack (explicit or recursion). BFS uses queue.

Answer: (ii) Kruskal's Algorithm

Explanation:

• Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is found by greedy MST algorithms:
  • Prim's: grows tree from a vertex, repeatedly adds minimum-weight edge crossing cut. $O(E \log V)$.
  • Kruskal's: sorts all edges, adds edges in increasing order skipping those forming a cycle (using Union-Find). $O(E \log E)$.
• Dijkstra's, Bellman-Ford, Floyd-Warshall solve shortest paths, not MST.
• Both Prim's and Kruskal's are valid; here the option listed is Kruskal's.

Correct choice: (ii) Kruskal's Algorithm (Prim's would also be correct if listed).

Answer: (ii) Prim's algorithm

Explanation:

• MST algorithms: Prim's ($O(E \log V)$ with heap, $O(E+V\log V)$ with Fibonacci heap) and Kruskal's ($O(E \log E)$) both find Minimum Spanning Tree.
• Dijkstra's, Bellman-Ford, Floyd-Warshall are shortest-path algorithms, not MST.
• Among given options, (ii) Prim's is the only MST algorithm.

Note: Q81 lists Kruskal's as option (ii) — both Prim's and Kruskal's are correct MST algorithms; the exam chooses whichever appears in options.

Correct choice: (ii)

Answer: (ii) $V-1$

Explanation:

• A spanning tree of a connected graph with $V$ vertices is a tree that includes all $V$ vertices.
• Any tree with $V$ vertices has exactly $V-1$ edges (proof by induction; also $|E|=|V|-1$ characterizes trees among connected graphs).
• Edge weights (positive or otherwise) do not affect the count — any spanning tree, regardless of weight, has $V-1$ edges. Minimum spanning tree also has $V-1$ edges; weight affects which edges, not how many.
• Additional edges would create a cycle → not a tree.

Correct choice: (ii) $V-1$ (if graph disconnected, spanning forest has $V-c$ edges for $c$ components).

Answer: (ii) Floyd-Warshall's Algorithm

Explanation:

• All-Pairs Shortest Path (APSP) = shortest distances between every pair $(i,j)$.
• Floyd-Warshall: DP, $\Theta(V^3)$, handles negative edges (no negative cycles), simple triple loop: dist[k][i][j]=min(dist[k-1][i][j], dist[k-1][i][k]+dist[k-1][k][j]).
• Dijkstra's = Single-Source Shortest Path for non-negative weights; to get APSP you must run it $V$ times → $O(V E \log V)$, but not the canonical APSP algorithm.
• Prim's / Kruskal's = MST algorithms, unrelated to shortest paths.

Correct choice: (ii) Floyd's Warshall's (also Johnson's algorithm is another APSP method).

Answer: (iii) Directed Acyclic Graphs (DAGs)

Explanation:

• Topological sorting is a linear ordering of vertices such that for every directed edge $u \to v$, $u$ appears before $v$.
• Such ordering exists iff the graph has no directed cycle. If a cycle exists, no linear extension can satisfy all precedence constraints.
• Undirected graphs have no direction → concept not defined (except trivial cases). Trees (when oriented as DAG) can be topologically sorted, but not all trees as undirected structures.
• Weighted vs. unweighted is irrelevant; only acyclicity matters.

Algorithm: DFS post-order reversed or Kahn's BFS with indegree queue, both $O(V+E)$.

Correct choice: (iii)

Answer: (iii) Ford-Fulkerson

Explanation:

• Maximum Flow problem: given network with capacities $c(u,v)$, find flow $f$ maximizing value from $s$ to $t$ respecting capacity and conservation.
• Ford-Fulkerson method (and Edmonds-Karp $O(VE^2)$ implementation, Dinic, Push-relabel) repeatedly finds augmenting paths in residual graph and augments until none remain; correctness via max-flow min-cut theorem.
• Kruskal/Prim = MST, Floyd-Warshall = APSP, not flow.

Correct choice: (iii) Ford-Fulkerson (also Edmonds-Karp, Dinic are refinements).

Answer: (iii) $O(V+E)$

Explanation:

• Topological sort via DFS: run DFS on DAG, push vertex onto stack when finished (post-order), then reverse. Each vertex visited once, each edge examined once.
• Time = $O(V)$ for initialization + $O(V+E)$ for DFS = $O(V+E)$.
• Kahn's algorithm (BFS with indegree) is also $O(V+E)$.
• $O(V^2)$ / $O(E^2)$ would be for adjacency matrix without adjacency lists; with adjacency list it's linear.

Correct choice: (iii) $O(V+E)$

Minimum Cost Spanning Tree & Kruskal's Algorithm

Definition

For connected undirected weighted graph $G(V,E,w)$, a spanning tree is acyclic connected subgraph spanning all $V$ with $|V|-1$ edges. Minimum Cost Spanning Tree (MST) / Minimum Spanning Tree is spanning tree minimizing $\sum_{e\in T} w(e)$. If distinct weights, MST unique; otherwise multiple. Cut property and cycle property characterize MST.

Kruskal's Algorithm (Greedy)

Kruskal(G):
  T=∅
  sort E by weight ascending
  make Union-Find structure for V
  for (u,v) in sorted E:
    if Find(u) != Find(v):
      T.add((u,v))
      Union(u,v)
      if |T|==|V|-1: break
  return T

Correctness via cut property: smallest edge crossing any cut belongs to some MST; cycle property prevents adding cycle edge.

Complexities: Sorting $O(E\log E)$, Union-Find $O(E \alpha(V))$ → total $O(E\log E)$ ($\alpha$ inverse Ackermann). Space $O(V)$.

Example

Graph: $V=\{A,B,C,D\}$, edges: AB1, AC3, BC3, BD4, CD2

• Sorted: AB1, CD2, AC3, BC3, BD4
• Add AB1 (A|B), add CD2 (C|D), add AC3 (merges {A,B} with {C,D} → {A,B,C,D}), skip BC3 (would cycle A-B-C), skip BD4. MST weight 1+2+3=6 edges AB,CD,AC.

Kruskal vs Prim

• Kruskal edge-based, good for sparse graphs; Prim vertex-based, good for dense ($O(E\log V)$ with heap, $O(V^2)$ naive).
• Both optimal, choice depends on density and structure.

BFS vs DFS — Algorithmic Comparison

Aspect	BFS (Breadth-First)	DFS (Depth-First)
Strategy	Level-order using queue; explores all neighbors of current level before going deeper.	Depth-first using stack (recursion); goes as deep as possible, backtracks.
Algorithm	queue Q={s}; visited[s]; while Q not empty: v=dequeue; for each w adj to v if not visited: visit, enqueue	DFS(v): visited[v]=true; for each w adj to v if not visited: DFS(w) (or iterative stack)
Time	$O(V+E)$ with adjacency list, $O(V^2)$ with matrix.	$O(V+E)$ / $O(V^2)$ same.
Space	$O(V)$ queue + visited; worst $O(V)$ (broad level) — more memory for wide graphs.	$O(V)$ stack/recursion, worst $O(V)$ depth; often less memory for deep narrow graphs, but recursion may overflow.
Tree vs Stack	Finds shortest path (fewest edges) in unweighted graph; level = distance from source.	Finds any path, not shortest; useful for connectivity, cycles, topological sort, strongly connected components.
Traversal Order	Visiting order by distance layers: s, all distance1, then distance2... (example linear).	Visiting order by depth: s→first neighbor→its neighbor... deeper first, pre-order.
Applications	Shortest path unweighted, peer-to-peer, web crawling breadth, social network 1st-degree, bipartite check, Ford-Fulkerson (Edmonds-Karp uses BFS).	Topological sort, cycle detection, articulation points, Kosaraju SCC, maze solving, backtracking, solving puzzles.
Completeness	Complete on infinite graphs with finite branching (if solution at finite depth).	Not complete on infinite depth without visited set.

Example on graph A→B,C etc: BFS from A order: A, B,C, D,E (level1,2) vs DFS order: A,B,D,E,C etc depending on adjacency order.

Hybrid: Iterative deepening DFS combines BFS completeness with DFS memory.

BFS Algorithm — Detail & Time Complexity

Algorithm (Queue)

BFS(G, s):
  for each v in V: color[v]=WHITE, dist[v]=∞, parent[v]=NIL
  color[s]=GRAY; dist[s]=0; Q=queue(); ENQUEUE(Q,s)
  while Q ≠ ∅:
    u=DEQUEUE(Q)
    for each v in Adj[u]:
      if color[v]==WHITE:
        color[v]=GRAY; dist[v]=dist[u]+1; parent[v]=u; ENQUEUE(Q,v)
    color[u]=BLACK

Variants output traversal order by recording dequeue order.

Example

Graph A→B,C etc, start A: queue [A] → visit A enqueue B,C → queue [B,C] → dequeue B enqueue D → [C,D] → dequeue C enqueue E → [D,E] → etc. Order A,B,C,D,E.

Time Complexity

• With adjacency list: Each vertex enqueued/dequeued once $O(V)$, each adjacency list scanned once $O(E)$ → $O(V+E)$.
• With adjacency matrix: scan row of $V$ entries per vertex → $O(V^2)$.

Space $O(V)$ for queue + color/dist arrays.

Properties

• Computes single-source shortest path (in edges) for unweighted graphs: dist[v] = minimum number of edges s→v.
• Produces BFS tree (parent pointers).
• Used as subroutine in Edmonds-Karp max flow, bipartite testing (2-coloring by levels), connected components.
• BFS levels correspond to distance layers; can also detect cycles / test bipartiteness by parity.

Shortest-Path System Design — Choice by Edge Weight

City = graph vertices = locations, edges = roads, weight = length/time.

(i) All roads equal length (unweighted)

Algorithm: Breadth-First Search (BFS)

• Reason: BFS explores in increasing distance (number of edges) layers → first time target dequeued, its distance is minimum edges. $O(V+E)$ with adjacency list, no need for priority queue.
• Alternative: Dijkstra with uniform weight 1 reduces to BFS (overhead wasteful).
• Use queue: dist[s]=0, push neighbors.

(ii) Varying lengths, no negative weights (positive weighted)

Algorithm: Dijkstra's Algorithm (with binary heap $O((V+E)\log V)$, Fibonacci $O(E+V\log V)$)

• Reason: Greedy choice of smallest tentative distance; proof relies on non-negative weights (once vertex extracted, distance final). Handles varying positive weights optimal.
• Steps: dist[s]=0, priority queue keyed by dist; repeatedly extract min $u$, relax edges $u→v$: if $dist[u]+w(u,v)<dist[v]$ update.
• Why not Bellman-Ford? Correct but $O(VE)$ slower, unnecessary without negatives.
• Why not BFS? BFS assumes uniform weight → would give wrong result.

(iii) Some roads have negative lengths (negative weights, but no negative cycles reachable)

Algorithm: Bellman-Ford Algorithm ($O(VE)$) — or SPFA / Johnson's if many sources.

• Reason: Dijkstra fails with negative edges (greedy finality broken; example $s→a$ weight5, $s→b$ weight6, $b→a$ weight -4 → shortest to $a$ is via $b$ (2) not direct 5, Dijkstra would finalize $a$ too early).
• Bellman-Ford relaxes all edges $V-1$ times, then one more pass detects negative cycles.
• If negative cycle exists, shortest path undefined ($-\infty$); Bellman-Ford reports it.
• If graph large and only few negatives, could use Johnson's ($O(VE\log V)$) reweighting.

Summary Table

Case	Weights	Algorithm	Time	Handles negatives?
(i)	uniform	BFS	$O(V+E)$	No need
(ii)	$≥0$ varying	Dijkstra (heap)	$O(E\log V)$	No
(iii)	arbitrary (no neg cycle)	Bellman-Ford	$O(VE)$	Yes + detects cycle

Justification: Choose simplest correct algorithm for constraint; progressing BFS → Dijkstra → Bellman-Ford as generality increases, trading speed for correctness.

Bellman-Ford & Negative Weight Cycle Detection

Bellman-Ford Recap

Input: directed weighted graph $G(V,E,w)$, source $s$.

Init: dist[s]=0, dist[v]=∞ for v≠s
repeat V-1 times:
  for each edge (u,v) in E:
    if dist[u]+w(u,v) < dist[v]: dist[v]=dist[u]+w(u,v); parent[v]=u

After $V-1$ iterations, $dist[v]$ = shortest path weight from $s$ using ≤ $V-1$ edges (any simple path has ≤ $V-1$ edges). Complexity $O(VE)$.

Detecting Negative Cycle

Extra $V$-th iteration:

for each edge (u,v) in E:
  if dist[u]+w(u,v) < dist[v]: // still relaxable
    then v is reachable from a negative cycle (and from s)
    report "Negative cycle exists reachable from s"

Why? In graph without negative cycles, after $V-1$ rounds no edge can be relaxed (shortest paths have converged). If an edge can still be relaxed, the shortest path would require ≥ $V$ edges → must repeat a vertex → contains a cycle. Since total weight decreased by going around cycle, that cycle is negative. Moreover, repeated relaxation can propagate $-\infty$ along all vertices reachable from the cycle.

Finding cycle: To retrieve cycle, follow parent pointers from $v$ $V$ times to get into cycle, then walk until repeat.

Example

Triangle $s→a$ (1), $a→b$ (-2), $b→a$ (-2): sum $b→a→b$ = -4 negative. After $V-1=2$ iterations dist keeps decreasing; Vth iteration detects relaxation.

Scope

• Detects only cycles reachable from $s$. To detect any negative cycle in graph, add super-source $s'$ with 0-edge to all vertices and run Bellman-Ford.
• Dijkstra cannot detect/develop must not be used with negatives.

Bellman-Ford from Source 3 on Graph with 5 Nodes (Undirected weighted)

Adjacency matrix (symmetric): edges weights:
1-2:1, 1-4:1, 1-5:4, 1-3:8, 2-4:4, 2-3:12, 2-5:9, 3-4:7, 3-5:3, 4-5:2

Treat undirected as two directed edges.

Initialization

dist[3]=0, others ∞.
dist = [∞,∞,0,∞,∞] indexed 1..5.

Relax edges $V-1=4$ times (order 1→5 edges):

We can simulate quickly (using undirected edges both directions).

Iter1:

• From 3: to1 via8 → dist1=8, to2 via12→12, to4 via7→7, to5 via3→3
• From1 (now8): 1-2 (1): 8+1=9<12 → dist2=9; 1-4(1):8+1=9>7 no; 1-5(4):8+4=12>3 no
• From2(9): 2-4(4):9+4=13>7; 2-5(9):18>3
• From4(7): 4-5(2):7+2=9>3
• From5(3): 5-1(4):7<8 → dist1=7; 5-4(2):5<7 → dist4=5; 5-2(9):12>9? 3+9=12>9 no ; 5-3 done
  After iter1: dist=[7,9,0,5,3]

Iter2:

• Check all edges: 1-2:7+1=8<9 → dist2=8; 1-4:7+1=8>5; 1-3:7+8=15>0; 2-4:8+4=12>5; 3-4:0+7=7>5; 4-5:5+2=7>3; 1-5:7+4=11>3; etc. Improvement dist2 to8.
• After iter2: [7,8,0,5,3]

Iter3:

• 2-1:8+1=9>7; 4-1:5+1=6<7 → dist1=6! ; Then 1-2 again 6+1=7<8 → dist2=7 ; Then 1-3 14>0 ; Now stable.
  After iter3: dist=[6,7,0,5,3] ?? Check 4-5:5+2=7>3, 5-1:3+4=7>6, 5-4:3+2=5 equal, 2-3:7+12=19>0, 4-3:5+7=12>0. So dist=[6,7,0,5,3]

Iter4: No change → converged.

Final distances from 3:

• dist[1]=6 via 3-5(3)+5-4(2)+4-1(1)=3+2+1=6 (path 3-5-4-1)
• dist[2]=7 via 3-5-4-1-2 =3+2+1+1=7 or 3-5-4-2? 3+2+4=9 longer, so 7 is min
• dist[3]=0
• dist[4]=5 via 3-5-4 (3+2)
• dist[5]=3 direct

Check alternative 3-1 direct 8 >6, so indirect via 5-4 shorter (graph has small edges).

No negative edges → Vth iteration detects no negative cycle (no relaxation).

Time Complexity of Bellman-Ford

$O(VE)$; with adjacency matrix $E=\Theta(V^2)$ → $O(V^3)$; with list $E$ → $O(VE)$. Space $O(V)$. Here $V=5$, $E=10$ undirected (20 directed) → ~80 relaxations.

Graph from Adjacency List + BFS

Adjacency List (directed weighted, weight in brackets)

• A → B(10), C(3)
• B → C(1), D(5)
• C → B(4), D(8), E(2)
• D → E(7)
• E → D(9)

(i) Graph Drawing (description)

Vertices A-E.
Edges: A→B (10), A→C (3), B→C (1), B→D (5), C→B (4), C→D (8), C→E (2), D→E (7), E→D (9). It's directed; no edge into A. Strongly connected component {B,C,D,E} partially.

If sketched: A at top, arrows to B (right) and C (middle); B to C (down-left, 1) and D; C to B (up), to D (right), to E (down); D⟷E bidirectional with weights 7/9.

(ii) BFS Algorithm (as in Q92)

BFS(G, s):
  for v in V: visited[v]=false, dist[v]=∞
  Q=queue(); visited[s]=true; dist[s]=0; enqueue(s)
  order=[]
  while Q not empty:
    u=dequeue()
    order.append(u)
    for v in Adj[u] (in list order):
      if not visited[v]:
        visited[v]=true; dist[v]=dist[u]+1; parent[v]=u; enqueue(v)

Time $O(V+E)$, space $O(V)$. BFS ignores weights (treats as unweighted for traversal order); for weighted shortest paths use Dijkstra.

(iii) BFS Traversal Starting A (assuming adjacency order as listed)

• Init Q=[A], visited {A}, order []
• Dequeue A → order [A]; neighbors B,C not visited → enqueue B,C → Q=[B,C]
• Dequeue B → order [A,B]; neighbors C (already visited), D not visited → enqueue D → Q=[C,D]
• Dequeue C → order [A,B,C]; neighbors B already, D already, E not visited → enqueue E → Q=[D,E]
• Dequeue D → order [A,B,C,D]; neighbor E already visited (via C) → Q=[E]
• Dequeue E → order [A,B,C,D,E]; neighbor D already visited → Q=[] done.

BFS order: A → B → C → D → E
Distances (edges): dist[A]=0, dist[B]=1, dist[C]=1, dist[D]=2 (via B), dist[E]=2 (via C).

Parent tree: parent[B]=A, parent[C]=A, parent[D]=B, parent[E]=C.

If adjacency order C before B, order would be A,C,B,E,D etc but standard given order yields A,B,C,D,E. BFS levels: L0 {A}, L1 {B,C}, L2 {D,E}.

Prim's Algorithm & Time Complexity

Algorithm (Greedy MST)

Prim(G, s):
  for v in V: key[v]=∞, parent[v]=NIL, inMST[v]=false
  key[s]=0
  Q = min-priority queue of V keyed by key
  while Q not empty:
    u = Extract-Min(Q); inMST[u]=true
    for each v in Adj[u]:
      if !inMST[v] and w(u,v) < key[v]:
        parent[v]=u; key[v]=w(u,v); Decrease-Key(Q,v,key[v])

Growth from source $s$, repeatedly adds minimum-weight edge crossing cut $(MST, V-MST)$ (cut property guarantees safety). Result = MST with $V-1$ edges, parent pointers form tree.

Example (as in Q89): start A, edges AB1 etc → picks AB1, then CD2 etc until MST weight minimal.

Correctness Sketch

Cut property: lightest edge crossing any cut belongs to some MST. Prim's cut is (inMST, rest); picking min crossing edge maintains invariant that inMST vertices are connected by MST edges.

Time Complexity

Depends on priority queue:

• Adjacency list + binary heap: $O((V+E)\log V)$ = $O(E\log V)$ (extract-min $V$ times, decrease-key up to $E$ times).
• Adjacency list + Fibonacci heap: $O(E + V\log V)$ (amortized decrease-key $O(1)$).
• Adjacency matrix + array (no heap, scan min): $O(V^2)$ — best for dense graphs ($E≈V^2$).
• Adjacency matrix + binary heap: still $O(E\log V)$.

Space: $O(V+E)$ or $O(V^2)$ for matrix.

Comparison

Prim good for dense graphs (array $O(V^2)$), Kruskal $O(E\log E)$ better for sparse. Both optimal greedy MST algorithms.

MST & Prim's Algorithm (Detailed)

MST Definition

Connected, undirected, weighted $G(V,E,w)$. Spanning tree $T$ with $V-1$ edges spanning all vertices. MST minimizes $\sum_{e\in T} w(e)$.

Prim's Algorithm (as in Q94)

Prim(G, r):
  key[v]=∞, parent[v]=NIL, inQueue[v]=true for all v
  key[r]=0; Q = min-heap on key
  while Q≠∅:
    u=Extract-Min(Q); inQueue[u]=false
    for v in Adj[u]:
      if inQueue[v] and w(u,v)<key[v]:
        parent[v]=u; key[v]=w(u,v); Decrease-Key(Q,v,key[v])

Cut property ensures each added edge is safe.

Example Run (Graph: V=4 edges AB1 AC4 BC2 BD5 CD3)

Start A: key[A]=0

• Extract A → relax B1, C4 → key[B]=1 parent A, key[C]=4
• Extract B (min1) → relax C via2 <4 → key[C]=2 parent B; D via5 → key[D]=5
• Extract C (2) → relax D via3 <5 → key[D]=3 parent C
• Extract D (3) → done. MST edges: AB1, BC2, CD3 weight 6.

Complexity: $O(E\log V)$ binary heap, $O(V^2)$ array, $O(E+V\log V)$ Fibonacci.

When to Use Prim vs Kruskal

• Prim vertex-growth → dense graphs ($O(V^2)$ without heap good).
• Kruskal edge-sort → sparse graphs ($O(E\log E)$). Both $O(E\log V)$ order-wise.

BFS vs DFS Differences (Traversal, Memory, Applications)

Detailed as in Q66/Q92 summary:

Traversal Order

• BFS: Level-order (queue) → visits neighbors layer by layer, yields vertices sorted by distance (edges) from source. Order: source, distance1, distance2...
• DFS: Depth-first (stack/recursion) → dives to deepest unvisited neighbor before backtracking, yields pre-order depth path.

Memory Usage

• BFS: Needs queue storing entire frontier; worst $O(V)$ but frontier can be wide → up to $O(b^d)$ for branching factor $b$, depth $d$; often more memory than DFS for wide graphs.
• DFS: Stack stores current path; $O(h)$ where $h$ = height/depth ($O(V)$ worst). Recursion stack $O(V)$ but typically smaller for deep narrow graphs. Risk of recursion overflow; iterative DFS also $O(V)$.
• Both $O(V)$ visited array + $O(V+E)$ or $O(V^2)$ graph storage.

Applications & Real-World

BFS:

• Unweighted shortest path (GPS with equal roads, social network degrees, web crawler breadth, peer-to-peer search).
• Bipartite testing, connected components, Edmonds-Karp max flow (BFS finds shortest augmenting path), broadcasting level synchrony.

DFS:

• Topological sort (DAG), cycle detection (back edge), strongly connected components (Kosaraju), articulation points/bridges, solving mazes/puzzles via backtracking, file system traversal.
• Memory-constrained search (when BFS frontier too large).

Tradeoff: Need shortest path on unweighted? BFS. Need any path / explore deep / detect cycles / topological? DFS. Need both? Use BFS for shortest, DFS for connectivity; iterative deepening combines benefits.

Negative Weight Cycle & Bellman-Ford Algorithm

Negative Weight Cycle

Directed cycle $C$ with sum $\sum_{e\in C} w(e) <0$. In such graph, shortest path from source to vertices reachable from $C$ is undefined ($-\infty$) because traversing cycle repeatedly reduces path weight arbitrarily. Example: $a→b$ -2, $b→a$ -1 → cycle -3.

Without negative cycles, shortest simple paths well-defined (≤ $V-1$ edges).

Bellman-Ford — Single Source Shortest Paths (SSSP) with Negatives

BellmanFord(G, s):
  dist[s]=0; dist[v]=∞ for v≠s; parent[v]=NIL
  repeat V-1 times:
    for each edge (u,v)∈E:
      if dist[u]+w(u,v) < dist[v]:
        dist[v]=dist[u]+w(u,v); parent[v]=u
  // detect negative cycle
  for each edge (u,v):
    if dist[u]+w(u,v) < dist[v]:
      return "Negative cycle reachable from s" (and retrieve cycle via parent)
  return dist, parent

Correctness: After $i$ iterations, $dist[v]$ = shortest path using ≤ $i$ edges. After $V-1$, all simple paths considered. If still relaxable → ≥ $V$ edges → must contain cycle → negative.

Complexities: Time $O(VE)$ (list) / $O(V^3)$ (matrix), Space $O(V)$. Superior to Dijkstra which fails with negatives; slower but handles them.

Finding All Negative Cycles: Add super source $s'$ with 0 edges to all vertices, run once to detect any cycle in graph.

MST Concepts, Prim vs Kruskal

(i) MST Concept

Connected, undirected, weighted $G(V,E,w)$. Spanning tree $T$ has $V-1$ edges, connects all vertices, acyclic. MST minimizes $\sum_{e\in T} w(e)$; unique if weights distinct. Characterized by Cut Property (lightest edge crossing any cut in some MST) and Cycle Property (heaviest edge on any cycle not in MST). Applications: network design (least cable), clustering.

(ii) Compare Prim vs Kruskal

Feature	Prim	Kruskal
Growth	Vertex-based: grows tree from start vertex, adds min edge crossing cut $(inMST, rest)$.	Edge-based: sorts all edges, adds min edge that doesn't form cycle (Union-Find).
Data structure	Priority queue (heap) + key[].	Union-Find (Disjoint Set) + sorting.
Steps	$V-1$ iterations extract min vertex	$E$ iterations over sorted edges
Complexity	$O(E\log V)$ heap, $O(V^2)$ array (dense), $O(E+V\log V)$ Fibonacci	$O(E\log E)$ sort dominates ($\approx O(E\log V)$ as $\log E ≈ \log V$)
Graph type	Good for dense ($V^2$ edges)	Good for sparse ($E≈V$)
Requires	Connected to get single tree; else spanning forest	Works on forest naturally

Both greedy and optimal via cut property.

(iii) Time & Advantages / Preference

• Prim: $O(V^2)$ without heap best for dense; $O(E\log V)$ with heap. Advantage: single tree growing → early stop or distributed. Preferred when $E$ large, graph dense, or adjacency matrix.
• Kruskal: $O(E\log E)$ sort. Advantage: simple, sorts edges, handles disconnected, easy parallel sort. Preferred when $E$ small (sparse) or edges already sorted.

Overall both $O(E\log V)$; choice depends on density: Prim for dense ($E≫V$), Kruskal for sparse ($E≈V$).

Ford-Fulkerson Max Flow — $S→A10,S→C10,A→B4,A→C2,C→D9,B→T10,D→B6,D→T10$

Network Structure

Source $S$, sink $T$, intermediate A,B,C,D.

Execution (Edmonds-Karp BFS for shortest augmenting path, but any path works; show one valid sequence)

Init flow 0, residual = capacities.

Augment 1: $S-A-B-T$ bottlenecks min(10,4,10)=4

• Push 4: residual $S-A$6, $A-B$0, $B-T$6. Flow=4

Augment 2: $S-A-C-D-T$ (via $A→C$)

• Path capacities: S-A6, A-C2, C-D9, D-T10 → bottleneck 2
• Push 2: $S-A$4, $A-C$0, $C-D$7, $D-T$8. Flow=6
• Note alternative $S-C-D-T$ also available but we use through A to show.

Augment 3: $S-C-D-T$ bottleneck min(S-C10, C-D7, D-T8)=7

• Push 7: $S-C$3, $C-D$0, $D-T$1. Flow=13

Augment 4: $S-C-D-B-T$ ??? Need residual check: After 1, $A→B$ saturated, but reverse $B→A$ 4 exists. However $D→B$6 is forward.
Path $S-C$3 → $C-D$ is 0 residual (saturated) so no. Let's instead use remaining $S-A$4 → but $A-C$0 and $A-B$0 blocked, so $S-A$ cannot reach T via A. So remaining flow must go $S-C-D-B-T$ if $C-D$0 no. Actually after step3 $C-D$0, so D only reachable not via C. So need alternative.

Let's choose better order: Instead of exhausting C-D early, more systematic:

Re-run with better path selection (standard max flow =13? Let's compute min cut).

Min Cut analysis: Cut $(S,A)$? Edges crossing: $S-A$10 + $S-C$10 =20. Cut $(S,A,C)$ → edges $A-B$4, $C-D$9 → 13. Cut $(S,A,C,D)$ → $A-B$4, $D-B$6? Actually $D-B$ internal, $B-T$10, $D-T$10 → cut includes $B-T$10 + $D-T$10 =20? Wait compute: Partition $\{S,A,C\}$ vs $\{B,D,T\}$ edges $A-B$4, $C-D$9 →13. Add $D→T$ and $B→T$ are from right to T but crossing? Actually T in right, B,D in right, so not crossing? Need correct: Let's compute max flow via brute: The bottleneck is $C-D$9 + $A-B$4 =13, and $S-C$10 + $A-B$4 =14, so min is 13. So max flow =13 (limited by $A-B$4 + $C-D$9). Another cut $\{S,A,C,D\}$ vs $\{B,T\}$ edges $A-B$4 + $D-B$6 + $D-T$10 =20? Not min. So max is 13.

Our earlier flow 13 already achievable (4+2+7=13). After step3 flow=13, indeed max reached.
Check residual: $S-A$4, $S-C$3 remain but no path to T because $A-B$0, $A-C$0, $C-D$0 blocks; alternative $S-C$ → ??? $D-B$ still has 6 but $D$ unreachable (since $C-D$0). So no augmenting path → algorithm terminates.

Updated Residual After Each Augmentation (summary)

Path	Bottleneck	Flow	Residual key edges
S-A-B-T	4	4	S-A6, A-B0(+4 reverse), B-T6
S-A-C-D-T	2	6	S-A4, A-C0(+2), C-D7, D-T8
S-C-D-T	7	13	S-C3, C-D0(+7), D-T1

Max Flow value =13 (4 via A-B-T, 9 via C-D-T split as 2+7). Achieved.

Any valid augmenting order yielding 13 is acceptable; another order S-C-D-B-T (6) etc also yields 13.