Graph Theory and Algorithms

Overview

In our study of data structures, we have thus far examined linear and hierarchical collections. We now advance to a more general and powerful structure: the graph. A graph provides a formal framework for modeling entities and the relationships between them, making it one of the most versatile and fundamental concepts in computer science. From social networks and transportation systems to the very structure of the internet, graphs offer the abstract machinery necessary to represent and analyze complex, interconnected systems. A firm grasp of graph theory is therefore indispensable for the modern computer scientist and engineer.

This chapter is dedicated to the systematic study of graphs and the core algorithms that operate upon them. For the Graduate Aptitude Test in Engineering (GATE), proficiency in this area is not merely advantageous; it is essential. Questions frequently assess a candidate's understanding of graph representations, such as the adjacency matrix and adjacency list, and their ability to analyze the behavior of fundamental algorithms. We will explore the foundational algorithms for graph traversal—Breadth-First Search (BFS) and Depth-First Search (DFS)—which form the basis for solving a wide array of problems. Subsequently, we shall investigate algorithms for finding the shortest path between vertices, a classic problem with profound practical applications. Mastery of the topics presented herein will equip you with the analytical tools required to solve a significant portion of the algorithm-based problems encountered in the examination.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------------------------------|---------------------------------------|
| 1 | Introduction to Graph Theory | Fundamental concepts and graph representations. |
| 2 | Graph Traversal Algorithms | Systematic exploration using BFS and DFS. |
| 3 | Basic Shortest Path Algorithms | Finding optimal paths in weighted graphs. |

---

Learning Objectives

---

We now turn our attention to Introduction to Graph Theory...
## Part 1: Introduction to Graph Theory

Introduction

Graph theory is a fundamental pillar of computer science and data analysis, providing a powerful mathematical framework for modeling and analyzing relational data. A graph, in its essence, is an abstract representation of a set of objects where some pairs of objects are connected by links. These "objects" can be anything from cities in a transportation network, to users in a social network, or web pages connected by hyperlinks. The "links" represent the relationships between them.

In the context of the GATE examination, a firm grasp of graph theory is indispensable. It forms the bedrock for understanding complex algorithms, network flows, data structures, and optimization problems. Our study will begin with the formal definitions and basic terminology, establishing a precise language to discuss graph properties. We will then explore different types of graphs and their characteristics, paying close attention to the distinctions that are critical for algorithmic analysis, such as weighted versus unweighted and directed versus undirected graphs. This foundational knowledge is paramount for tackling problems in more advanced topics like graph traversals and shortest path algorithms.

---

Key Concepts

#
## 1. Types of Graphs

The properties of a graph are determined by the nature of its vertices and edges. Understanding these classifications is the first step toward selecting appropriate algorithms for graph-related problems.

Undirected and Directed Graphs

An undirected graph is one in which edges have no orientation. The edge $(u, v)$ is identical to the edge $(v, u)$, signifying a symmetric relationship between the vertices. In contrast, a directed graph (or digraph) consists of edges that have a direction. An edge $(u, v)$ represents a connection from $u$ to $v$, which is distinct from a potential edge $(v, u)$.

Undirected Graph

A

B

C

Directed Graph

X

Y

Z

Weighted and Unweighted Graphs

In an unweighted graph, all edges are considered equal. The focus is purely on the existence of a connection. In a weighted graph, each edge is assigned a numerical value, or weight, which can represent cost, distance, time, or capacity. For an edge $e = (u,v)$, its weight is denoted by $w(u,v)$.

Simple Graphs

A simple graph is an unweighted, undirected graph containing no self-loops (an edge from a vertex to itself) and no parallel edges (multiple edges between the same two vertices). GATE problems often specify that a graph is simple, which is an important constraint.

#
## 2. Fundamental Terminology

A precise vocabulary is essential for reasoning about graphs.

• Adjacency: Two vertices $u$ and $v$ are adjacent (or neighbors) if there is an edge $(u, v)$ connecting them.
• Degree of a Vertex: In an undirected graph, the degree of a vertex $v$, denoted $deg(v)$, is the number of edges incident to it. For a directed graph, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges.
• Path: A path is a sequence of vertices $(v_0, v_1, \dots, v_k)$ such that for all $i$ from $0$ to $k-1$, $(v_i, v_{i+1})$ is an edge in $E$. The length of a path is the number of edges in it, which is $k$.
• Cycle: A cycle is a path of length at least 1 that starts and ends at the same vertex, with no repeated edges or intermediate vertices.
• Connected Graph: An undirected graph is connected if there exists a path between every pair of distinct vertices.

#
## 3. Shortest Paths in Unweighted Graphs

A problem of central importance in graph theory is finding the shortest path between two vertices. The definition of "shortest" depends on whether the graph is weighted or unweighted.

For an unweighted graph, the shortest path is simply the path containing the minimum number of edges. The length of this shortest path between vertices $u$ and $v$ is called the distance between them, denoted $d(u,v)$.

This concept has a powerful logical implication that is frequently tested in competitive exams.

Worked Example:

Problem:
Consider a simple, unweighted, and undirected graph $G$. It is known that $P = (p, q, r, s, t)$ is a shortest path between vertex $p$ and vertex $t$. Which of the following edges cannot exist in $G$?
(i) $(q, s)$
(ii) $(p, r)$
(iii) $(r, t)$

Solution:

The given shortest path is $p \to q \to r \to s \to t$. The length of this path is 4.

Step 1: Analyze the implication for edge $(q, s)$.
The vertices $q$ and $s$ are in the path $P$. If the edge $(q, s)$ existed, we could form a new path from $p$ to $t$: $p \to q \to s \to t$.

Step 2: Calculate the length of the new path.
The path $p \to q \to s \to t$ has a length of 3.

Step 3: Compare with the original shortest path length.
The new path of length 3 is shorter than the given shortest path of length 4. This is a contradiction. Therefore, the edge $(q, s)$ cannot exist.

Step 4: Analyze the implication for edge $(p, r)$.
If the edge $(p, r)$ existed, we could form a new path from $p$ to $t$: $p \to r \to s \to t$.

Step 5: Calculate the length of this new path.
The path $p \to r \to s \to t$ has a length of 3, which is shorter than 4. This is a contradiction. Therefore, the edge $(p, r)$ cannot exist.

Step 6: Analyze the implication for edge $(r, t)$.
If the edge $(r, t)$ existed, we could form a new path from $p$ to $t$: $p \to q \to r \to t$.

Step 7: Calculate the length of this final new path.
The path $p \to q \to r \to t$ has a length of 3, which is shorter than 4. This is a contradiction. Therefore, the edge $(r, t)$ cannot exist.

Answer: All three edges, $(q, s)$, $(p, r)$, and $(r, t)$, cannot exist in the graph $G$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A simple undirected graph $G$ has 10 vertices. The degree of every vertex is 3. What is the number of edges in $G$?" options=["10", "15", "20", "30"] answer="15" hint="Use the Handshaking Lemma, which relates the sum of degrees to the number of edges." solution="
Step 1: Recall the Handshaking Lemma.
For an undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges.

Step 2: Calculate the sum of degrees.
The graph has 10 vertices, and each vertex has a degree of 3.

Step 3: Solve for the number of edges, $|E|$.

Result:
The number of edges in the graph is 15.
"
:::

:::question type="NAT" question="In a simple connected undirected graph, the number of vertices is 8. What is the minimum number of edges this graph can have?" answer="7" hint="Consider the definition of a connected graph and what structure has the minimum number of edges while satisfying this property. A tree is a minimally connected graph." solution="
Step 1: Understand the condition for a connected graph.
A graph is connected if there is a path between any two vertices.

Step 2: Consider the structure of a minimally connected graph.
A graph with $n$ vertices is connected if it has at least $n-1$ edges. A graph with $n$ vertices and $n-1$ edges that is connected is a tree. Adding any fewer edges would result in a disconnected graph (a forest).

Step 3: Apply this to the given problem.
The number of vertices is $n=8$.
The minimum number of edges required to keep the graph connected is $n-1$.

Step 4: Calculate the result.
Minimum edges = $8 - 1 = 7$.

Result:
The minimum number of edges is 7.
"
:::

:::question type="MSQ" question="Let $G$ be a simple, unweighted, and undirected graph. It is given that the path $A-B-C-D-E$ is a shortest path between vertex $A$ and vertex $E$. Which of the following statements is/are necessarily true?" options=["The edge $(A,C)$ does not exist.", "The edge $(B,E)$ does not exist.", "The degree of vertex $C$ is exactly 2.", "The graph $G$ does not contain a cycle."] answer="The edge $(A,C)$ does not exist.,The edge $(B,E)$ does not exist." hint="Apply the implication of a path being the 'shortest'. The existence of certain edges would create a shortcut, contradicting the given information. The information provided is only about a single path, not the entire graph." solution="
Analysis of Option A: The edge $(A,C)$ does not exist.
The given shortest path is $A-B-C-D-E$, with length 4. If the edge $(A,C)$ existed, a new path $A-C-D-E$ could be formed. The length of this new path would be 3. Since $3 < 4$, this contradicts that $A-B-C-D-E$ is a shortest path. Thus, the edge $(A,C)$ cannot exist. This statement is TRUE.

Analysis of Option B: The edge $(B,E)$ does not exist.
If the edge $(B,E)$ existed, a new path $A-B-E$ could be formed. The length of this new path would be 2. Since $2 < 4$, this contradicts that $A-B-C-D-E$ is a shortest path. Thus, the edge $(B,E)$ cannot exist. This statement is TRUE.

Analysis of Option C: The degree of vertex $C$ is exactly 2.
The given path tells us that vertex $C$ is adjacent to $B$ and $D$, so its degree is at least 2. However, $C$ could be connected to other vertices not on this path (e.g., a vertex $F$). The problem gives no information to restrict other connections. For example, the edge $(C,F)$ could exist without creating a shorter path between $A$ and $E$. Therefore, we cannot conclude that $deg(C)$ is exactly 2. This statement is FALSE.

Analysis of Option D: The graph $G$ does not contain a cycle.
The information provided is only about a single shortest path. The graph could be much larger and contain cycles elsewhere. For instance, there could be an edge $(A,F)$ and $(B,F)$, forming a cycle $A-B-F-A$, which does not affect the shortest path from $A$ to $E$. Therefore, we cannot conclude that the graph is acyclic. This statement is FALSE.
"
:::

:::question type="MCQ" question="Which of the following describes a graph where it is possible to start at a vertex, traverse every edge exactly once, and return to the starting vertex?" options=["A Hamiltonian Cycle", "A Bipartite Graph", "An Eulerian Circuit", "A Complete Graph"] answer="An Eulerian Circuit" hint="This is the definition of a specific type of tour in a graph. Recall the conditions related to vertex degrees for such a tour to exist." solution="
Step 1: Analyze the question's conditions.
The question describes a closed trail that visits every edge of a graph exactly once. This is the precise definition of an Eulerian circuit (or Eulerian tour).

Step 2: Evaluate the options.

• A Hamiltonian Cycle is a cycle that visits every vertex exactly once. It does not guarantee traversing every edge.


• A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to one in the other. This is a structural property and does not describe a walk.


• An Eulerian Circuit is by definition a trail that starts and ends at the same vertex and traverses every edge exactly once. This matches the question perfectly. A connected graph has an Eulerian circuit if and only if every vertex has an even degree.


• A Complete Graph is a graph where every pair of distinct vertices is connected by a unique edge. While some complete graphs may have an Eulerian circuit (e.g., $K_3, K_5$), the term itself does not describe the walk.

Result:
The correct term is an Eulerian Circuit.
"
:::

---

Summary

---

What's Next?

---

---

Part 2: Graph Traversal Algorithms

Introduction

Graph traversal, also known as graph search, is a fundamental algorithmic concept concerned with the systematic exploration of vertices and edges within a graph. The objective is to visit each vertex precisely once in a structured manner, starting from a designated source vertex. The manner in which the graph is explored gives rise to distinct traversal strategies, each with its own unique properties and applications. For the GATE examination, a deep understanding of the two principal traversal algorithms—Breadth-First Search (BFS) and Depth-First Search (DFS)—is indispensable.

These algorithms form the bedrock upon which more complex graph algorithms are built. They are not merely procedures for visitation but are powerful tools for uncovering the structural properties of graphs. We use them to determine connectivity, find paths, identify cycles, and establish orderings among vertices. A mastery of their mechanics, complexities, and applications is therefore essential for solving a wide range of problems in data science and algorithms.

---

Key Concepts

#
## 1. Breadth-First Search (BFS)

Breadth-First Search explores a graph layer by layer. It begins at a source vertex $s$ and explores all its immediate neighbors. Then, for each of those neighbors, it explores their unvisited neighbors, and so on. This level-wise exploration is achieved using a queue data structure. The primary application of BFS in an unweighted graph is to find the shortest path—in terms of the number of edges—from the source vertex to all other reachable vertices.

The algorithm maintains three key pieces of information for each vertex $u$:

• `color[u]`: The state of the vertex (WHITE for unvisited, GRAY for visited but not fully explored, BLACK for fully explored).


• `d[u]`: The distance (shortest path length) from the source $s$ to $u$.


• `π[u]`: The predecessor or parent of $u$ in the BFS tree.

Algorithm Pseudocode:
```
BFS(G, s)
for each vertex u in G.V - {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color[s] = GRAY
d[s] = 0
π[s] = NIL
Q = new Queue()
ENQUEUE(Q, s)
while Q is not empty
u = DEQUEUE(Q)
for each v in G.Adj[u]
if color[v] == WHITE
color[v] = GRAY
d[v] = d[u] + 1
π[v] = u
ENQUEUE(Q, v)
color[u] = BLACK
```

Worked Example:

Problem: Perform a Breadth-First Search on the following unweighted, undirected graph, starting from vertex A. Determine the distance of each vertex from A.

A

B

C

D

E

F

Solution:

We initialize a queue `Q`, a distance array `d`, and assume alphabetical order for exploring neighbors.

Step 1: Initialize. Source is A.

• `d[A] = 0`, all other `d` values are $\infty$.


• Enqueue A. `Q = [A]`

Step 2: Dequeue A. Visit its neighbors B and C.

• `d[B] = d[A] + 1 = 1`. Enqueue B.


• `d[C] = d[A] + 1 = 1`. Enqueue C.


• `Q = [B, C]`

Step 3: Dequeue B. Visit its unvisited neighbors D and E.

• `d[D] = d[B] + 1 = 2`. Enqueue D.


• `d[E] = d[B] + 1 = 2`. Enqueue E.


• `Q = [C, D, E]`

Step 4: Dequeue C. Its only unvisited neighbor is E. Since E is already visited (GRAY), we do nothing.

• `Q = [D, E]`

Step 5: Dequeue D. Visit its unvisited neighbor F.

• `d[F] = d[D] + 1 = 3`. Enqueue F.


• `Q = [E, F]`

Step 6: Dequeue E. Visit its unvisited neighbor F. F is already visited (GRAY).

• `Q = [F]`

Step 7: Dequeue F. It has no unvisited neighbors.

• `Q = []`. The queue is empty, so the algorithm terminates.

Result:
The distances from source A are:

• $d[A] = 0$


• $d[B] = 1$


• $d[C] = 1$


• $d[D] = 2$


• $d[E] = 2$


• $d[F] = 3$

---

#
## 2. Depth-First Search (DFS)

Depth-First Search explores a graph by venturing as deeply as possible along each branch before backtracking. This "depth-first" strategy is naturally implemented using recursion, where the call stack implicitly manages the vertices to visit. An iterative version using an explicit stack is also possible. DFS is instrumental in applications such as topological sorting, cycle detection, and finding connected components.

Algorithm Pseudocode (Recursive):
```
DFS(G)
for each vertex u in G.V
color[u] = WHITE
π[u] = NIL
time = 0
for each vertex u in G.V
if color[u] == WHITE
DFS-VISIT(G, u)

DFS-VISIT(G, u)
time = time + 1
d[u] = time // Discovery time
color[u] = GRAY
for each v in G.Adj[u]
if color[v] == WHITE
π[v] = u
DFS-VISIT(G, v)
color[u] = BLACK
time = time + 1
f[u] = time // Finish time
```
The discovery time $d[u]$ and finish time $f[u]$ are crucial for advanced applications like topological sorting and edge classification.

---

#
## 3. DFS Edge Classification

During a DFS traversal of a graph $G$, every edge $(u,v)$ can be classified into one of four types based on the state of vertex $v$ when the edge is first explored from $u$.

u
v
w
x
y
z

Tree
Tree
Tree
Tree
Back (x to u)
Forward (u to x)
Cross (z to w)

• Tree Edge: An edge $(u,v)$ is a tree edge if vertex $v$ was previously unvisited (`WHITE`) when the edge is explored. These edges form the DFS forest. For such an edge, if DFS is performed from $u$ to $v$, then $v$ becomes a child of $u$ in the DFS tree. A key property related to BFS distances in an unweighted graph is that if $(u,v)$ is a tree edge discovered from $u$, then the shortest path distance satisfies $d[v] = d[u] + 1$.

• Back Edge: An edge $(u,v)$ is a back edge if $v$ is an ancestor of $u$ in the DFS tree. A back edge indicates the presence of a cycle in the graph. Vertex $v$ will be `GRAY` when the edge $(u,v)$ is explored.

• Forward Edge: An edge $(u,v)$ is a forward edge if $v$ is a descendant of $u$ in the DFS tree, but it is not a tree edge. This occurs when $v$ has already been discovered via another path originating from $u$. Vertex $v$ will be `BLACK` or `GRAY` when the edge is explored.

• Cross Edge: An edge $(u,v)$ that is not any of the above. It connects two vertices that are in different subtrees of the DFS forest, or two vertices in the same subtree where neither is an ancestor of the other. Vertex $v$ will be `BLACK` when the edge is explored.

---

#
## 4. Topological Sorting

For a Directed Acyclic Graph (DAG), a topological sort is a linear ordering of its vertices such that for every directed edge from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering. A graph must be a DAG to have a topological sort.

Method 1: Kahn's Algorithm (BFS-based)

This algorithm iteratively removes vertices with an in-degree of 0.

Compute the in-degree of all vertices in the graph.

Initialize a queue and add all vertices with an in-degree of 0.

While the queue is not empty:

a. Dequeue a vertex $u$. Add $u$ to the topological sort result.
b. For each neighbor $v$ of $u$:
i. Decrement the in-degree of $v$.
ii. If the in-degree of $v$ becomes 0, enqueue $v$.

If the count of visited vertices is not equal to the total number of vertices, the graph has a cycle.

Method 2: DFS-based Algorithm

This algorithm leverages the finish times of a DFS traversal.

Perform a DFS on the graph.

As each vertex finishes (i.e., the recursive call for that vertex returns), prepend it to a linked list.

The final linked list represents a valid topological ordering.

This is equivalent to sorting the vertices in decreasing order of their finish times.

Worked Example:

Problem: Find a topological sort for the following DAG.

A
B
C
D
E

Solution (using Kahn's Algorithm):

Step 1: Compute in-degrees.

• In-degree(A) = 0


• In-degree(B) = 0


• In-degree(C) = 2


• In-degree(D) = 1


• In-degree(E) = 1

Step 2: Initialize queue with in-degree 0 vertices.

• `Q = [A, B]` (assuming alphabetical order)


• `Result = []`

Step 3: Dequeue A.

• `Result = [A]`


• For neighbor C: In-degree(C) becomes 1.


• `Q = [B]`

Step 4: Dequeue B.

• `Result = [A, B]`


• For neighbor C: In-degree(C) becomes 0. Enqueue C.


• `Q = [C]`

Step 5: Dequeue C.

• `Result = [A, B, C]`


• For neighbor D: In-degree(D) becomes 0. Enqueue D.


• For neighbor E: In-degree(E) becomes 0. Enqueue E.


• `Q = [D, E]`

Step 6: Dequeue D.

• `Result = [A, B, C, D]`


• `Q = [E]`

Step 7: Dequeue E.

• `Result = [A, B, C, D, E]`


• `Q = []`. Queue is empty.

Answer: A valid topological sort is `A, B, C, D, E`. Note that if we had dequeued B before A in Step 3, we would have obtained another valid sort: `B, A, C, D, E`.

---

Problem-Solving Strategies

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A recursive function `traverse(G, u, visited)` is designed to perform a graph traversal. The graph `G` is represented by an adjacency list. The function's body is as follows:\n\n```python\nvisited[u] = True\nprint(u)\nfor v in G.adj[u]:\n if not visited[v]:\n traverse(G, v, visited)\n```\n\nThis implementation is functionally equivalent to which algorithm?" options=["Breadth-First Search","Depth-First Search","Dijkstra's Algorithm","Kahn's Algorithm"] answer="Depth-First Search" hint="Consider how recursion uses a stack data structure implicitly. Which traversal algorithm is stack-based?" solution="The recursive function `traverse` explores as deeply as possible along one path before backtracking. When it calls `traverse(G, v, visited)`, it commits to exploring the entire subtree rooted at `v` before it returns to the `for` loop to consider other neighbors of `u`. This 'depth-first' behavior is the defining characteristic of Depth-First Search. The system's call stack manages the backtracking, which is equivalent to using an explicit stack in an iterative DFS."
:::

:::question type="NAT" question="Consider a directed graph with vertices $\{0, 1, 2, 3, 4, 5\}$. The adjacency lists are given as follows:

• 0: [1, 2]


• 1: [3]


• 2: [4]


• 3: [5]


• 4: [5]


• 5: []

A Depth-First Search is performed starting from vertex 0. The neighbors of any vertex are visited in the order they appear in the adjacency list. What is the finish time of vertex 2? (Assume the initial time is 0, and time increments by 1 for each discovery and each finish event)." answer="8" hint="Trace the DFS traversal step-by-step. Keep track of a global `time` variable. A vertex is discovered when it is first visited (turns GRAY). A vertex is finished when all its descendants have been visited (turns BLACK)." solution="Let's trace the DFS and the global time `t`.

• t=0: Start DFS. Call `DFS-VISIT(0)`.


• t=1: Discover 0. `d[0]=1`. Neighbors of 0 are 1, 2. Visit 1 first.


• t=2: Discover 1. `d[1]=2`. Neighbors of 1 is 3. Visit 3.


• t=3: Discover 3. `d[3]=3`. Neighbors of 3 is 5. Visit 5.


• t=4: Discover 5. `d[5]=4`. No neighbors.


• t=5: Finish 5. `f[5]=5`. Return to 3.


• t=6: Finish 3. `f[3]=6`. Return to 1.


• t=7: Finish 1. `f[1]=7`. Return to 0. Now visit the next neighbor of 0, which is 2.


• t=8: Discover 2. `d[2]=8`. Neighbors of 2 is 4. Visit 4.


• t=9: Discover 4. `d[4]=9`. Neighbors of 4 is 5. But 5 is already visited.


• t=10: Finish 4. `f[4]=10`. Return to 2.


• t=11: Finish 2. `f[2]=11`. Return to 0.


• t=12: Finish 0. `f[0]=12`.

The question asks for the finish time of vertex 2. From our trace, `f[2]=11`. Let's re-read the question carefully. "What is the finish time of vertex 2?" The trace is correct. `d` is discovery, `f` is finish. `f[2]=11`. Let's re-check the trace.

Wait, I made a mistake in the prompt's solution. Let me re-trace.

• `time = 0`


• `DFS(0)`

- `time = 1`, `d[0] = 1`
- `DFS(1)`
- `time = 2`, `d[1] = 2`
- `DFS(3)`
- `time = 3`, `d[3] = 3`
- `DFS(5)`
- `time = 4`, `d[5] = 4`
- `time = 5`, `f[5] = 5`, return
- `time = 6`, `f[3] = 6`, return
- `time = 7`, `f[1] = 7`, return
- `DFS(2)`
- `time = 8`, `d[2] = 8`
- `DFS(4)`
- `time = 9`, `d[4] = 9`
- neighbor 5 is visited, do nothing.
- `time = 10`, `f[4] = 10`, return
- `time = 11`, `f[2] = 11`, return
- `time = 12`, `f[0] = 12`
The finish time is 11. Let me adjust the question or answer to make it a rounder number.
Let's change the graph.
0: [1, 4]
1: [2]
2: [3]
3: []
4: [3]
Start at 0.

• t=1, d[0]=1


• DFS(1)

- t=2, d[1]=2
- DFS(2)
- t=3, d[2]=3
- DFS(3)
- t=4, d[3]=4
- t=5, f[3]=5
- t=6, f[2]=6
- t=7, f[1]=7

• DFS(4)

- t=8, d[4]=8
- neighbor 3 is visited
- t=9, f[4]=9

• t=10, f[0]=10

The finish time of vertex 2 is 6. This is a better NAT question. Let's use this.

The question should be:
Consider a directed graph with vertices $\{0, 1, 2, 3, 4\}$. The adjacency lists are:

• 0: [1, 4]


• 1: [2]


• 2: [3]


• 3: []


• 4: [3]

A DFS is performed starting from vertex 0, visiting neighbors in the order they appear. What is the finish time of vertex 2? (Initial time=0, increments for each discovery and finish event).
Answer: 6
Solution:
Step 1: Start DFS at vertex 0. Time `t=0`.

• Call `DFS(0)`.


• `t=1`, `d[0]=1`. Explore neighbor 1.

Step 2: Explore from vertex 1.

• Call `DFS(1)`.


• `t=2`, `d[1]=2`. Explore neighbor 2.

Step 3: Explore from vertex 2.

• Call `DFS(2)`.


• `t=3`, `d[2]=3`. Explore neighbor 3.

Step 4: Explore from vertex 3.

• Call `DFS(3)`.


• `t=4`, `d[3]=4`. Vertex 3 has no outgoing edges.


• Finish vertex 3. `t=5`, `f[3]=5`. Return.

Step 5: Return to vertex 2. All its neighbors have been explored.

• Finish vertex 2. `t=6`, `f[2]=6`. Return.

Step 6: Subsequent steps will finish vertices 1, 4, and 0, but we have found our answer.

Result: The finish time of vertex 2 is 6.
:::

:::question type="MSQ" question="For the Directed Acyclic Graph (DAG) shown below, which of the following sequences are valid topological sorts?

A
B
C
D
E

" options=["A, C, B, D, E","A, B, C, D, E","C, A, B, D, E","B, C, A, D, E"] answer="A, C, B, D, E,A, B, C, D, E" hint="A topological sort requires that for every edge u -> v, u must appear before v in the sequence. Check this condition for each option. Remember that multiple valid sorts can exist." solution="The dependencies in the graph are: A->B, A->C, B->D, C->D, D->E.

• A must come before B and C.


• B and C must come before D.


• D must come before E.

Let's check each option:

• A, C, B, D, E: A is before B, C. C and B are before D. D is before E. This is a valid topological sort.


• A, B, C, D, E: A is before B, C. B and C are before D. D is before E. This is a valid topological sort.


• C, A, B, D, E: This is invalid because A must come before C.


• B, C, A, D, E: This is invalid because A must come before B and C.

Therefore, the only valid options are 'A, C, B, D, E' and 'A, B, C, D, E'."
:::

:::question type="MCQ" question="In a DFS traversal of a directed graph, an edge $(u,v)$ is explored. At the time of exploration, vertex $u$ is GRAY and vertex $v$ is also GRAY. What type of edge is $(u,v)$?" options=["Tree edge","Back edge","Forward edge","Cross edge"] answer="Back edge" hint="Consider the meaning of a GRAY vertex in DFS. A GRAY vertex is one that has been discovered but not yet finished. What is the relationship between two GRAY vertices connected by an edge?" solution="In DFS, a vertex is marked GRAY from the time it is discovered until the time it is finished. A vertex `v` is an ancestor of a vertex `u` if and only if `v` is discovered before `u`, and `u` is discovered before `v` is finished. In other words, at the time `u` is discovered, `v` is GRAY. If we then explore an edge `(u,v)` and find that `v` is still GRAY, it means that `v` is an ancestor of `u` in the DFS tree. An edge from a vertex to its ancestor is, by definition, a back edge."
:::

---

Summary

---

What's Next?

---

---

Part 3: Basic Shortest Path Algorithms

Introduction

The problem of finding the shortest path between two vertices in a weighted graph is a cornerstone of graph theory and a frequent subject in competitive examinations. In the context of the GATE Data Science and AI paper, a firm grasp of these fundamental algorithms is essential. These algorithms are not merely academic exercises; they form the basis for numerous real-world applications, from network routing protocols that direct internet traffic to GPS systems that calculate the quickest route for a journey.

We shall explore the single-source shortest path (SSSP) problem, where the objective is to find the shortest paths from a designated source vertex to all other vertices in a graph. Our study will focus on two principal algorithms: Dijkstra's algorithm, which is highly efficient for graphs with non-negative edge weights, and the Bellman-Ford algorithm, a more general method capable of handling negative edge weights and detecting the presence of negative-weight cycles.

---

Key Concepts

A central operation in most shortest path algorithms is the process of "relaxation." For an edge $(u, v)$, relaxing the edge tests whether we can improve the current shortest-path estimate to $v$ by going through $u$.

#
## 1. Dijkstra's Algorithm

Dijkstra's algorithm solves the single-source shortest path problem for a weighted directed graph where all edge weights are non-negative. It operates by maintaining a set of vertices whose final shortest-path weights from the source $s$ have already been determined. The algorithm repeatedly selects the vertex $u$ not yet in this set that has the minimum shortest-path estimate, adds $u$ to the set, and relaxes all edges leaving $u$.

The algorithm maintains a distance array, $d[v]$, which stores the current best estimate of the shortest path distance from $s$ to $v$. Initially, $d[s] = 0$ and $d[v] = \infty$ for all other vertices $v$.

The efficiency of Dijkstra's algorithm critically depends on the data structure used to store the set of unvisited vertices and retrieve the one with the minimum distance estimate. A min-priority queue is commonly used for this purpose.

Time Complexity:

• Using an adjacency matrix and linear scan: $O(V^2)$


• Using an adjacency list and a binary heap (min-priority queue): $O((V+E)\log V)$ or more simply $O(E \log V)$ for connected graphs.

Worked Example:

Problem: Find the shortest path distances from source vertex A to all other vertices in the graph shown below using Dijkstra's algorithm.

A


B

C

D

E

10


3


2


4

2

7

Solution:

We initialize distances: $d[A]=0$, $d[B]=\infty$, $d[C]=\infty$, $d[D]=\infty$, $d[E]=\infty$.
The set of visited vertices $S$ is initially empty.

Iteration 1:

• Select A (distance 0). $S=\{A\}$.


• Relax edges from A:

- Edge (A, B): $d[B] = \min(\infty, 0+10) = 10$.
- Edge (A, C): $d[C] = \min(\infty, 0+3) = 3$.

• Distances: $d = \{A:0, B:10, C:3, D:\infty, E:\infty\}$.

Iteration 2:

• Select C (minimum distance 3). $S=\{A, C\}$.


• Relax edges from C:

- Edge (C, B): $d[B] = \min(10, 3+4) = 7$.
- Edge (C, E): $d[E] = \min(\infty, 3+2) = 5$.

• Distances: $d = \{A:0, B:7, C:3, D:\infty, E:5\}$.

Iteration 3:

• Select E (minimum distance 5). $S=\{A, C, E\}$.


• No outgoing edges from E to unvisited nodes.


• Distances: $d = \{A:0, B:7, C:3, D:\infty, E:5\}$.

Iteration 4:

• Select B (minimum distance 7). $S=\{A, C, E, B\}$.


• Relax edges from B:

- Edge (B, D): $d[D] = \min(\infty, 7+2) = 9$.

• Distances: $d = \{A:0, B:7, C:3, D:9, E:5\}$.

Iteration 5:

• Select D (minimum distance 9). $S=\{A, C, E, B, D\}$.


• Relax edges from D:

- Edge (D, E): $d[E]$ is already 5 and D's path is $9+7=16$. No update.

• All vertices are visited.

Answer: The shortest path distances are: A: 0, B: 7, C: 3, D: 9, E: 5.

---

#
## 2. Bellman-Ford Algorithm

The Bellman-Ford algorithm is a more robust alternative that solves the single-source shortest path problem in the general case where edge weights may be negative. Its core principle is simple: it iteratively relaxes every edge in the graph. This process is repeated $|V|-1$ times. After $|V|-1$ iterations, if the graph contains no negative-weight cycles reachable from the source, the algorithm is guaranteed to have found the shortest paths.

A crucial feature of the Bellman-Ford algorithm is its ability to detect negative-weight cycles. If, after $|V|-1$ iterations, a further pass of relaxation still yields a shorter path for any vertex, it implies the existence of a negative-weight cycle reachable from the source.

Time Complexity:

• The algorithm consists of $|V|-1$ iterations, and each iteration involves checking all $|E|$ edges.


• Therefore, the time complexity is consistently $O(V \cdot E)$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="What is the worst-case time complexity of Dijkstra's algorithm when implemented with an adjacency list and a binary heap on a connected graph with $V$ vertices and $E$ edges?" options=["$O(V^2)$","$O(E + V \log V)$","$O(E \log V)$","$O(V \log E)$"] answer="$O(E \log V)$" hint="Consider the number of vertex extractions and edge relaxations, and the cost of priority queue operations." solution="Dijkstra's algorithm involves extracting each of the $V$ vertices from the priority queue once, with each extraction taking $O(\log V)$ time. This gives $O(V \log V)$. Additionally, every edge is relaxed at most once. A successful relaxation (distance update) may lead to a decrease-key operation in the priority queue, which also takes $O(\log V)$ time. In the worst case, this happens for all $E$ edges. Thus, the total complexity is $O(V \log V + E \log V)$. For a connected graph, $E \ge V-1$, so this is commonly simplified to $O(E \log V)$."
:::

:::question type="NAT" question="In the following weighted graph, what is the shortest path distance from vertex S to vertex T?"

S


A

B

C

T

2


6


5


-4

3

1







answer="6" hint="The graph contains a negative edge weight. Therefore, Dijkstra's algorithm is not suitable. Use the Bellman-Ford algorithm or careful path enumeration for this small graph." solution="We must account for the negative edge. Let's trace the paths from S to T.
Path 1: S -> A -> C -> T
Weight = $w(S,A) + w(A,C) + w(C,T) = 2 + 5 + 3 = 10$

Path 2: S -> B -> C -> T
Weight = $w(S,B) + w(B,C) + w(C,T) = 6 + 1 + 3 = 10$

Path 3: S -> B -> A -> C -> T
Weight = $w(S,B) + w(B,A) + w(A,C) + w(C,T) = 6 + (-4) + 5 + 3 = 10$

Path 4: S -> A -> ... (no path to B from A to take advantage of negative edge)

Let's re-evaluate using Bellman-Ford logic.
Initialize: d(S)=0, others = $\infty$

Iteration 1:
d(A) = 2
d(B) = 6

Iteration 2:
Relax(S,A): no change
Relax(S,B): no change
Relax(A,C): d(C) = d(A) + 5 = 2 + 5 = 7
Relax(B,A): d(A) = min(2, d(B) + (-4)) = min(2, 6-4) = 2. No change.
Relax(B,C): d(C) = min(7, d(B) + 1) = min(7, 6+1) = 7. No change.
Relax(C,T): d(T) = d(C) + 3 = 7 + 3 = 10

Iteration 3:
Relax(B,A): d(A) = min(2, d(B) + (-4)) = 2. No change.
Relax(A,C): d(C) = 7. No change.
Relax(B,C): d(C) = min(7, d(B)+1) = 7. No change.
Relax(C,T): d(T) = 10. No change.

It seems I missed a path. Let's trace again carefully.
Path S -> B -> A has cost $6 + (-4) = 2$. This matches the cost of path S -> A.
So, the cost to reach A is 2.
The cost to reach B is 6.
The cost to reach C can be via A (cost 2+5=7) or via B (cost 6+1=7).
Let's consider the path S -> B -> A -> C -> T. The cost is $6 + (-4) + 5 + 3 = 10$.
Let's reconsider the path enumeration.
Path S -> A -> C -> T : $2 + 5 + 3 = 10$
Path S -> B -> C -> T : $6 + 1 + 3 = 10$
Path S -> B -> A -> C -> T : $6 + (-4) + 5 + 3 = 10$

Wait, I made a mistake in the graph description. There is another path.
Ah, I see. Let's re-examine the graph.
S->A = 2
S->B = 6
From B, we can go to A with weight -4. So distance to A can be updated: d(A) = min(d(A), d(B) + w(B,A)) = min(2, 6-4) = 2. No change.
From B, we can go to C with weight 1. So d(C) = min(inf, d(B)+w(B,C)) = 6+1 = 7.
From A, we can go to C with weight 5. So d(C) = min(7, d(A)+w(A,C)) = min(7, 2+5) = 7.
So far, d(S)=0, d(A)=2, d(B)=6, d(C)=7.
Finally, from C to T, weight is 3. So d(T) = d(C) + w(C,T) = 7+3 = 10.

Let me re-read the question and re-draw the graph in my head.
S->A (2), S->B (6).
A->C (5).
B->A (-4), B->C (1).
C->T (3).

Let's try one more time.
Path 1: S -> A -> C -> T. Cost = 2 + 5 + 3 = 10.
Path 2: S -> B -> C -> T. Cost = 6 + 1 + 3 = 10.
Path 3: S -> B -> A -> C -> T. Cost = 6 + (-4) + 5 + 3 = 10.

This is very strange. A shortest path of 10 seems consistent. Is there a trick? Let me re-create the problem to have a different answer. Let's change weight S->B to 1.
S->A (2), S->B (1).
A->C (5).
B->A (-4), B->C (1).
C->T (3).

Path 1: S -> A -> C -> T. Cost = 2 + 5 + 3 = 10.
Path 2: S -> B -> C -> T. Cost = 1 + 1 + 3 = 5.
Path 3: S -> B -> A -> C -> T. Cost = 1 + (-4) + 5 + 3 = 5.
The answer would be 5.

Let me change another weight. Let's change B->C to 8.
S->A (2), S->B (6).
A->C (5).
B->A (-4), B->C (8).
C->T (3).

Path 1: S -> A -> C -> T. Cost = 2 + 5 + 3 = 10.
Path 2: S -> B -> C -> T. Cost = 6 + 8 + 3 = 17.
Path 3: S -> B -> A -> C -> T. Cost = 6 + (-4) + 5 + 3 = 10.
Still 10.

Let me change S->A to 8.
S->A (8), S->B (6).
A->C (5).
B->A (-4), B->C (1).
C->T (3).
Path 1: S -> A -> C -> T. Cost = 8 + 5 + 3 = 16.
Path 2: S -> B -> C -> T. Cost = 6 + 1 + 3 = 10.
Path 3: S -> B -> A -> C -> T. Cost = 6 + (-4) + 5 + 3 = 10.
Still 10.

Let me change B->A to -6.
S->A (2), S->B (6).
A->C (5).
B->A (-6), B->C (1).
C->T (3).
Path 1: S -> A -> C -> T. Cost = 2 + 5 + 3 = 10.
Path 2: S -> B -> C -> T. Cost = 6 + 1 + 3 = 10.
Path 3: S -> B -> A -> C -> T. Cost = 6 + (-6) + 5 + 3 = 8.
This works. Let's set the question with this.

Revised Question
In the following weighted graph, what is the shortest path distance from vertex S to vertex T?
S->A (2), S->B (6), A->C (5), B->A (-6), B->C (1), C->T (3).





S


A

B

C

T

2


6


5


-6

3

1







The correct answer is 8.

Final check of the solution steps for the new question:
Step 1: Identify paths from S to T.
Path (a): S → A → C → T.
Path (b): S → B → C → T.
Path (c): S → B → A → C → T. This path is critical because it utilizes the negative edge.

Step 2: Calculate weight of Path (a).
$Cost(a) = w(S, A) + w(A, C) + w(C, T) = 2 + 5 + 3 = 10$.

Step 3: Calculate weight of Path (b).
$Cost(b) = w(S, B) + w(B, C) + w(C, T) = 6 + 1 + 3 = 10$.

Step 4: Calculate weight of Path (c).
$Cost(c) = w(S, B) + w(B, A) + w(A, C) + w(C, T) = 6 + (-6) + 5 + 3 = 8$.

Step 5: Compare path weights.
The minimum weight is 8.

The solution is clear and correct.
I'll change the question text and solution to reflect this.
The NAT question is now good.

For the MSQ, I'll ask about properties.
Which are true?

• Dijkstra's can handle negative weights. (False)


• Bellman-Ford can detect negative cycles. (True)


• Time complexity of Bellman-Ford is O(E log V). (False, that's Dijkstra)


• Dijkstra's is a greedy algorithm. (True)

So B and D are correct.

This looks like a good set of questions. I will now write the final output.
The conciseness constraint is important. I'll keep the text focused and avoid going into too much detail on proofs or complex data structures. The current length seems appropriate.
Final review of all instructions:

• Textbook style: Yes.


• LaTeX: Yes.


• Step-by-step solutions: Yes.


• Callouts: Yes.


• Code snippets: I will add a python pseudocode for Dijkstra to be complete.


• SVG: Yes.


• Original questions: Yes.


• Structure: Yes.


• No history/bio: Yes.


• What's next: Yes.

I will add a pseudocode snippet for Dijkstra's algorithm for clarity.
```python

Pseudocode for Dijkstra's Algorithm

function Dijkstra(Graph, source):
dist = {}
prev = {}
for vertex in Graph.vertices:
dist[vertex] = infinity
prev[vertex] = null
dist[source] = 0

Q = priority_queue(Graph.vertices) # Using distance as priority

while Q is not empty:
u = Q.extract_min() # Vertex with smallest distance

for each neighbor v of u:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
Q.decrease_priority(v, alt)
return dist, prev
```
This is good. It's language-agnostic enough to be pseudocode but uses Python-like syntax for readability as requested. I'll make it clear it's pseudocode.
The overall structure and content are ready.

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="During a Depth-First Search (DFS) of a directed graph $G$, a back edge $(u, v)$ is encountered. What does the presence of this back edge imply?" options=["Vertex $v$ is an ancestor of vertex $u$ in the DFS tree.","Vertex $u$ is an ancestor of vertex $v$ in the DFS tree.","Vertices $u$ and $v$ belong to different strongly connected components.","The graph $G$ is a Directed Acyclic Graph (DAG)."] answer="A" hint="Recall the classification of edges in a DFS traversal (tree, back, forward, cross). A back edge connects a vertex to one of its ancestors in the DFS tree." solution="
In the formal analysis of a DFS traversal on a directed graph, edges $(u, v)$ are classified based on the state of vertex $v$ when the edge is first explored from $u$.

• A back edge $(u, v)$ is one where vertex $v$ is an ancestor of vertex $u$ in the DFS tree. This means that $v$ is already on the recursion stack when the edge from $u$ to $v$ is explored.
• The existence of a back edge $(u, v)$ implies there is a path from $v$ to $u$ (as $v$ is an ancestor) and an edge from $u$ back to $v$. This structure forms a cycle.

Let us evaluate the given options:

• A: Vertex $v$ is an ancestor of vertex $u$ in the DFS tree. This is the precise definition of a back edge. This statement is correct.
• B: Vertex $u$ is an ancestor of vertex $v$ in the DFS tree. If this were the case, $(u, v)$ would be a tree edge or a forward edge.
• C: Vertices $u$ and $v$ belong to different strongly connected components. A cycle implies that all vertices within it can reach each other, so they must belong to the same strongly connected component.
• D: The graph $G$ is a Directed Acyclic Graph (DAG). The presence of a back edge proves the existence of a cycle, so the graph cannot be a DAG.

Therefore, the correct implication is that $v$ is an ancestor of $u$. " :::

:::question type="NAT" question="What is the maximum number of edges in a simple, disconnected graph with 10 vertices?" answer="36" hint="To maximize the number of edges in a disconnected graph, you should create the most unbalanced partition of vertices possible and make the largest partition a complete graph." solution="
Let $G=(V, E)$ be a simple graph with $|V|=n=10$ vertices. For the graph to be disconnected, its vertices must be partitioned into at least two components. To maximize the total number of edges, we must maximize the number of edges within the components.

The maximum number of edges in a simple graph with $p$ vertices is achieved when it forms a complete graph, $K_p$, which has $\binom{p}{2} = \frac{p(p-1)}{2}$ edges.

Let us consider partitioning the 10 vertices into two components with $n_1$ and $n_2$ vertices, where $n_1 \ge 1$, $n_2 \ge 1$, and $n_1 + n_2 = 10$. The total number of edges $E$ is maximized by making each component a complete graph:

We must find the integer $n_1$ (from 1 to 9) that maximizes this function. Let's test the boundary cases:

• If the partition is $(1, 9)$: $E = \binom{1}{2} + \binom{9}{2} = 0 + \frac{9 \times 8}{2} = 36$.


• If the partition is $(2, 8)$: $E = \binom{2}{2} + \binom{8}{2} = 1 + \frac{8 \times 7}{2} = 1 + 28 = 29$.


• If the partition is $(5, 5)$: $E = \binom{5}{2} + \binom{5}{2} = 10 + 10 = 20$.

The function is minimized when the partitions are as close in size as possible and maximized when they are as far apart as possible. The most extreme partition is one component with a single vertex and the other component with the remaining $n-1 = 9$ vertices.

Thus, the maximum number of edges is achieved with a complete graph on 9 vertices, $K_9$, and one isolated vertex. The number of edges is $\binom{9}{2} = 36$.
"
:::

:::question type="MCQ" question="Consider an unweighted, connected graph $G=(V, E)$. If we run Dijkstra's algorithm starting from a source vertex $s$, which of the following statements is true regarding the order in which vertices are extracted from the priority queue?" options=["The order is identical to the order in which vertices are visited in a Breadth-First Search (BFS) starting from $s$.","The order is identical to the order in which vertices are visited in a Depth-First Search (DFS) starting from $s$.","The order is arbitrary and depends on the priority queue's implementation for vertices with the same distance.","The algorithm will not terminate correctly as it is designed for weighted graphs."] answer="A" hint="In an unweighted graph, all edge weights can be considered to be 1. How does this affect the 'distance' value that Dijkstra's algorithm uses for prioritization?" solution="
Dijkstra's algorithm finds the shortest path from a source $s$ to all other vertices. It maintains a priority queue of vertices, prioritized by their current shortest distance estimate from $s$.

In an unweighted graph, the shortest path distance between two vertices is simply the minimum number of edges on a path connecting them. We can model this as a weighted graph where every edge has a weight of $w=1$.

Let's analyze the behavior of both algorithms under this condition:

• BFS: Starting from source $s$, BFS first visits all vertices at distance 1, then all vertices at distance 2, and so on. It explores the graph in increasing order of path length (number of edges).


• Dijkstra's Algorithm: Starting with $d[s]=0$, Dijkstra's extracts $s$. It then updates the distances of all neighbors of $s$ to 1. Since all these neighbors have the same distance, they are all equally prioritized in the min-priority queue. The algorithm will then proceed to extract all vertices at distance 1 from $s$. After processing all vertices at distance 1, the next set of vertices to have the minimum distance will be those at distance 2.

This process exactly mimics the level-by-level exploration of BFS. The min-priority queue in Dijkstra's, when operating on a graph with uniform positive edge weights, effectively behaves like the FIFO queue used in BFS. Therefore, the sequence of vertices extracted from the priority queue in Dijkstra's algorithm will be identical to the sequence of vertices visited by BFS.
"
:::

:::question type="NAT" question="Consider the directed, weighted graph with vertices {S, A, B, C} and source vertex S. The edges and their weights are: (S, A, 3), (S, B, 6), (A, B, -4), (B, C, 1), (C, A, -1). After two full relaxation passes of the Bellman-Ford algorithm, what is the final shortest path estimate for vertex C, i.e., what is the value of $d[C]$?" answer="0" hint="Run the relaxation step for all edges for the first pass. Then, use the resulting distance estimates as the input for the second full pass of relaxations." solution="
We initialize the distances as $d[S] = 0$ and $d[A] = d[B] = d[C] = \infty$. The relaxation for an edge $(u, v)$ with weight $w$ updates $d[v]$ as: $d[v] = \min(d[v], d[u] + w)$.

Pass 1: We relax every edge once.

Relax (S, A, 3): $d[A] = \min(\infty, 0 + 3) = 3$.

Relax (S, B, 6): $d[B] = \min(\infty, 0 + 6) = 6$.

Relax (A, B, -4): $d[B] = \min(6, d[A] - 4) = \min(6, 3 - 4) = -1$.

Relax (B, C, 1): $d[C] = \min(\infty, d[B] + 1) = \min(\infty, -1 + 1) = 0$.

Relax (C, A, -1): $d[A] = \min(3, d[C] - 1) = \min(3, 0 - 1) = -1$.

After Pass 1, the distances are: $d[S]=0, d[A]=-1, d[B]=-1, d[C]=0$.

Pass 2: We relax every edge again, using the distances from Pass 1.

Relax (S, A, 3): $d[A] = \min(-1, 0 + 3) = -1$. (No change)

Relax (S, B, 6): $d[B] = \min(-1, 0 + 6) = -1$. (No change)

Relax (A, B, -4): $d[B] = \min(-1, d[A] - 4) = \min(-1, -1 - 4) = -5$.

Relax (B, C, 1): $d[C] = \min(0, d[B] + 1) = \min(0, -5 + 1) = -4$.

Relax (C, A, -1): $d[A] = \min(-1, d[C] - 1) = \min(-1, -4 - 1) = -5$.

After Pass 2, the distances are: $d[S]=0, d[A]=-5, d[B]=-5, d[C]=-4$.

Correction: The question asks for the value of $d[C]$ after two full passes. Let's re-verify the order of operations as they can affect intermediate results within a pass. The final state of a pass is what matters for the next. The calculation above is correct. Wait, let's re-read the problem. The graph has a negative cycle: A -> B -> C -> A with total weight (-4) + 1 + (-1) = -4. Bellman-Ford will continue to decrease the estimates. However, the question asks for the estimate after exactly two passes.

Let's re-run the calculation very carefully.
Initial: $d[S]=0, d[A]=\infty, d[B]=\infty, d[C]=\infty$

Pass 1:

• $d[A] = 3$


• $d[B] = 6$


• $d[B] = \min(6, 3-4) = -1$


• $d[C] = \min(\infty, -1+1) = 0$


• $d[A] = \min(3, 0-1) = -1$

End of Pass 1: $d=\{S:0, A:-1, B:-1, C:0\}$

Pass 2:

• Relax (S, A, 3): $d[A]=\min(-1, 0+3) = -1$


• Relax (S, B, 6): $d[B]=\min(-1, 0+6) = -1$


• Relax (A, B, -4): $d[B]=\min(-1, -1-4) = -5$


• Relax (B, C, 1): $d[C]=\min(0, -5+1) = -4$


• Relax (C, A, -1): $d[A]=\min(-1, -4-1) = -5$

End of Pass 2: $d=\{S:0, A:-5, B:-5, C:-4\}$

The final shortest path estimate for vertex C after two passes is -4. Let me re-calculate the previous NAT question with the sum.
(S, A, 2), (S, B, 5), (A, B, -4), (A, C, 2), (B, C, 3)
d[A]=2, d[B]=5 -> d[B]=min(5,2-4)=-2, d[C]=min(inf, 2+2)=4, d[C]=min(4, -2+3)=1. Sum = 2-2+1=1. That was correct.

Rethinking this question. Perhaps I made it too complex. Let's use a simpler graph without a cycle to be safe and clear.
New NAT question:
Consider the directed, weighted graph with vertices {S, A, B, C} and source vertex S. The edges and their weights are: (S, A, 2), (S, B, 5), (A, B, 1), (A, C, 8), (B, C, 3). After one full relaxation pass of the Bellman-Ford algorithm (in the given edge order), what is the shortest path estimate for vertex C?

Let's solve this one.
Initial: $d[S]=0, d[A]=\infty, d[B]=\infty, d[C]=\infty$
Pass 1:

Relax(S,A,2): $d[A]=2$

Relax(S,B,5): $d[B]=5$

Relax(A,B,1): $d[B]=\min(5, 2+1)=3$

Relax(A,C,8): $d[C]=\min(\infty, 2+8)=10$

Relax(B,C,3): $d[C]=\min(10, 3+3)=6$

End of pass 1, $d[C]=6$. This is a better question. I will use this instead. It's cleaner.

Final Answer Generation: I will replace the complex NAT question with this simpler one.

:::question type="NAT" question="Consider the directed, weighted graph with vertices {S, A, B, C} and source vertex S. The edges and their weights are given in order: (S, A, 2), (S, B, 5), (A, B, 1), (A, C, 8), (B, C, 3). After one full relaxation pass of the Bellman-Ford algorithm, what is the shortest path estimate for vertex C?" answer="6" hint="Perform the relaxation step $d[v] = \min(d[v], d[u] + w)$ for each edge exactly once, in the specified order. Remember that distance estimates updated within the pass are used for subsequent relaxations in the same pass." solution="
We initialize the distances from the source $S$ as $d[S] = 0$ and $d[v] = \infty$ for all other vertices $v$. We will perform one pass of relaxation, updating the distance estimates for each edge in the given sequence.

Initial state: $d[S] = 0, d[A] = \infty, d[B] = \infty, d[C] = \infty$.

Relax (S, A, 2):

$d[A] = \min(\infty, d[S] + 2) = \min(\infty, 0 + 2) = 2$.
Current distances: $\{S:0, A:2, B:\infty, C:\infty\}$

Relax (S, B, 5):

$d[B] = \min(\infty, d[S] + 5) = \min(\infty, 0 + 5) = 5$.
Current distances: $\{S:0, A:2, B:5, C:\infty\}$

Relax (A, B, 1): We use the newly computed $d[A]=2$.

$d[B] = \min(5, d[A] + 1) = \min(5, 2 + 1) = 3$.
Current distances: $\{S:0, A:2, B:3, C:\infty\}$

Relax (A, C, 8): We use $d[A]=2$.

$d[C] = \min(\infty, d[A] + 8) = \min(\infty, 2 + 8) = 10$.
Current distances: $\{S:0, A:2, B:3, C:10\}$

Relax (B, C, 3): We use the updated $d[B]=3$.

$d[C] = \min(10, d[B] + 3) = \min(10, 3 + 3) = 6$.
Current distances: $\{S:0, A:2, B:3, C:6\}$

After one full pass of relaxation, the shortest path estimate for vertex C is 6.
"
:::

---

What's Next?