UNIT 3.

Greedy Algorithms :
• A greedy algorithm builds a solution step by step, choosing the best
possible option at each stage.
• It makes decisions based on local optimization, hoping this leads
to a global optimum.
• Once a choice is made, it is not reconsidered or changed later.
• It works correctly only for problems that have the greedy-choice
property and optimal substructure.

Optimal Substructure :
• A problem has optimal substructure if its optimal solution can be
built from the optimal solutions of its subproblems.
• In such problems, solving smaller parts optimally leads to the
overall optimal solution.
• This property is essential for greedy algorithms and dynamic
programming.

Characteristics of Greedy Algorithms:

• Feasibility — Each chosen step must satisfy the problem constraints.
• Local Optimal Choice — Pick the best among available options.
• Irrevocability — Once a choice is made, it cannot be changed.
• Optimal Substructure — Problem can be solved optimally by combining
optimal solutions of subproblems.
• Greedy-choice property — A global optimum can be reached by choosing
a local optimum at each step.

Examples of Greedy Algorithms :

Problem Greedy Choice
Fractional Knapsack Pick item with highest value/weight ratio
Job Sequencing with Select job with highest profit that fits
Deadlines the slot
Huffman Coding Combine two smallest frequencies
Pick minimum-weight edge connecting tree
Prim’s Algorithm
to new vertex
Pick smallest edge that doesn’t form a
Kruskal’s Algorithm
cycle
Pick next vertex with minimum tentative
Dijkstra’s Algorithm
distance

P a g e 1 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Fractional Knapsack Problem:
You are given:
• A set of items, each with:
o value 𝑣𝑖
o weight 𝑤𝑖
• A knapsack (bag) with maximum capacity 𝑊
You must:
• Maximize total value in the knapsack
• You can take fractions of items (unlike 0/1 knapsack)

Greedy Approach:
1. Compute value per unit weight for each item:
𝑣𝑖
ratio =
𝑤𝑖

2. Sort all items in decreasing order of this ratio.

3. Pick items one by one:
o If the item fits fully → take it.
o If not → take the fraction that fits.
4. Stop when the knapsack is full.

PseudoCode:
FRACTIONAL-KNAPSACK(v, w, n, W)
1 for i ← 1 to n
2 do ratio[i] ← v[i] / w[i]
3 sort items in nonincreasing order of ratio[i]
4 totalValue ← 0
5 remainingCapacity ← W
6 for i ← 1 to n
7 do if w[i] ≤ remainingCapacity
8 then totalValue ← totalValue + v[i]
9 remainingCapacity ← remainingCapacity - w[i]
10 else
11 fraction ← remainingCapacity / w[i]
12 totalValue ← totalValue + v[i] * fraction
13 return totalValue
14 return totalValue
Complexity
• Computing ratio: 𝑂(𝑛)
• Sorting: 𝑂(𝑛log⁡ 𝑛)
• Selection loop: 𝑂(𝑛)
• Total = O(n log n)

Example
Find the optimal solution for fractional knapsack problem for the
capacity 50, weight W={10,20,30} and value V={60,100,120}.

P a g e 2 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Item Value (v) Weight (w) Ratio(v/w)
1 60 10 6
2 100 20 5
3 120 30 4
Capacity 𝑊 = 50

Step 1. Sort by ratio (already sorted)

Item Ratio(v/w) Value Weight
1 6 60 10
2 5 100 20
3 4 120 30

Step 2. Start filling

Take item 1 – weight <= remaining (10 ≤ 50) →
Total = 60, Remaining = 40
Take item 2 – weight <= remaining (20 ≤ 40) →
Total = 160, Remaining = 20
Take item 3 – weight>remaining (30>20) →
Added value = remaining*ratio = 20 * 4 = 80

Total = 160 + 80 = 240

P a g e 3 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Job Sequencing with Deadlines:
You are given n jobs, each with:
• a deadline (time by which it must be completed), and
• a profit (earned if the job is completed before or on its deadline).
Each job takes one unit of time, and only one job can be scheduled
at a time.
The goal is to maximize total profit.

Greedy Approach:
1. Sort all jobs in decreasing order of profit.
2. For each job (in that order):
o Schedule it in the latest available time slot before its
deadline. (as far as possible)
o If no slot is available, skip it.
3. This ensures maximum profit while meeting deadlines.

PseudoCode:
JOB-SEQUENCING(jobs[1..n])
1 sort jobs in decreasing order of profit
2 find maxDeadline ← maximum of all deadlines
3 create timeSlot[1..maxDeadline] initialized to empty
4 totalProfit ← 0
5 for i ← 1 to n
6 do for j ← min(maxDeadline, jobs[i].deadline) downto 1
7 if timeSlot[j] is empty
8 then timeSlot[j] ← jobs[i]
9 totalProfit ← totalProfit + jobs[i].profit
10 break
11 return totalProfit, timeslot

Time Complexity
• Sorting: 𝑂(𝑛log⁡ 𝑛)
• Scheduling: 𝑂(𝑛 × 𝑛), assuming 𝑛= max deadline
→ Typically 𝑂(𝑛2 ) in basic implementation.

Example:
Schedule the following job to get the maximum profit.

Job Deadline Profit

A 2 100
B 1 19
C 2 27
D 1 25
E 3 15

P a g e 4 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Step 1: Sort by profit (descending)
Job Deadline Profit
A 2 100
C 2 27
D 1 25
B 1 19
E 3 15

Step 2: Schedule jobs

We have total 3 slots. [ slot1, slot2, slot3 ]

Job A (profit = 100, deadline = 2)

• Latest possible slot ≤ 2 → slot 2
• Slot 2 is free → place A in slot 2
Schedule:
[ _, A, _ ]

Job C (profit = 27, deadline = 2)

• Latest possible slot ≤ 2 → check slot 2 → occupied by A
• Check previous slot (1) → free → place C in slot 1
Schedule:
[ C, A, _ ]

Job D (profit = 25, deadline = 1)

• Latest possible slot ≤ 1 → slot 1 → already occupied (by C)
• No earlier slot available → cannot schedule D
Skip D

Job B (profit = 19, deadline = 1)

• Slot 1 already filled → skip
Skip B

Job E (profit = 15, deadline = 3)

• Latest possible slot ≤ 3 → slot 3 → free → place E in slot 3
Schedule:
[ C, A, E ]

Total Profit = 27 + 100 + 15 = 142

P a g e 5 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Huffman Coding :
• Huffman Coding is a lossless data compression algorithm based on
variable-length codes.
• It assigns shorter binary codes to more frequent characters and
longer codes to less frequent ones.
• Works on the Greedy approach, combining the two least frequent
symbols repeatedly.

Approach :
• Build a binary tree (Huffman Tree) based on character frequencies.
• Each leaf node represents a character.
• Traversing left adds a 0, traversing right adds a 1.
• Characters with higher frequency get shorter codes → reduces total
bits.

Pseudocode:
HUFFMAN(C)
1 n ← |C| // number of characters
2 create a min-priority queue Q containing all characters in C
3 for i ← 1 to n - 1
4 do allocate a new node z
5 [Link] ← x ← EXTRACT-MIN(Q)
6 [Link] ← y ← EXTRACT-MIN(Q)
7 [Link] ← [Link] + [Link]
8 INSERT(Q, z)
9 return EXTRACT-MIN(Q) // root of the Huffman tree

Complexity :
• Building priority queue: 𝑂(𝑛)
• Extract-min & insert (n−1 times): 𝑂(𝑛log⁡ 𝑛)
Overall time complexity = O(n log n)

Frequency Path Length (FPL): The sum of (frequency × code length) for
all symbols. It represents the total cost (weighted path length) of
the Huffman tree.
Average Length : The average number of bits used per symbol in the
encoded message.

Example :
Let’s take 6 characters with frequencies:
Character Frequency
A 5
B 9
C 12
D 13
E 16
F 45
Total = 100 characters

P a g e 6 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Step 0: Initialize Min-Heap
Start with all leaf nodes (characters as individual trees):
A(5) B(9) C(12) D(13) E(16) F(45)

Step 1: Combine two smallest (A=5, B=9)

Create a new node with frequency = 5 + 9 = 14
(14)
/ \
A(5) B(9)

Now heap becomes:

AB(14), C(12), D(13), E(16), F(45)

Step 2: Combine next two smallest (C=12, D=13)

New node = 12 + 13 = 25
(25)
/ \
C(12) D(13)

Now heap becomes:

AB(14), CD(25), E(16), F(45)

Step 3: Combine next two smallest (14, 16)

New node = 14 + 16 = 30
(30)
/ \
(14) E(16)
/ \
A(5) B(9)

Heap now:
CD(25), ABE(30), F(45)

Combine next two smallest (25, 30)

New node = 25 + 30 = 55
(55)
/ \
(25) (30)
/ \ / \
C(12) D(13) (14) E(16)
/ \
A(5) B(9)

Heap now:
F(45), CDABE(55)

P a g e 7 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Step 5: Combine remaining two nodes (45, 55)
New root = 45 + 55 = 100
(100)
/ \
F(45) (55)
/ \
(25) (30)
/ \ / \
C(12) D(13) (14) E(16)
/ \
A(5) B(9)

Final Huffman Tree

(100)
/ \
F(45) (55)
/ \
(25) (30)
/ \ / \
C(12) D(13) (14) E(16)
/ \
A(5) B(9)
Assign Binary Codes
(Left = 0, Right = 1) and traverse the tree.
Character Code
F 0
C 100
D 101
A 1100
B 1101
E 111

Total Bits Required (Frequency Path Length) :

FPL = 45 × 1 + 16 × 3 + 13 × 3 + 12 × 3 + 9 × 4 + 5 × 4 = 𝟐𝟐𝟒 bits

If fixed-length codes (3 bits each) were used for 6 symbols →

6 × 3 × 100 = 1800 bits for 100 symbols.

Do It Yourself:
A text is made up of the characters a, b, c, d, e each occurring
with the probabilities 0.11, 0.40, 0.16, 0.09, and 0.24
respectively.
The optimal Huffman coding technique will have the average length ?
Hint :

P a g e 8 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Graph : A graph G is defined as an ordered pair G = (V, E) where:
• V is a set of vertices (also called nodes)
• E is a set of edges (also called links) connecting pairs of
vertices
• A graph can be represented using
o Adjacency Matrix
A B C
A 0 1 0
B 1 0 1
C 0 1 0
o Adjacency List
A: [B]
B: [A, C]
C: [B]

Tree : A tree is an undirected, acyclic, and connected graph.

• Acyclic: No cycles or loops
• Connected: All nodes are reachable from any other node
• Exactly n-1 edges for n vertices
• Unique path between any two vertices
• Adding any edge creates a cycle
• Removing any edge disconnects the tree

P a g e 9 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Spanning Tree : It's the "skeleton" that connects all points using
the fewest possible connections without creating any loops.
• A subgraph of the original graph
• Contains all vertices of the original graph
• Connected - there is a path between every pair of vertices
• Acyclic - contains no cycles or loops
• Uses the minimum number of edges possible while maintaining
connectivity
• Has exactly n-1 edges for a graph with n vertices
• Forms a tree structure within the original graph

Minimum Spanning Tree :

• is a spanning tree with the minimum possible total edge
weight among all possible spanning trees of a weighted graph.
• It follow all the properties of a spanning tree.

P a g e 10 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 A single graph can have multiple Minimum Spanning Trees:

Prims Algorithm :
• Used to find a Minimum Spanning Tree (MST) of a connected, undirected,
weighted graph.
• It is a greedy algorithm – always chooses the edge with minimum
weight connecting MST to a new vertex.
• Starts from any vertex and gradually grows the MST by adding
minimum-weight edges.
• Stops when all vertices are included in the MST.
• Ensures no cycles in the MST.

Pseudocode:
PRIM(G, w, r) // G = graph, w = weight function, r = starting vertex
1. for each u in G.V
2. [Link] = ∞
3. u.π = NIL
4. [Link] = 0
5. Q = G.V // priority queue ordered by key
6. while Q is not empty
7. u = EXTRACT-MIN(Q)
8. for each v in [Link][u]
9. if v in Q and w(u,v) < [Link]
10. v.π = u
11. [Link] = w(u,v)

• key stores the minimum weight edge connecting the vertex to MST.
• π (parent) keeps track of the MST edges.
• EXTRACT-MIN(Q) picks the vertex with the smallest key not yet in MST.

Time Complexity :
1. Using an Adjacency Matrix and Simple Array
• For each of the V vertices, we find the minimum key vertex not yet
included in MST → O(V) per iteration.
• For each selected vertex, we check all its adjacent vertices → O(V)
per iteration.
So total: 𝑇(𝑉) = 𝑂(𝑉) × 𝑂(𝑉) = 𝑂(𝑉 2 )

P a g e 11 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 2. Using an Adjacency List and Min-Heap (Binary Heap)
• Extract-Min(Q): takes O(log V) time.
→ done V times → O(V log V)
• Decrease-Key: for each edge relaxation, possibly called E times,
each taking O(log V) → O(E log V)
So total: 𝑇(𝑉, 𝐸) = 𝑂((𝑉 + 𝐸)log⁡ 𝑉) => O(E log V)

3. Using Fibonacci Heap

𝑇(𝑉, 𝐸) = 𝑂(𝐸 + 𝑉log⁡ 𝑉)

Example:

Step 0: Initialization
Keys: A=0, B=∞, B=∞, D=∞, E=∞, F=∞
Parent: A=NIL, B=NIL, C=NIL,
D=NIL, E=NIL, F=NIL
MST: {}
Queue: {A, B, C, D, E, F}

Step 1: Process A (key=0)

Keys: A=0, B=12, C=8, D=∞, E=∞, F=3
Parent: A=NIL, B=A, C=A, D=NIL,
E=NIL, F=A
MST: {A}
Queue: {B, C, D, E, F}

Step 2: Process F (key=3)

Keys: A=0, B=12, C=8, D=∞, E=3, F=3
Parent: A=NIL, B=A, C=A, D=NIL,
E=F, F=A
MST: {A, F}
Queue: {B, C, D, E}

P a g e 12 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Step 3: Process E (key=3)
Keys: A=0, B=12, C=1, D=9, E=3, F=3
Parent: A=NIL, B=A, C=E, D=E, E=F,
F=A
MST: {A, F, E}
Queue: {B, C, D}

Step 4: Process C (key=1)

Keys: A=0, B=5, C=1, D=6, E=3, F=3
Parent: A=NIL, B=C, C=E, D=C, E=F,
F=A
MST: {A, F, E, C}
Queue: {B, D}

Step 5: Process B (key=5)

Keys: A=0, B=5, C=1, D=6, E=3, F=3
Parent: A=NIL, B=C, C=E, D=C, E=F,
F=A
MST: {A, F, E, C, B}
Queue: {D}

Step 6: Process D (key=6)

Keys: A=0, B=5, C=1, D=6, E=3, F=3
Parent: A=NIL, B=C, C=E, D=C, E=F,
F=A
MST: {A, F, E, C, B, D}
Queue: {}

MST == >

P a g e 13 | 20 U2_Part 2 of 2_DAA_GECS_2K23
Kruskal’s Algorithm :
• Kruskal’s Algorithm is a greedy algorithm used to find a Minimum
Spanning Tree (MST) of a connected, weighted, undirected graph.
• It works by selecting edges in increasing order of weight.
• At each step, the smallest edge is chosen that does not form a
cycle with the already selected edges.
• The algorithm continues until the MST contains (V – 1) edges, where
V is the number of vertices.
• It uses the Disjoint Set Union (DSU) or Union-Find data structure
to efficiently detect cycles.

Algorithm Steps :
1. Sort all edges in the graph in non-decreasing order of their
weights.
2. Initialize an empty set (or list) for the MST.
3. For each edge (u, v) in sorted order:
o If adding the edge does not form a cycle, include it in the
MST.
o Else, discard it.
4. Stop when MST has (V – 1) edges (where V = number of vertices).

Pseudocode:
KRUSKAL(G, w)
1. A = ∅
2. for each vertex v ∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into non-decreasing order by weight w
5. for each edge (u, v) ∈ G.E, taken in sorted order
6. if FIND-SET(u) ≠ FIND-SET(v)
7. A = A ∪ {(u, v)}
8. UNION(u, v)
9. return A

MAKE-SET : Creates a new set containing only the element x.

MAKE-SET(x)
parent[x] = x // Each element is its own parent
rank[x] = 0 // Rank is initially zero

FIND-SET : Returns the root of the set containing x.

FIND-SET(x)
if parent[x] ≠ x
parent[x] = FIND-SET(parent[x])
return parent[x]

P a g e 14 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 UNION : Combines two disjoint sets containing x and y.
UNION(x, y)
xRoot = FIND-SET(x)
yRoot = FIND-SET(y)
if xRoot == yRoot
return // Already in same set
if rank[xRoot] < rank[yRoot]
parent[xRoot] = yRoot
else if rank[xRoot] > rank[yRoot]
parent[yRoot] = xRoot
else
parent[yRoot] = xRoot
rank[xRoot] = rank[xRoot] + 1

Time Complexity:
KRUSKAL-MST(G):
1. MST = ∅
2. for each vertex v ∈ G.V:
3. MAKE-SET(v) → O(V)
4. sort G.E by weight → O(E log E)
5. for each edge (u, v) ∈ G.E (in sorted order): → O(E) iterations
6. if FIND-SET(u) ≠ FIND-SET(v): → O(α(V)) ≈ O(1)
7. MST = MST ∪ {(u, v)} → O(1)
8. UNION(u, v) → O(α(V)) ≈ O(1)

Total = O(V) + O(E log E) + O(E × 1)

= O(E log E + V)
Since E ≥ V-1 for connected graphs:
O(E log E + V) = O(E log E)

Example:
Sets:
{A}, {B}, {C}, {D}, {E}, {F}

Sorted edges:
Weight
Edge
(C, E) 1
(A, F) 3
(E, F) 3
(B, C) 5
(C, D) 6
(A, C) 8
(D, E) 9
(A, B) 12

P a g e 15 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Extract Edge 1: (C,E)=1

Edge 1: (C, E) = 1
• FIND-SET(C) = {C}
• FIND-SET(E) = {E}
• Disjoint → Add (C, E) to A
• UNION(C, E)

Sets : {C, E}, {A}, {B}, {D}, {F}

MST A = { (C, E) }

Edge 2: (A, F) = 3

Edge 2: (A, F) = 3
• FIND-SET(A) = {A}
• FIND-SET(F) = {F}
• Disjoint → Add (A, F) to A
• UNION(A, F)

Sets : {C, E}, {A, F}, {B}, {D}

MST A = { (C, E), (A, F) }

Edge 3: (E, F) = 3

Edge 3: (E, F) = 3
• FIND-SET(E) = {C, E}
• FIND-SET(F) = {A, F}
• Disjoint → Add (E, F) to A
• UNION(E, F)

Sets : {A, F, C, E}, {B}, {D}

MST A = { (C, E), (A, F), (E, F) }

Edge 4: (B, C) = 5

Edge 4: (B, C) = 5
• FIND-SET(B) = {B}
• FIND-SET(C) = {A, F, C, E}
• Disjoint → Add (B, C) to A
• UNION(B, C)

Sets : {A, B, C, E, F}, {D}

MST A = { (C, E), (A, F), (E, F), (B, C) }

P a g e 16 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Edge 5: (C, D) = 6
Edge 5: (C, D) = 6
• FIND-SET(C) = {A, B, C, E, F}
• FIND-SET(D) = {D}
• Disjoint → Add (C, D) to A
• UNION(C, D)

Sets : {A, B, C, D, E, F}
MST A = { (C, E), (A, F), (E, F), (B, C), (C, D) }

MST A = { (C, E), (A, F), (E, F), (B, C), (C, D) }

Dijkstra’s Algorithm :
• Finds the shortest path from a single source vertex to all other
vertices in a weighted graph with non-negative edge weights.
• It is a greedy algorithm because it always selects the vertex with
the minimum tentative distance next.
Approach:
o Initialization: Set all distances to infinity except the
source (0).
o Selection: Pick the vertex with the minimum distance using a
priority queue (min heap).
o Relaxation: Update the distances of all adjacent vertices if
a shorter path is found.
Time Complexity (using min Heap):
o O((V+E)logV)
Application
o Shortest route in maps and navigation systems
o Network routing protocols
o Flight or transport scheduling

P a g e 17 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Pseudocode:
DIJKSTRA(G, w, s)
1. INITIALIZE-SINGLE-SOURCE(G, s)
2. S = ∅
3. Q = G.V
4. while Q ≠ ∅
5. u = EXTRACT-MIN(Q)
6. S = S ∪ {u}
7. for each vertex v ∈ [Link][u]
8. RELAX(u, v, w)

INITIALIZE-SINGLE-SOURCE(G, s)
1. for each vertex v ∈ G.V
2. v.d = ∞
3. v.π = NIL
4. s.d = 0

RELAX(u, v, w)
1. if v.d > u.d + w(u, v)
2. v.d = u.d + w(u, v)
3. v.π = u

Time Complexity Analysis:

DIJKSTRA(G, w, s)
1. INITIALIZE-SINGLE-SOURCE(G, s) // O(V)
2. S = ∅ // O(1)
3. Q = G.V // O(V) - build heap
4. while Q ≠ ∅ // O(V) iterations
5. u = EXTRACT-MIN(Q) // O(log V) per extraction
6. S = S ∪ {u} // O(1)
7. for each vertex v ∈ [Link][u] // O(deg(u)) per vertex
8. RELAX(u, v, w) // O(log V) per relaxation

INITIALIZE-SINGLE-SOURCE(G, s)
1. for each vertex v ∈ G.V // O(V) iterations
2. v.d = ∞ // O(1)
3. v.π = NIL // O(1)
4. s.d = 0 // O(1)

RELAX(u, v, w)
1. if v.d > u.d + w(u, v) // O(1)
2. v.d = u.d + w(u, v) // O(1)
3. v.π = u // O(1)
// Note: If using heap, DECREASE-KEY takes O(log V)

Total Time Complexity:

• EXTRACT-MIN: O(V) calls × O(log V) = O(V log V)
• RELAX/DECREASE-KEY: O(E) calls × O(log V) = O(E log V)
• Initialization: O(V)
• Total: O((V + E) log V)

P a g e 18 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Example:
dist: a=0, b=∞, c=∞, d=∞, e=∞, z=∞

parent: all NIL

Heap: [(0, a)]

FINALIZED = { }

Extract (0, a) → finalize a

Relax neighbors of a:
• a→b: 0 + 4 = 4 → dist[b]=4
• a→c: 0 + 2 = 2 → dist[c]=2

a: dist=0, parent=NIL
b: dist=4, parent=a
c: dist=2, parent=a
d: dist=∞, parent=NIL
e: dist=∞, parent=NIL
z: dist=∞, parent=NIL
FINALIZED = {a}
Heap: [(2, c), (4, b)]

Extract (2, c) (finalize c)

c→b: 2 + 1 = 3 → 3 < dist → update dist[b]=3, parent[b]=c
c→d: 2 + 8 = 10 → dist[d]=10, parent[d]=c
c→e: 2 + 10 = 12 → dist[e]=12, parent[e]=c
a: dist=0, parent=NIL
b: dist=3, parent=c
c: dist=2, parent=a
d: dist=10, parent=c
e: dist=12, parent=c
z: dist=∞, parent=NIL
FINALIZED = {a, c}
Heap: [(3, b), (10, d), (12, e)]

Extract (3, b) (finalize b)

b→d: candidate 3 + 5 = 8 → 8 < dist → update dist[d]=8, parent[d]=b
b→c: candidate 3 + 1 = 4 → 4 > dist → no change

a: 0, parent=NIL
b: 3, parent=c
c: 2, parent=a
d: 8, parent=b
e: 12, parent=c
z: ∞, parent=NIL
FINALIZED = {a, c, b}
Heap: [(8, d), (12, e)]

P a g e 19 | 20 U2_Part 2 of 2_DAA_GECS_2K23
 Extract (8, d) (finalize d)
d→e: 8 + 2 = 10 → 10 < dist → update dist[e]=10, parent[e]=d
d→z: 8 + 6 = 14 → dist[z]=14, parent[z]=d
(other relaxations to b or c give no improvements)

a: dist=0, parent=NIL
b: dist=3, parent=c
c: dist=2, parent=a
d: dist=8, parent=b
e: dist=10, parent=d
z: dist=14, parent=d
FINALIZED = {a, c, b, d}
Heap: [(10, e), (14, z)]

Extract (10, e) (finalize e)

e→z: 10 + 5 = 15 → 15 > dist → no update
e→c: 10 + 10 = 20 → 20 > dist → no update
a: dist=0, parent=NIL
b: dist=3, parent=c
c: dist=2, parent=a
d: dist=8, parent=b
e: dist=10, parent=d
z: dist=14, parent=d
FINALIZED = {a, c, b, d, e}
Heap: [(14, z)]

Extract (14, z) (finalize z)

No relaxations give improvements.

a: dist = 0, parent = NIL

b: dist = 3, parent = c(path: a → c → b)
c: dist = 2, parent = a (path: a → c)
d: dist = 8, parent = b (path: a → c → b → d)
e: dist = 10, parent = d (path: a → c → b → d → e)
z: dist = 14, parent = d (path: a → c → b → d → z)
FINALIZED = {a, c, b, d, e, z}

P a g e 20 | 20 U2_Part 2 of 2_DAA_GECS_2K23