• Design and Analysis of Algorithms (DAA)

Unit-4
Greedy Algorithms
 Outline
  Optimization Problems and Optimal Solution, Introduction of
Looping
Greedy Algorithms, Elements of Greedy Strategy.
 Greedy Algorithms: Fractional Knapsack, Job sequencing with
Deadlines, Kruskal’s Algorithm, Prims Algorithm, Dijkstra’s
Algorithm and their Analysis
 Huffman Coding: Purpose of Huffman Coding, Prefix Codes,
Huffman Coding Algorithm and its Analysis General
Characteristics of greedy algorithms
Introduction
Optimized Problems and Optimal Solution
• In mathematics and computer science, an optimization problem is the problem of
finding best solution from all feasible solutions.
• An optimal solution is a feasible solution where the objective function reaches its
maximum or minimum value. For example, the most profit or the least cost.
• A globally optimal solution is one where there are no other feasible solutions with
better objective function values.
• A locally optimal solution is one where there are no other feasible solutions in the
vicinity(surrounding) with better objective function values
Introduction to Greedy Algorithms
• Greedy algorithm solves problems by making the best choice that seems best at
the particular moment.
• Greedy algorithm may provide a solution that is close to optimal.
• Greedy approach is used to solve many problems like finding shortest path
between two vertices using Dijkstra’s algorithm
Characteristics of Greedy Algorithms
• Greedy algorithms are characterized by the following features.
1. Greedy approach forms a set or list of candidates 𝑪.
2. Once a candidate is selected in the solution, it is there forever: once a candidate is
excluded from the solution, it is never reconsidered.
3. To construct the solution in an optimal way, Greedy Algorithm maintains two sets.
4. One set contains candidates that have already been considered and chosen, while the
other set contains candidates that have been considered but rejected.

• The greedy algorithm consists of four functions.

i. Solution Function:- A function that checks whether chosen set of items provides a
solution.
ii. Feasible Function:- A function that checks the feasibility of a set.
iii. Selection Function:- The selection function tells which of the candidates is the most
promising.
iv. Objective Function:- An objective function, gives the value of a solution.
Knapsack Problem
Knapsack Problem
Fractional Knapsack Problem
Introduction
• We are given 𝑛 objects and a knapsack.
• Object 𝒊 has a positive weight 𝒘𝒊 and a positive value 𝒗𝒊 for 𝒊 = 𝟏, 𝟐 … 𝒏.
• The knapsack can carry a weight not exceeding 𝑾.
• Our aim is to fill the knapsack in a way that maximizes the value of the included objects,
while respecting the capacity constraint.
• In a fractional knapsack problem, we assume that the objects can be broken into
smaller pieces.
• So we may decide to carry only a fraction 𝒙𝒊 of object 𝒊, where 𝟎 ≤ 𝒙𝒊 ≤ 𝟏.
• In this case, object 𝒊 contribute 𝒙𝒊 𝒘𝒊 to the total weight in the knapsack, and 𝒙𝒊 𝒗𝒊 to the
value of the load.
• Symbolic Representation of the problem can be given as follows:
maximize 𝒏𝒊=𝟏 𝒙𝐢 𝒗𝐢 subject to 𝒏𝒊=𝟏 𝒙𝐢 𝒘𝐢 ≤ 𝑾
Where, 𝑣𝑖 > 0, 𝑤𝑖 > 0 and 0 ≤ 𝑥𝑖 ≤ 1 for 1 ≤ 𝑖 ≤ 𝑛.
Fractional Knapsack Problem - Example
• We are given 5 objects and the weight carrying capacity of knapsack is 𝑾 = 𝟏𝟎𝟎.
• For each object, weight 𝑤𝑖 and value 𝑣𝑖 are given in the following table.
Object 𝑖 1 2 3 4 5
𝑣𝑖 20 30 66 40 60
𝑤𝑖 10 20 30 40 50

• Fill the knapsack with given objects such that the total value of knapsack is
maximized.
Fractional Knapsack Problem - Greedy Solution
• Three Selection Functions can be defined as,
1. Sort the items in descending order of their values and select the items till weight criteria
is satisfied.
2. Sort the items in ascending order of their weight and select the items till weight criteria is
satisfied.
3. To calculate the ratio value/weight for each item and sort the item on basis of this ratio.
Then take the item with the highest ratio and add it.
Fractional Knapsack Problem - Greedy Solution
Object 𝑖 1 2 3 4 5
𝑣𝑖 20 30 66 40 60
𝑤𝑖 10 20 30 40 50
𝑣𝑖 2.0 1.5 2.2 1.0 1.2
𝑤𝑖

Selection Objects Value Weight

1 2 3 4 5 Capacity 100
Max 𝑣𝑖 0 0 1 0.5 1 146 30 50 20
Min 𝑤𝑖 1 1 1 1 0 156 10 20 30 40
Max 𝑣𝑖 𝑤𝑖 1 1 1 0 0.8 164 30 10 20 40

Profit
Profit==66
Profit 66 20
20++60 30 *+ 0.5)
30++(40
66 48 ==156
40 164
146
Fractional Knapsack Problem - Algorithm
Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for (i = 1; i<=n; i++)
calculate PW[i] = p[i]/w[i]
Sort objects in decreasing order of P/W ratio
for (i = 1; i<=n; i++)
x[i] ← 0
weight ← 0 , P ← 0, i ← 1
W = 100 and Current weight in knapsack= 60
While(weight < W)
Object weight = 50
if (weight + w[i] ≤ W) then The fraction of object to be included will be
x[i] ← 1 (100 – 60) / 50 = 0.8
else
x[i] ← (W - weight) / w[i]
weight ← weight + w[i] *x[i]
P ← P + P[i]*x[i]
i++
end while
Analysis
• Since, we need to calculate PW ratio for n so it takes O(n)
• We need to sort objects in decreasing order on the basis of P/W ratio thus
sorting takes O(nlogn) time.
• Initialization of n elements need most O(n)
• While loop takes another n steps at worst so O(n)
• So, total time complexity T(n) = O(n)+O(nlogn)+O(n)+O(n)= O(nlogn)
Exercises – Home Work
1. Consider Knapsack capacity 𝑊 = 50, 𝑤 = (10, 20, 40) and 𝑣 =
(60, 80,100) find the maximum profit using greedy approach.
2. Consider Knapsack capacity 𝑊 = 10, 𝑤 = (4, 8, 2, 6, 1) and 𝑣 =
(12, 32, 40, 30, 50). Find the maximum profit using greedy approach.
Job Scheduling with Deadlines
Introduction
• We have set of 𝒏 jobs to execute, each of which takes unit time.
• At any point of time we can execute only one job.
• Job 𝒊 earns profit 𝒈𝒊 > 𝟎 if and only if it is executed no later than its deadline 𝒅𝒊 .
• We have to find an optimal sequence of jobs such that our total profit is
maximized.
• Feasible jobs: A set of job is feasible if there exits at least one sequence that
allows all the jobs in the set to be executed no later than their respective
deadlines.
Job Scheduling with Deadlines - Example
• Using greedy algorithm find an optimal schedule for following jobs with 𝒏 = 𝟔.
• Profits: (𝑃1 , 𝑃2 , 𝑃3 , 𝑃4 , 𝑃5 , 𝑃6 ) = (15,20,10,7,5,3) &
• Deadline: (𝑑1 , 𝑑2 , 𝑑3 , 𝑑4 , 𝑑5 , 𝑑6 ) = (1, 3, 1, 3, 1, 3)
Solution:
Step 1: Sort the jobs in decreasing order of their profit.

Job 𝑖 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔
Profit 𝑔𝑖 𝟐𝟎 𝟏𝟓 𝟏𝟎 𝟕 𝟓 𝟑
Deadline 𝑑𝑖 . 𝟑 𝟏 𝟏 𝟑 𝟏 𝟑
Job Scheduling with Deadlines - Example
Job 𝑖 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔
Profit 𝑔𝑖 𝟐𝟎 𝟏𝟓 𝟏𝟎 𝟕 𝟓 𝟑
Deadline 𝑑𝑖 . 𝟑 𝟏 𝟏 𝟑 𝟏 𝟑
Step 2: Find total position 𝑃 = 𝑚𝑖𝑛(𝑛, 𝑚𝑎𝑥(𝑑𝑖))
Here, 𝑃 = 𝑚𝑖𝑛(6, 3) = 𝟑
P 1 2 3
Job selected 0 0 0

Step 3: 𝑑1 = 3 : assign job 1 to position 3

P 1 2 3
Job selected 0 0 J1
Job Scheduling with Deadlines - Example
Job 𝑖 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔
Profit 𝑔𝑖 𝟐𝟎 𝟏𝟓 𝟏𝟎 𝟕 𝟓 𝟑
Deadline 𝑑𝑖 . 𝟑 𝟏 𝟏 𝟑 𝟏 𝟑

Step 4: 𝑑2 = 1 ∶ assign job 2 to position 1

P 1 2 3
Job selected J2 0 J1

Step 5: 𝑑3 = 1 : assign job 3 to position 1

But position 1 is already occupied and two jobs

can not be executed in parallel, so reject job 3
Job Scheduling with Deadlines - Example
Job 𝑖 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔
Profit 𝑔𝑖 𝟐𝟎 𝟏𝟓 𝟏𝟎 𝟕 𝟓 𝟑
Deadline 𝑑𝑖 . 𝟑 𝟏 𝟏 𝟑 𝟏 𝟑
Step 6: 𝑑4 = 3 ∶ assign job 4 to position 2 as, position 3 is not free but position 2
is free.
P 1 2 3
Job selected J2 J4 J1

Now no more free position is left so no more jobs can be scheduled.

The final optimal sequence:
Execute the job in order 2, 4, 1 with total profit value 42.
Exercises – Home Work
1. Using greedy algorithm find an optimal schedule for following jobs with 𝒏=4.
Profits: (a, b, c, d) = (20,10,40,30) &
Deadline: (d1, d2, d3, d4) = (4, 1, 1, 1)
2. Using greedy algorithm find an optimal schedule for following jobs with 𝒏=5.
Profits: (a, b, c, d, e) = (100,19,27,25,15) &
Deadline: (d1, d2, d3, d4, d5) = (2, 1, 2, 1, 3)
Job Scheduling with Deadlines - Algorithm
Algorithm: Job-Scheduling (P[1..n], D[1..n])
Arrange the job on descending order on the basis of profit
For i = 1 to n do
Set k = min (d[i],max(deadline[i]))
While k >=1 do
if timeslot[k] is empty then
timeslot[k] = job[i]
break;
end if
set k = k-1
end while
end for
Analysis
• Since, we are using two loops, one within another. Hence, the complexity of this
algorithm is O(n2)
Huffman Codes
Prefix Code
• Prefix code is used for encoding(compression) and Decoding(Decompression).
• Prefix Code: Any code that is not prefix of another code is called prefix code.
Characters Frequency Code Bits
a 45 000 135
b 13 111 39
c 12 101 36
d 16 110 48
e 9 011 27
f 5 001 15
Total bits 300
Huffman code Introduction
• Huffman invented a greedy algorithm that constructs an optimal prefix code called
a Huffman code.
• Huffman coding is a lossless data compression algorithm.
• It assigns variable-length codes to input characters.
• Lengths of the assigned codes are based on the frequencies of corresponding
characters.
• The most frequent character gets the smallest code and the least frequent
character gets the largest code.
• The variable-length codes assigned to input characters are Prefix Codes.
Huffman Codes
• In Prefix codes, the codes are assigned in such a way that the code assigned to
one character is not a prefix of code assigned to any other character.
• For example,
a = 01, b = 010 and c = 11 Not a prefix code

• This is how Huffman Coding makes sure that there is no ambiguity when
decoding the generated bit stream.
• There are mainly two major parts in Huffman Coding
1. Build a Huffman Tree from input characters.
2. Traverse the Huffman Tree and assign codes to characters.
Huffman Codes - Example
• Find the Huffman codes for the following characters.

Characters a b c d e f
Frequency (in thousand) 45 13 12 16 9 5

Step 1: Arrange the characters in the Ascending order of their frequency.

f:5 e:9 c:12 b:13 d:16 a:45

Huffman Codes - Example
Step 2:
 Extract two nodes with the minimum frequency.
 Create a new internal node with frequency equal to the sum of the two nodes
frequencies.
 Make the first extracted node as its left child and the other extracted node as its right
child.

14

f:5 e:9 c:12 b:13 d:16 a:45

Huffman Codes - Example
Step 3:
 Rearrange the tree in ascending order.
 Assign 𝟎 to the left branch and 𝟏 to the right branch.
 Repeat the process to complete the tree.

14

f:5 e:9 c:12 b:13 d:16 a:45

0 1
Huffman Codes - Example
Step 4: 25

c:12 b:13 14 d:16 a:45

0 1

f:5 e:9

14 d:16 25 a:45
0 1 0 1

f:5 e:9 c:12 b:13

Huffman Codes - Example
Step 5: 30

14 d:16 25 a:45
0 1 0 1

f:5 e:9 c:12 b:13

25 30 a:45
0 1 0 1

c:12 b:13 14 d:16

0 1
f:5 e:9
Huffman Codes - Example
Step 6:

55

0 1

25 30 a:45
0 1
0 1

c:12 b:13 14 d:16

0 1
f:5 e:9
Huffman Codes - Example
Step 7: 100
0 1

a:45 55

0 1

25 30
0 1
0 1

c:12 b:13 14 d:16

0 1
f:5 e:9
Huffman Codes - Example
Characters a b c d e f
Step 8:
Frequency (in thousand) 45 13 12 16 9 5
0 101 100 111 1101 1100

Total bits: 224

Huffman Codes - Algorithm
Algorithm: HUFFMAN (C)
Huffman (C) // C is the st of n characters and related information
{
n = [Link]
Q = priority_queue()
for i = 1 to n
n = node(C[i])
[Link](n)
end for
while [Link]() is not equal to 1
z = new node()
[Link] = x = [Link]
[Link] = y = [Link]
[Link] = [Link] + [Link]
[Link](Z)
end while
return Q // return the root of the tree
}
Analysis
• Since, we need to sort the given input symbols in ascending order of their
frequencies thus sorting takes O(nlogn) time.
• For loop takes another O(n)
• The while for executes at most O(n)
• So, total time complexity T(n) = O(nlogn)+ O(n)+ O(n)= O(nlogn)
Exercises – Home Work
• Find an optimal Huffman code for the following set of frequency.
1. a : 50, b : 20, c : 15, d : 30.
2. Frequency
Characters A B C D E F
Frequency (in thousand) 24 12 10 8 8 5

3. Frequency

Characters a b c d e f g
Frequency (in thousand) 37 28 29 13 30 17 6
Minimum Spanning Tree
Introduction to Minimum Spanning Tree (MST)
• Let 𝐺 = 𝑁, 𝐴 be a connected, undirected graph where,
1. N is the set of nodes and
2. A is the set of edges.
• Each edge has a given positive length or weight.
• A spanning tree of a graph 𝐺 is a sub-graph which is basically a tree and it
contains all the vertices of G but does not contain cycle.
• A minimum spanning tree (MST) of a weighted connected graph 𝐺 is a spanning
tree with minimum or smallest weight of edges.
• Two Algorithms for constructing minimum spanning tree are,
1. Kruskal’s Algorithm
2. Prim’s Algorithm
Spanning Tree Examples
Graph A Spanning Tree A
B C B C

D E F G D E F G

H H

Graph Spanning Tree

A
A
B C E
B C E
D F
D F
Kruskal’s Algorithm for MST – Example 1
A Step 2: Taking next Step 4: Taking next
4 5
6 min edge (B,C) min edge (A,B)
6
B 3
E B A
4
5 7 2
2
C D B E
C D 1 3
1
2
Step 3: Taking next

Step 1: Taking min

min edge (B,E) C D
edge (C,D) B E 1
3
So, we obtained a
C D 2
1 C D minimum
1 spanning tree of cost:
4 + 2 + 1 + 3 = 10
 Step:1
Kruskal’s Algorithm for MST – Example 2
Sort the edges in increasing order of their weight.

Edges Weight

1 2 {1, 2} 1
1 2 3 {2, 3} 2
{4, 5} 3
4 6 4 5 6
{6, 7} 3
{1, 4} 4
4 3 5 8 6 {2, 5} 4
{4, 7} 4
7 {3, 5) 5
4 3
{2, 4} 6
{3, 6} 6
7
{5, 7} 7
{5, 6} 8
 Step:2
Kruskal’s Algorithm for MST – Example 2
Select the minimum weight edge but no cycle.

Edges Weight

1 2 {1, 2} 1 
1 2 3 {2, 3} 2 
{4, 5} 3 
4 6 4 5 6
{6, 7} 3 
{1, 4} 4 
4 3 5 8 6 {2, 5} 4
{4, 7} 4 
7 {3, 5) 5
4 3
{2, 4} 6
{3, 6} 6
7
{5, 7} 7
{5, 6} 8
 Step:3
Kruskal’s Algorithm for MST – Example 2
The minimum spanning tree for the given graph.

Edges Weight

1 2 {1, 2} 1 
1 2 3 {2, 3} 2 
{4, 5} 3 
4
{6, 7} 3 
{1, 4} 4 
4 3 5 6 {4, 7} 4 

4 3 Total Cost = 17

7
Kruskal’s Algorithm – Example 2
Step Edges considered - Connected Components Edges Weight
{u, v}
Init. - {1} {2} {3} {4} {5} {6} {7} {1, 2} 1

1 {1,2} {1,2} (3} {4} {5} {6} {7} {2, 3} 2

2 {2,3} {1,2,3} {4} {5} {6} {7} {4, 5} 3
3 {4,5} {1,2,3} {4,5} {6} {7} {6, 7} 3
4 {6,7} {1,2,3} {4,5} {6,7} {1, 4} 4
5 {1,4} {1,2,3,4,5} {6,7} {4, 7} 4
6 {2,5} Rejected Total Cost = 17
7 {4,7} {1,2,3,4,5,6,7}
Kruskal’s Algorithm for MST
Function Kruskal(G = (N, E))//G be a weighted connected graph with N vertices
Sort E by increasing length
n ← the number of nodes in N
T ← Ø {edges of the minimum spanning tree}
Define n sets, containing a different element of set N
While(|T| < n-1 and E!= Ø)
{
Select {u, v} from E in order//e is the shortest edge not yet considered
Remove (u,v) from E
If ((u,v) does not create a cycle in T))
T = T U {(u,v)}
}
return T
Analysis
• Since, we need to sort the given input symbols in ascending order of their weight
of each edge thus sorting takes O(ElogE) or (ElogV)time.
• The while for executes at most O(E) for n vertices
• So, total time complexity T(n) = O(ElogE)+ O(E) = O(ElogE) or O(ElogV)
Exercises – Home Work
• The complexity for the Kruskal’s algorithm is in 𝜽(𝒂 𝒍𝒐𝒈 𝒏) where 𝒂 is total number of edges
and 𝒏 is the total number of nodes in the graph 𝐺.

• Write the kruskal’s Algorithm to find out Minimum Spanning Tree. Apply the same and find MST
for the graph given below.
𝟏. 𝟐.

10
3
3 A 1
F C
A 4 3 7
B 2 4
C 5
8 4
6
5 B D E F G
4 D
4
H 3 2 8
2 1 9
3
G E
3 H
Prim’s Algorithm
• In Prim's algorithm, the minimum spanning tree grows in a natural way, starting
from an arbitrary root.
• At each stage we add a new branch to the tree already constructed; the algorithm
stops when all the nodes have been reached.
• The complexity for the Prim’s algorithm is 𝜽(𝒏𝟐 ) where 𝑛 is the total number of
nodes in the graph 𝐺.
Prim’s Algorithm for MST – Example 1 Step:1 Select an arbitrary node.

Node - Set B Edges

1 2
1 2 3 1

4 6 4 5 6

4 3 5 8 6
7
4 3

7
Prim’s Algorithm for MST – Example 1 Step:2 Find an edge with minimum weight.

Node - Set B Edges

1 2
1 2 3 1 {1, 2}, {1, 4}

4 6 1, 2 {1, 4}, {2, 3} {2, 4}, {2, 5}

6 4 5
1, 2, 3 {1,4}, {2,4}, {2,5}, {3,5},
4 3 5 8 6 {3,6}
1, 2, 3, 4 {2,4} {2,5} {3,5} {3,6} {4,5}
7 {4,7}
4 3 1, 2, 3, 4, 5 {2,4} {2,5} {3,5} {3,6} {4,7}
{5,6} {5,7}
7 1, 2, 3, 4, 5, 7 {2,4} {2,5} {3,5} {3,6} {5,6}
{5,7} {6,7}
1, 2, 3, 4, 5, 6, 7
Prim’s Algorithm for MST – Example 1 Step:3

The minimum spanning tree for the given graph.

Node Edges
1 2
1 2 3 1
1, 2 {1, 2}
4
1, 2, 3 {2, 3}
1, 2, 3, 4 {1, 4}
4 3 5 6 1, 2, 3, 4, 5 {4, 5}
1, 2, 3, 4, 5, 7 {4, 7}
4 3 1, 2, 3, 4, 5, 6, 7 {6, 7}

Total Cost = 17
7
 Cost = 17

Step Edge Set B Edges Considered

Selected
{u, v}
Init. - {1} --
1 {1, 2} {1,2} {1,2} {1,4}
2 {2, 3} {1,2,3} {1,4} {2,3} {2,4} {2,5}
3 {1, 4} {1,2,3,4} {1,4} {2,4} {2,5} {3,5} {3,6}
4 {4, 5} {1,2,3,4,5} {2,4} {2,5} {3,5} {3,6} {4,5} {4,7}
5 {4, 7} {1,2,3,4,5,7} {2,4} {2,5} {3,5} {3,6} {4,7} {5,6} {5,7}
6 {6,7} {1,2,3,4,5,6,7} {2,4} {2,5} {3,5} {3,6} {5,6} {5,7} {6,7}
Prim’s Algorithm
Function Prim(G = (N, A): graph; length: A — R+): set of
edges
T ← Ø
B ← {an arbitrary member of N}
while B ≠ N do
find e = {u, v} of minimum length such that
u ∈ B and v ∈ N \ B
T ← T U {e}
B ← B U {v}
return T
Exercises – Home Work
• Write the Prim’s Algorithm to find out Minimum Spanning Tree. Apply the same
and find MST for the graph given below.

𝟏. 𝟐.
10
3
3 A 1
F C
A 4 3 7
B 2 4
C 5
8 4
5 6
4 B D D E F G
4
H 3 2 8
2 1 9
3
G E
3 H
Single Source Shortest Path – Dijkstra’s
Algorithm
Introduction
• Consider now a directed graph 𝐺 = (𝑁, 𝐴) where 𝑁 is the set of nodes and 𝐴 is the set of
directed edges of graph 𝐺.
• Each edge has a positive length.
• One of the nodes is designated as the source node.
• The problem is to determine the length of the shortest path from the source to each of the other
nodes of the graph.
• Dijkstra’s Algorithm is for finding the shortest paths between the nodes in a graph.
• For a given source node, the algorithm finds the shortest path between the source node and
every other node.
• The algorithm maintains a matrix 𝑳 which gives the length of each directed edge:

𝐿[𝑖, 𝑗] ≥ 0 if the edge (𝑖, 𝑗) ∈ 𝐴, and

𝐿[𝑖, 𝑗] = ∞ otherwise.
Dijkstra’s Algorithm - Example

1 Single source shortest path algorithm

10 50

5 30 2
100
Source node = 1
10 5 Step v C 2 3 4 5
20
Init. - {2, 3, 4, 5} 50 30 100 10
4 3
50 1 5 {2, 3, 4} 50 30 20 10

Compare cost of 1–5–4

Is there path from 1 - 5 - 432 No
Yes (20) and 1–4 (100)
Dijkstra’s Algorithm - Example

1 Single source shortest path algorithm

10 50

5 30 2
100
Source node = 1
10 5 Step v C 2 3 4 5
20
Init. - {2, 3, 4, 5} 50 30 100 10
4 3
50 1 5 {2, 3, 4} 50 30 20 10
2 4 {2, 3} 40 30 20 10

1–4–2
Compare cost of 1–4–3
Is there
Is there path
path from
from 11 -- 44 -- 532 Yes
No
(40) and
(70) and 1–3
1–2(50)
(30)
Dijkstra’s Algorithm - Example

1 Single source shortest path algorithm

10 50

5 30 2
100
Source node = 1
10 5 Step v C 2 3 4 5
20
Init. - {2, 3, 4, 5} 50 30 100 10
4 3
50 1 5 {2, 3, 4} 50 30 20 10
2 4 {2, 3} 40 30 20 10
3 3 {2} 35 30 20 10

Compare cost of
Is there path from 1 - 3 - 542 Yes
No
1–3–2 and 1–2
Exercises – Home Work
• Write Dijkstra’s Algorithm for shortest path. Use the algorithm to find the shortest
path from the following graph.

1. 2.
2
2 A B
B D
10 4 1 3 10

1 4 8 7 9 2 2
A C D E

3 2 5 8 4 6
C E
1
F G
Dijkstra’s Algorithm
Function Dijkstra(L[1 .. n, 1 .. n]): array [2..n]
array D[2.. n]
C ← {2,3,…, n}
{S = N \ C exists only implicitly}
for i ← 2 to n do
D[i] ← L[1, i]
repeat n - 2 times
v ← some element of C minimizing D[v]
C ← C \ {v} {and implicitly S ← S U {v}}
for each w ∈ C do
D[w] ← min(D[w], D[v] + L[v, w])
return D
Thank You!