Algorithm Analysis

Chapter -3
Greedy Method
 Outline
• Introduction
• Job Sequencing with Deadlines
• Optimal Merge Pattern
• Minimum Spanning Trees
• Single Source Shortest Pattern
 Introduction
• The greedy method is an algorithmic paradigm that builds up a solution piece by

piece, always choosing the next piece that offers the most immediate benefit (the

"greedy choice"), without reconsidering previous decisions.

• It is used for optimization problems where a sequence of choices leads to an optimal

solution — but it doesn’t always work unless the problem has certain properties.

• The greedy method is perhaps the most straightforward design technique, and it

can be applied to a wide variety of problems. Most of these problems have n - inputs

and require us to obtain a subset that satisfies some constraints. Any subset that

satisfies these constraints is called a feasible solution.

• Feasible solution that either maximizes or minimizes a given objective function. A

feasible solution that does this is called an optimal solution.

Introduction…
Algorithm Greedy(A, n){ Note: All dynamic programming,
// A(1:n contains the inputs
Greedy method and branch and
for i= 1 to n do
X= select(a);
bound are used to find optimal
If feasible(x) then solution for the problem
{
Solution= Solution+(x);
}
}}
 Knapsack Problem
▪ In simple terms, the Knapsack Problem means:

❑ You have a bag with limited capacity, and several items with different weights

and values.

Your task is to choose the best combination of items so that:

o The total weight does not exceed the bag’s capacity, and
o The total value (profit) is as large as possible.
❑ The Knapsack Problem is about making the best choices when you cannot take
everything.
Everyday Meaning (Real-Life Example)
Imagine you are traveling and your bag can carry 50 kg:
•A laptop is heavy but valuable
Example •Clothes are light but less valuable
•Books are heavy and of low value
You must decide what to pack to get the maximum benefit without exceeding the
weight limit.
 Knapsack Problem…
Why It Is Important
Simple Interpretation of Terms
•Resources are limited
▪ Knapsack → Bag with limited
•Choices must be optimized
capacity
•Used in:
▪ Items → Choices/options
• Project selection
▪ Weight → Cost/resource usage
• Budget allocation
▪ Value/Profit → Benefit/gain
• Network bandwidth allocation
▪ Goal → Best possible selection
• Cloud resource management
Knapsack Problem

1 2
Knapsack Problem

4
3
 Knapsack Problem…
❑ Fractional Knapsack (Greedy Method)
 Knapsack Problem…
Fractional Knapsack (Greedy Method) – Step by Step
❑ Exercise Step 1: Given Data
Step 2: Compute Profit-to-Weight Ratio (p/w)
Step 3: Sort Items (Descending p/w)
Step 4: Fill the Knapsack
Step 5: Calculate Total Profit
Final Answer (Fractional Knapsack)
Maximum profit

Since Item 1’s weight is 2, we need

only half of Item 1’s weight, because of
the capacity of the holder or bag.
 Knapsack Problem…

Item 1 : added only half the weight or partially ➔1/2

Item 2: is not added ➔ 0 (When the bag is full, no item weight can be selected )

Item 3 is added with the full weight of the complete item, not partially ➔1

Item 4 is added with the full weight of the complete item, not partially ➔1.
 Knapsack Problem…
Exercise -2
Obtain the optimal solution for the knapsack problem using the greedy method, given the
Following
M=40 capacity of Knapsack
N=3 number of objects
(𝑤1 = 20, 𝑤2 = 25, 𝑤3 = 10) represents the weights of 3 objects
(𝑝1 = 30, 𝑝2 = 40, 𝑝3 = 35) represents the profits of 3 objects
 Knapsack Problem…
Solution
Step 2 – Calculate profit-to-weight ratio
𝑝1 30
Step 1 – Understand the problem 𝑟1 = = = 1.5
𝑤1 20
We have: 𝑝2 40
𝑟2 = = = 1.6
Knapsack capacity 𝑀 = 40 𝑤2 25
𝑝3 35
Number of objects 𝑛 = 3 𝑟3 = = = 3.5
𝑤3 10
Weights: 𝑤1 = 20, 𝑤2 = 25, 𝑤3 = 10 Step 3 – Sort objects in non-increasing order of 𝑟𝑖
𝑟3 = 3.5 𝑤3 = 10𝑝3 = 35 Rank 1
Profits: 𝑝1 = 30, 𝑝2 = 40, 𝑝3 = 35 𝑟2 = 1.6 𝑤2 = 25𝑝2 = 40 Rank 2
Greedy method for knapsack problem usually means profit per 𝑟1 = 1.5 𝑤1 = 20𝑝1 = 30 Rank 3
Order: Object 3 → Object 2 → Object 1 by 𝑟𝑖 .
unit weight (not simply pick highest profit).
 Knapsack Problem
Step 4 – Fill knapsack greedily (fractional knapsack allowed)
Step 5 – Total profit
Remaining capacity = 40
Pick Object 3 (w=10, p=35) fully
Total profit = 35 + 40 + 7.5 = 82.5
Taken: 10 units weight
Remaining capacity = 40 − 10 = 30
Step 6 – Optimal solution (fractional knapsack)
Profit so far = 35
We took:
Pick Object 2 (w=25, p=40) fully All of object 3 (10 kg)
Taken: 25 units weight All of object 2 (25 kg)
5
Remaining capacity = 30 − 25 = 5 = 0.25 fraction of object 1 (5 kg)
20
Profit so far = 35 + 40 = 75 Max profit = 82.5
Pick Object 1 (w=20, p=30)
Remaining capacity = 5
5
Can’t take fully. Take fraction: of object 1.
20

5
Fraction profit = × 30 = 7.5
20

Weight taken = 5
Remaining capacity = 0
 Knapsack Problem…
❑ Exercise
 Knapsack Problem…
❑ Exercise
 Job Sequencing with Deadlines
✓ The problem is stated as below.  Given an array of jobs where every job has a deadline
and an associated profit if the job is finished before the
 There are n jobs to be processed on a machine.
deadline.
 Each job i has a deadline dj>0 and profit pi>0 .
 Every job takes a single unit of time. So the minimum
 pi is earned if the job is completed by its deadline.
deadline for any job is 1.
 The job is completed if it is processed on a machine for
a unit time.

 Only one machine is available for processing jobs.

 Only one job is processed at a time on the machine.

 Job Sequencing with Deadlines…
✓ The problem is stated as below.
 Given an array of jobs where every job has a deadline and an associated profit if
the job is finished before the deadline.

 Every job takes a single unit of time. So the minimum deadline for any job is 1.
Job Sequencing with Deadlines…
Job Sequencing with Deadlines…
Job Sequencing with Deadlines…
 Job Sequencing with Deadlines Problem
Exercise
Obtain the optimal solution for the Job sequencing problem with deadlines where n=6([Link] jobs), Profit(P1, P2, P3, P4, P5, P6)=(200,180,190,300,120,120), and
deadlines(d1,d2,d3,d4,d5,d6)=(5,3,3,2,4,2).
 Job Sequencing with Deadlines Problem
Step 7: Select Job 5
▪ Since both Job5 and Job6 have the same profit, they are considered equally desirable. However, Job6's deadline is 2,
and both slots 1 and 2 are already occupied, so Job6 cannot be scheduled.
▪ Job5 has a later deadline of 4, meaning it can be scheduled in any available slot from time 1 through time 4. But if
slots 1 and 2 are full, then the earliest available slot for Job5 would be slot 4, within its deadline.

▪ Result
o Optimal Solution of Job Sequence = 300+200+190+180+120=990
o Total Profit= {J2,J4,J3,J5,J1}
 Job Sequencing with Deadlines Problem
Exercise
For the following sequence of jobs, provide a snapshot of the execution that will achieve the
maximum profit.

Given Job J1 J2 J3 J4 J5 J6 J7
Profit 3 5 20 18 0 6 30
Deadline 1 3 4 3 2 1 2
Step 1:Sort/Arrange the jobs in decreasing order of profits
Job J7 J3 J4 J6 J2 J1 J5
Result= ????
Profit 30 20 18 6 5 3 0
Deadline 2 4 3 1 3 1 2
 Exercise
1. Obtain the optimal solution for the Job sequencing problem with deadlines where n=4([Link] jobs), Profit(P1, P2, P3, P4)=(100,10,15,27),

and deadlines(d1,d2,d3,d4)=(2,1,2,1).

2. Obtain the optimal solution for the Job sequencing problem with deadlines as given in the table.
Job Profit Deadline
J₁ 35 3
J₂ 30 4
J₃ 25 4
J₄ 20 2
J₅ 15 3
J₆ 12 1
J₇ 5 1
 Optimal Merge Pattern Using Greedy Method
▪ It relates to the merging of 2 or more sorted files into a single sorted file.
Algorithm
1. Sort the file in increasing order of length
2. Merge the first 2 file, replace them with the resulting files in the list.
3. Repeat from step 1 till list has only one file.
4. Exit Algorithm: TREE (n)

Pseudo Code 1. for i := 1 to n-1 do / / declare new node

▪ Take the list of file sizes (or merge costs). 2. [Link]:= least (list) [Link]:= least (list)
▪ Repeat until only one file remains:
3. node. Weight:=(([Link]).weight) + (([Link]).weight) insert (list, node);
Pick the two smallest files.
4. return least (list);
Merge them (cost = sum of their sizes).
Insert the new merged file size back into the list.

▪ Total cost = sum of all merge costs in the process.

 Optimal Merge Pattern Using Greedy Method
Example
Merge files with sizes: 5, 10, 20, 30, 30
Step-by-step merges:
▪ Merge 5 & 10 → cost 15, new list: [15, 20, 30, 30]
Total cost so far: 15
• Merge 15 & 20 → cost 35, new list: [35, 30, 30]
Total: 15 + 35 = 50
• Merge 30 & 30 → cost 60, new list: [35, 60]
Total: 50 + 60 = 110
• Merge 35 & 60 → cost 95
Total: 110 + 95 = 205
 Optimal Merge Pattern Using Greedy Method
Problem Statement: Step 2: Apply Greedy Algorithm (always merge the smallest two)

We have files with sizes: 5, 3, 3, 7, 9, 8, 6, 4 Iteration 1: Iteration 5:

Smallest two: 3 and 3 Smallest two: 9 and 9
We need to merge them optimally (minimum total merge cost). Merge cost = 3 + 3 = 6 Merge cost = 9 + 9 = 18
New list: [4, 5, 6, 6, 7, 8, 9] New list: [12, 15, 18]
Total cost so far: 6 Total cost: 42 + 18 = 60
Step 1: Sort the initial list
Iteration 2: Iteration 6:
▪ Original: [5, 3, 3, 7, 9, 8, 6, 4] Smallest two: 4 and 5 Smallest two: 12 and 15
Merge cost = 4 + 5 = 9 Merge cost = 12 + 15 = 27
▪ Sorted: [3, 3, 4, 5, 6, 7, 8, 9] New list: [6, 6, 7, 8, 9, 9] New list: [18, 27]
Total cost: 6 + 9 = 15 Total cost: 60 + 27 = 87
Iteration 3: Iteration 7:
Smallest two: 6 and 6 Smallest two: 18 and 27
Merge cost = 6 + 6 = 12 Merge cost = 18 + 27 = 45
New list: [7, 8, 9, 9, 12] New list: [45]
Total cost: 15 + 12 = 27 Total cost: 87 + 45 = 132
Iteration 4:
Smallest two: 7 and 8 Total comparison = 132
Merge cost = 7 + 8 = 15
New list: [9, 9, 12, 15]
Total cost: 27 + 15 = 42
Optimal Merge Pattern Using Greedy Method and Merge Tree
 Exercises
1. Merge the following file sizes using the optimal merge pattern (greedy method) and find the total minimum cost:
Files: 12, 8, 15, 6, 10

▪ Draw the merge tree and show each step.

2. Given file sizes: 25, 30, 20, 15, 10, 5

▪ Apply the greedy algorithm to find the optimal merge order.

▪ What is the total merge cost?
▪ Show the merge tree.

3. Challenge:
Files: 50, 20, 10, 15, 25, 40, 5

• Find optimal merge pattern.

• How many merges are needed in total?

• What is the final total cost?

• Would the cost change if we started merging the largest files first? Justify.
 Minimum Spanning Trees(MST)
▪ Tree: A connected graph without cycles. A cycle is a path that starts and ends at the same vertex.

▪ A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of

edges.

o A spanning tree does not have cycles, and it cannot be disconnected.

o we conclude that every connected and undirected Graph G has at least one spanning tree.

▪ Let G=(V, E) be an undirected connected graph . A sub graph t=(V, E’) of G is a spanning tree of G iff t is a tree.

A minimal sub graph is one with the fewest number of edges.

Spanning tree is sub-graph of a graph and it will take all vertices of graph G.

Any connected graph with n-vertices must have at least n-1 edges and all are tree.

The cost of spanning tree is the cost of sum of the edges in that tree.

To find spanning tree the G must be connected.

 Minimum Spanning Trees(MST)
❑ A Minimum Spanning Tree of a connected, undirected graph is a tree that:

• Connects all vertices

• Has no cycles
• Minimizes total edge weight
• ensures all nodes are connected at minimal total edge weight, with no cycles.
❑ A Spanning Tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices
of the graph.
❑ Minimum Spanning Tree (MST) : A Minimum Spanning Tree is the spanning tree with the smallest total weight or cost.
❑ The Minimum Spanning Tree Problem: This is the problem of finding a spanning tree for a given weighted connected
graph with the minimum possible total cost.
❑ Algorithms to solve the MST problem:
• Prim’s Algorithm
• Kruskal’s Algorithm
 Minimum Spanning Trees(MST)
▪ A Minimum Spanning Tree (MST) – or minimum weight spanning tree – is a subset of the edges
of a connected, edge-weighted, undirected graph that connects all the vertices without any cycles
and with the minimum possible total edge weight.

▪ Examples of Minimum Spanning Tree Applications:

o Telecommunications Networks – Designing cost-effective fiber-optic cable layouts.

o Computer Networks – Connecting routers/switches with minimal wiring cost.
o Transportation Networks – Planning roads or rail lines to link cities efficiently.
o Water Supply Networks – Optimizing pipeline connections to reduce construction cost.
o Electrical Grids – Connecting power stations to substations with minimum cable length.

In each case, the MST gives the lowest-cost set of connections that links all required points
 Minimum Spanning Trees(MST)
▪ Example
List a Possible Spanning tree of the following
 Minimum Spanning Trees(MST)
▪ Example
List a Possible Spanning tree of the following
 Minimum Spanning Trees(MST)
▪ Example
List a Possible Spanning tree of the following
Prim’s Algorithm
 Prim’s Algorithm

Key Algorithms

[Link]’s Algorithm

▪ Start from any vertex

▪ Grow a tree by adding the smallest edge connected to the tree

Prim’s Algorithm Implementation
 Prim’s Algorithm Implementation

Step-6
 Exercise
Apply Prim’s Algorithm
Graph Data
[Link] the weighted graph with vertices P1–P6 and edges labeled with distances.
Vertices: P1, P2, P3, P4, P5, P6
[Link] Prim’s Algorithm starting from P1.
Edges with distances (in meters):
[Link] each step:
▪ P1 – P2 = 150 [Link] vertices in MST
▪ P1 – P3 = 200 [Link] edges (connecting MST to outside)
▪ P1 – P4 = 100 [Link] edge (minimum weight)
▪ P2 – P3 = 120 [Link] MST
▪ P2 – P5 = 180 [Link] the final chosen paths and the total minimized distance.
▪ P3 – P4 = 80 [Link] the final MST (connection map of PoliStops).
▪ P3 – P5 = 90
➢ Your task is to choose paths so that all PoliStops are connected, and the total
▪ P4 – P5 = 130
walking distance is minimized.
▪ P4 – P6 = 160
▪ P5 – P6 = 110
 Kruskal’s Algorithm
▪ It is faster than Prim’s algorithm.
▪ It generates a minimum cost spanning tree for every connected undirected graph.
▪ It says that always select the minimum cost edges.
▪ Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted
graph.
▪ The main target of the algorithm is to find a subset of edges by using which we can
traverse every vertex of the graph.
▪ It follows a greedy approach, which finds an optimum solution at every stage instead of
focusing on a total optimum.
 Kruskal’s Algorithm Examples
Here is the list of applications where Kruskal's algorithm is commonly used:

[Link] cables – such as fiber-optic or electrical cables

[Link] network design – connecting broadcast stations efficiently
[Link] operations – planning routes to minimize travel costs
[Link] networks – connecting computers in a local network with minimal cabling
[Link] or gas pipeline networks – designing cost-effective distribution systems
[Link] grid design – connecting power stations and substations
[Link]-link clustering – used in hierarchical clustering in data analysis
Kruskal’s Algorithm
 Kruskal’s Algorithm

[Link]’s Algorithm

[Link] edges by weight

[Link] the smallest edge that doesn’t form a cycle (use Union-Find)
 Example
Construct a minimum spanning tree of the given graph
Using Kruskal’s Algorithm
Given
[Link] construct the Minimum Spanning Tree using Kruskal’s Algorithm, first draw
all the vertices of the graph.
[Link] these vertices by adding edges in order of increasing weight, ensuring
that no cycle is formed at any step.

Step-1 Step-2 Step-3 Step-4 Step-5

 Example
Construct a minimum spanning tree of the given graph
Step-6 Using Kruskal’s Algorithm

➢ Remember: the edge 7 to 4 and edge 7 to 5 form a cycle, so reject it and move to the
next minimum weight.

Weight of the MST:

Sum of all edge weights:
Weight of the MST:
10 + 25 + 22 + 12 + 16 + 14 = 99 units
Step-7

▪ Sum of all edge weights: 10 + 25 + 22 + 12 + 16 + 14 = 99 units

▪ Sequence: 1,6,5,4,3,2,7
 Exercise

Use Kruskal's Algorithm for the following:

Given the graph above, what is its Minimum Spanning Tree?
Also, what is the minimum sum of distances of all edges that connect all the vertices?
 Summary of Both Algorithm

▪ Kruskal's algorithm is an algorithm that produces a Minimum Spanning Tree (MST) of a given
connected, weighted graph.
▪ It is a greedy MST algorithm.
❑ The main difference from Prim's algorithm is that :
▪ Prim's algorithm grows a single tree from a starting vertex.
▪ In contrast, Kruskal's algorithm grows a collection of trees (a forest) and gradually merges them
until a single spanning tree remains.
 Single Source Shortest Pattern (SSSP)

▪ In graph theory, the shortest path problem is the problem of finding a

path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent
edges is minimized. Given a directed graph, and a single node called the source.
▪ For each of the remaining nodes, find a shortest path connected to the source.
▪ It is a classic problem in a graph. Find the shortest path in a weighted graph.
 Dijkstra's Algorithm
✓Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G =(V, E)
for the case in which all edge weights are non-negative. We assume that w(u, v) ≥ 0 for each edge (u,v) ∈ E.
✓It finds the shortest paths from some initial vertex, say vs to all the other vertices one-by- one.
✓The essential feature of Dijkstra's algorithm is the order in which the paths are determined:
✓The paths are discovered in the order of their weighted lengths, starting with the shortest,
proceeding to the longest.
✓It is used to find shortest path between nodes in a graph. It may be work for negative edges which show any
business problem. It may also work for directed or undirected graphs.
✓It is used to find shortest path between nodes in a graphs
 Dijkstra's Algorithm
Steps
[Link] every node a tentative distance.

[Link] initial node as current and mark all other nodes as unvisited.

[Link] current node, consider all unvisited nodes and calculate tentative distance. Compare
current distance with calculated distance and assign the small value.

[Link] all the neighbors are considered of the current node, mark it visited, ‘visited node’ is
never checked again

[Link] the destination node is marked visited, stop

[Link]
Dijkstra's Algorithm
 Dijkstra's Algorithm

▪ Given that node A is the source node, what are the distances of the shortest paths
from the source node to all other nodes using Dijkstra’s shortest path algorithm.

Step -01
The source node has a distance of 0.

1. Mark all nodes as Unvisited

2. Assign to all nodes a tentative distance value

 Dijkstra's Algorithm…

Step -02
➢ If we have found a new shorter distance to one of the unvisited nodes. So B and D are unvisited nodes, and
the current distance is infinity. So we can update the distance from A to B to 2. Store A as a previous node in
the table and A to D to 8.

3. For the Current node, calculate the distance

to all unvisited neighbors
3.1. Update the shortest distance if the new
distance is shorter than the old distance.
 Dijkstra's Algorithm…
Step -04
Step -03 ➢ 4. Mark the current node as visited
[Link] the new current node from the
unvisited nodes with the minimal distance.
➢This means B is the current node
 Dijkstra's Algorithm…
Step -05

➢ For the Current node, calculate the distance to all unvisited neighbors
▪ Update the shortest distance if the new distance is shorter than the old distance.

➢ If we have found a new shorter distance to one of the

unvisited nodes. So B and D are unvisited nodes, and the
current distance is 8. So we can update the distance from
B to D to 7. Store B as a previous node in the table and B
to E to 7, which is the shortest distance.

Note: Update the value of the D to 7. Since 7 < 8 and

it is the shortest distance.
 Dijkstra's Algorithm…
Step -05 ➢ 4. Mark the current node as visited Step -06
Choose the new current node from the unvisited nodes
with the minimal distance.
➢This means D is the current node
 Dijkstra's Algorithm…
Step -07

➢ For the Current node, calculate the distance to all unvisited neighbors
▪ Update the shortest distance if the new distance is shorter than the old distance.

➢ If we have found a new shorter distance to one of the

unvisited nodes. So D and F are unvisited nodes, and the
current distance is Infinitive. So we can update the
distance from D to F to 9. Store D as a previous node in
the table and D to F to 7, which is the shortest distance.

▪ Update the value of the D to F. (From infinite to 9) that is

the shortest distance.
▪ The value of D to E is 10, but the shortest distance is
already occupied. Hence, no need to update it b/c 8<10.
 Dijkstra's Algorithm…
Step -07
➢ Mark the current node as visited
 Dijkstra's Algorithm…

Step -08 Choose the new current node from the unvisited nodes with the minimal distance.
➢This means E is the current node
 Dijkstra's Algorithm…

Step -09
➢ For the Current node, calculate the distance to all unvisited neighbors
▪ Update the shortest distance if the new distance is shorter than the old distance.
 Dijkstra's Algorithm…

Step -09 Choose the new current node from the unvisited nodes with the minimal distance.
➢This means F is the current node
 Dijkstra's Algorithm…

Step -09 Choose the new current node from the unvisited nodes with the minimal distance.
➢This means F is the current node
 Dijkstra's Algorithm…

Step -09 Choose the new current node from the unvisited nodes with the minimal distance.
➢This means C is the current node
 Dijkstra's Algorithm…

Step -09
➢There is no unvisited node of neighbor of C
 Dijkstra's Algorithm…

Step -09
➢The shortest path from A to C is :
A➔B➔D➔F➔C
 Exercise

Find the shortest path from vertex A to every other vertex Using Dijkstra's Algorithm…
 Floydwrashall

1. Mark all nodes as unvisited

2. Assign to all nodes a tentative distance value
3. For the current node, calculate the distance to all unvisited neighbors.
3.1. Update the shortest distance if the distance is shorter than the old distance.
4. Mark the current node as visited.
5. Choose a new current node from unvisited nodes with minimal distance.
 Floydwrashall

Floyd Warshall: The advantage of this algorithm is used to handle negative weighted graphs.
✓The all pairs shortest path problem is to determine a matrix A such that A (i, j) is the
length of a shortest path from i to j.
✓The matrix A may be obtained by solving n single source problems using the procedure
shortest_paths.
✓Another alternate solution will require a weaker restriction on edge costs than required by
shortest _paths.
✓It uses negative weights without negative-weight cycles. The general formula:
 Floydwrashall

▪ The main idea behind the Floyd-Warshall algorithm is to gradually build up all
intermediate routes between nodes i and j to find the optimal path.
▪ The Floyd-Warshall algorithm is a dynamic programming algorithm (not purely greedy) used to find
the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and
undirected graphs, and can handle negative weights
l solution from i to j is simply the distance in the adjacency matrix.
𝑑𝑝 𝑘 𝑖 𝑗 = 𝑚 𝑖 𝑗 𝑖𝑓 𝑘 = 0
Find the shortest path of all edge using Floydwrashall

Initial distance matrix 𝑫 𝟎 ( direct distances, ∞ means no direct edge):

Step 1: The diagonal of the matrix is set to 0, and the rest is put according to the adjacency.

Step 2: Copy Row 1 and Column 1 from D(0).

Use formula: AK [i, j] =min {Ak-1[i, j], Ak-1[i, k] +Ak-1[k, j]}

 Find the shortest path of all edge using Floydwrashall
Step 2: Copy Row 1 and Column 1 from D(0). Step 3: Copy Row 2 and Column 2 from D(1).

Step 4: Copy Row 3 and Column 3 from D(2). Step 5: Copy Row 4 and Column 4 from D(3).

Step 6: Copy Row 5 and Column 5 from D(4).

Use formula: AK [i, j] =min {Ak-1[i, j], Ak-1[i, k] +Ak-1[k, j]}

 Example: 2 Exercise
0 3  7
0 3  7
8 0 2 15
8 0 2 
A 0= 5 8 0 1
5  0 1 A1=
2 5  0
2   0

0 3 5 7 0 3 5 6 0 3 5 6
8 0 2 15 7 0 2 3 5 0 2 3
A2= A3= A4=
5 8 0 1 5 8 0 1 3 6 0 1
2 5 7 0 2 5 7 0 2 7 5 0

Use formula: AK [i, j] =min {Ak-1[i, j], Ak-1[i, k] +Ak-1[k, j]}

74
Example: 2 Cont’d
A0[2, 3] A0[2, 1]+A0[1, 3]
A(0)=
1 2 3 4 5 A(1)=

1 0 3 8  − 4 0 3 8  − 4
  7 
2  0  1 7 
  0  1 
  4 0   
4 0     
3   2 5 −5 0 − 2
 2  −5 0  
4 
   6 0 

 0 
5    6 
1st row and 1st column are the same with A(0) and A(1)
A(3)=
75
0 3 8 4 − 4
0 3 8 4 − 4  0  1 7 
 0  1 7   
A(2)=    4 0 5 11 
 4 0 5 11   

−5

− 2 2 −1 −5 0 − 2
2 5 0
 
   6 0 

   6 0 


Note: if A(1) there is ∞ signKin the 1st row and k-1 same with A(0) for all rows.
col then thek-1value is thek-1
Use formula: A [i, j] =min {A [i, j], A [i, k] +A [k, j]}
 Cont’d

0 3 −1 4 − 4 0 1 −3 2 − 4
3  3 0 −4 1 
− 1
 0 −4 1 − 1 
7 4 0 5 3  A(5)= 7 4 0 5 3 
A(4)=    
2 −1 −5 0 − 2 2 −1 −5 0 − 2

8 5 1 6 0 
 
8 5 1 6 0 

76

1-Jan-26
 Cont’d
Algorithm:

For (k=1, k≤n, k++){ Time efficiency: Θ(n3)

For (i=1; i≤ n, i++){

For (j=1, j≤n, j++) {

a[i, j]=min(a[i ,j]+a[i, k]+a[k, j])}}}

The time complexity is O (n3).

Note: The advantage of this algorithm is used to handle the negative weighted graphs

77
THANK YOU