4.2 All Pairs Shortest Path (Floyd-Warshall) - Dynamic Programming

Summary

This video tutorial addresses the All Pairs Shortest Path problem, proposing a dynamic programming solution. It contrasts Dijkstra's algorithm, which finds single-source shortest paths, with the presented approach, which computes the shortest paths between every pair of vertices. The video demonstrates how to construct a distance matrix and iteratively improve it by considering intermediate vertices. The formula for updating the matrix is explained, and sample code is provided to implement the solution, culminating in a time complexity of O(n^3).

Takeaways

• 😀 The problem discussed is the All Pairs Shortest Paths, which involves finding the shortest path between every pair of vertices in a graph.
• 🔍 The video explains that while Dijkstra's algorithm can solve the single-source shortest path problem, applying it to all vertices would result in an O(n^3) time complexity.
• 🛠️ Dynamic programming is introduced as a method to solve the All Pairs Shortest Paths problem more efficiently by breaking it down into smaller subproblems.
• 📊 The concept of a distance matrix is used to represent the shortest paths, where each cell represents the shortest distance between two vertices, either directly or via an intermediate vertex.
• 🔄 The video demonstrates how to iteratively improve the distance matrix by considering intermediate vertices, starting from the first vertex and continuing to the last.
• 💡 The formula for updating the distance matrix is presented, which involves taking the minimum of the existing distance or the sum of the distances through the intermediate vertex.
• 💻 The script includes a step-by-step explanation of how to implement the dynamic programming solution in code, emphasizing the nested loops required to calculate the shortest paths.
• 📝 The code snippet provided in the video script is a practical example of how to apply the dynamic programming approach to solve the All Pairs Shortest Paths problem programmatically.
• ⏱️ The time complexity of the dynamic programming solution for the All Pairs Shortest Paths problem is O(n^3), which is more efficient than applying Dijkstra's algorithm to each vertex individually.
• 🔑 The key takeaway is that dynamic programming offers a powerful approach to solving optimization problems by building up solutions to complex problems from solutions to simpler subproblems.

Q & A

What is the problem discussed in the video?

The problem discussed in the video is the All Pairs Shortest Paths problem, which involves finding the shortest path between every pair of vertices in a graph.

How does the All Pairs Shortest Paths problem differ from the Single Source Shortest Path problem?

The All Pairs Shortest Paths problem differs from the Single Source Shortest Path problem in that it aims to find the shortest paths between every pair of vertices, whereas the Single Source Shortest Path problem focuses on finding the shortest path from one source vertex to all other vertices.

What is the time complexity of solving the All Pairs Shortest Paths problem using Dijkstra's algorithm on all vertices?

If Dijkstra's algorithm is run on all vertices one by one, the time complexity for solving the All Pairs Shortest Paths problem would be O(n^3), where n is the number of vertices.

How does the video suggest solving the All Pairs Shortest Paths problem using dynamic programming?

The video suggests solving the problem by taking a sequence of decisions at each stage, starting with selecting a middle vertex and checking for shorter paths through that vertex, iteratively updating the distance matrix for each intermediate vertex.

What is the role of the distance matrix in solving the All Pairs Shortest Paths problem?

The distance matrix plays a crucial role in solving the problem by storing the shortest path distances between vertices. It is iteratively updated with the shortest paths found using dynamic programming.

How does the video explain the process of updating the distance matrix?

The video explains the process by taking the minimum of the direct path and the path that includes an intermediate vertex, updating the matrix values accordingly to reflect the shortest paths found.

What is the formula used in the video to update the distance matrix for an intermediate vertex?

The formula used to update the distance matrix for an intermediate vertex is min(a[i][j], a[i][k] + a[k][j]), where 'a' represents the distance matrix, 'i' and 'j' are the vertices, and 'k' is the intermediate vertex.

How many matrices are generated in total for the dynamic programming approach shown in the video?

In the video, a total of n-1 matrices are generated, where n is the number of vertices in the graph, with each matrix representing the shortest paths considering an additional intermediate vertex.

What is the time complexity of the dynamic programming approach for the All Pairs Shortest Paths problem as described in the video?

The time complexity of the dynamic programming approach described in the video is O(n^3), due to the three nested loops required to generate all the matrices.

Can you provide an example of how the video demonstrates the application of the dynamic programming approach?

The video demonstrates the approach by first showing the working with a small example, then deriving the formula used for updating the distance matrix, and finally presenting the code that implements the algorithm with a time complexity of O(n^3).

Outlines

00:00

🔍 Understanding All-Pairs Shortest Paths Problem

The video introduces the all-pairs shortest paths problem, explaining that the goal is to find the shortest path between every pair of vertices in a graph. The narrator discusses how a single-source shortest path algorithm like Dijkstra's can be applied for each vertex, but this leads to an inefficient time complexity of O(n³) when used repeatedly. To solve this problem more efficiently, dynamic programming is introduced, which involves making decisions at each stage by checking possible intermediate vertices that could lead to a shorter path. The problem setup, including how to check for paths through intermediate vertices, is thoroughly explained with an introduction to distance matrices that represent edge weights between vertices.

05:02

🧮 Matrix Representation and Dynamic Programming Approach

The dynamic programming solution to the problem is detailed, focusing on how to iteratively improve a distance matrix by checking for paths through intermediate vertices. The matrix is initialized with direct edge weights between vertices, with missing edges represented as infinity. The narrator demonstrates how to update matrix values by considering paths through intermediate vertices and explains the process of checking if these intermediate paths provide a shorter distance. An example with specific values shows how to calculate the updated matrix and how the presence of an intermediate vertex can shorten a path between two vertices.

10:03

📝 Constructing the Dynamic Programming Formula

The formula for updating the matrix using dynamic programming is introduced. This formula calculates the shortest path between two vertices by comparing the existing path and the new path that includes an intermediate vertex. The narrator breaks down how each step of the process works, explaining how the matrices evolve from one step to the next. The explanation also covers how the code is structured with nested loops to generate the intermediate matrices, where each loop represents one of the vertices as the intermediate one. The formula's role in driving these updates is clearly illustrated.

Keywords

💡All Pair Shortest Paths

The 'All Pair Shortest Paths' is a problem in graph theory where the objective is to find the shortest paths between every pair of vertices within a graph. This is a central concept in the video, as it sets the stage for the discussion on algorithms and methods to solve this problem. The video aims to solve this problem using a dynamic programming approach, which is a significant departure from the more commonly used Dijkstra's algorithm that finds the shortest path from a single source vertex.

💡Dynamic Programming

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. In the context of the video, it is used to tackle the All Pair Shortest Paths problem more efficiently than the straightforward application of Dijkstra's algorithm. The video explains how dynamic programming can be applied to iteratively improve the solution by considering intermediate vertices, leading to a solution with a time complexity of O(n^3).

💡Dijkstra's Algorithm

Dijkstra's Algorithm is a well-known algorithm for finding the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. The video mentions Dijkstra's Algorithm as a comparison to the dynamic programming approach. It points out that while Dijkstra's algorithm is efficient for single-source shortest paths, applying it to all vertices would result in a higher time complexity of O(n^3), which is less efficient than the proposed dynamic programming solution.

💡Intermediate Vertex

In the video, an 'Intermediate Vertex' refers to a vertex used to potentially shorten the path between two other vertices. The dynamic programming approach involves considering different intermediate vertices to find if they can provide a shorter path between two vertices. This concept is crucial for understanding how the dynamic programming solution iteratively improves the path lengths by exploring different intermediate vertices.

💡Matrix

The term 'Matrix' in the video refers to a distance matrix that stores the shortest path distances between pairs of vertices. The matrix is updated iteratively as the algorithm considers different intermediate vertices. The video explains how the matrix is initially populated with direct edge weights and then how it is updated to reflect the shortest paths found using dynamic programming.

💡Infinity

In the context of the video, 'Infinity' is used to represent the absence of a direct path between two vertices in the initial distance matrix. It is a placeholder value that helps in determining whether including an intermediate vertex can provide a shorter path. The video explains how infinity is used in the matrix to indicate that no direct connection exists, and it is replaced with the actual path length once a shorter path is found.

💡Time Complexity

Time Complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input. The video discusses the time complexity of solving the All Pair Shortest Paths problem using different approaches, comparing the O(n^3) time complexity of the dynamic programming solution to the O(n^2) time complexity of running Dijkstra's algorithm from each vertex.

💡Floyd-Warshall Algorithm

Although not explicitly named in the script, the approach described in the video is indicative of the Floyd-Warshall Algorithm, a dynamic programming algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). The algorithm is alluded to through the iterative process of updating the distance matrix using intermediate vertices.

💡Self Loop

A 'Self Loop' in graph theory refers to an edge that connects a vertex to itself. The video mentions that self-loops are represented as 0 in the distance matrix, indicating that there is no cost associated with moving from a vertex to itself. This is a standard representation in algorithms that deal with graph traversal.

💡Nested For-Loops

Nested For-Loops are a programming construct where a loop is used inside another loop. In the video, nested for-loops are used in the code implementation of the dynamic programming solution to iterate over all possible pairs of vertices and all possible intermediate vertices. This is a direct reflection of the algorithm's need to consider all combinations of vertices and intermediate points to find the shortest paths.

Highlights

Introduction to the All Pairs Shortest Paths problem.

Explaining the difference between All Pairs Shortest Paths and Single Source Shortest Path algorithms like Dijkstra's.

Mention of the time complexity of using Dijkstra's algorithm for all vertices.

Introduction to solving the problem using dynamic programming.

Explanation of decision-making in dynamic programming for finding shortest paths.

Description of the initial distance matrix setup.

Process of updating the distance matrix by considering intermediate vertices.

Explanation of how to handle the absence of edges and self-loops in the matrix.

Demonstration of updating the matrix for intermediate vertex 1.

Discussion on the iterative process of updating matrices for each intermediate vertex.

Presentation of the final distance matrix after considering all intermediate vertices.

Derivation of the dynamic programming formula for updating the matrix.

Explanation of the formula used to determine the shortest path through an intermediate vertex.

Code walkthrough for implementing the All Pairs Shortest Paths problem solution.

Description of the nested for-loops used in the code for generating matrices.

Conclusion on the time complexity of the implemented solution, which is O(n^3).

Transcripts

the problem is all pair shortest paths

in this video we will look at a problem

and we will solve it using dynamic

programming approach then I will show

you what is the formula how we get the

formula for dynamic programming and also

I will show you a piece of code for

solving a problem so let us start what

the problem is the the problem is to

find a shortest path between every pair

of vertices let us say the starting

vertex is 1 then I should find out our

path from 1 to 2 1 2 3 and 1 2 4 then

again selecting 2 as a starting vertex I

should find a shortest path to vertex 1

& 3 & 4 similarly from 3 I should find a

shortest path from 1 2 & 4 from 4 to 1 &

2 & 3 so this looks similar to single

source shortest path that is Dijkstra

algorithm but Dijkstra's algorithm will

find out a shortest path from one of the

source vertex and this vertex order of n

square time if I run Dijkstra algorithm

on all the vertices one by one that is

all n vertices then I can get the result

yes I can use the extra algorithm for

solving this problem for all n vertices

one by one and for each vertex it will

take n square time and and the time will

be order of n cube so this problem can

be solved using reading method also but

let us now see how we can apply dynamic

programming for solving this problem now

how the problem can be solved using

dynamic programming dynamic programming

says that the problem should be solved

by taking sequence of decision in each

stage we will take a decision so what

decision I have to take let us see see

if I have to find a shortest path

between vertex 1 to 2 so there will be a

direct edge path from 1 to 2 also like

here you can see or maybe there is a

shorter path going via vertex 3 or it

may be going where a vertex 4 so in this

way I have to check or decide whether a

shorter part is going by or some other

word

so I'll start selecting the middle

vertex as vertex one so I'll find out

first whether there is a shorter path

between all the pair of vertices going

by a vertex 1 then Y a vertex 2 and so

on so this is how we can take decision

or sequence of decisions so how this can

be done this can be done by just

preparing mattis's explaining this a

distance matrix see here from 1 to 1 or

2 2 to 4 4 to 4 there is no exit that's

why all these are zeros means there is

no X possible that loops are not

possible then there is an edge going

from 1 to 2 so 1 to 2 the cost of an

edge is 3 and similarly there is an edge

going from 2 to 3 so the cost of an edge

is 2 so 3 2 2 3 the cost of an edge is 2

if there is no edge from 3 to 2 there is

no edge you see so 3 - 2 is kept as

infinity in case of absence of any edge

we will take it as infinity otherwise

for self loop we will show them as 0 now

how we will solve this is we will solve

it by preparing matrixes so let us see

how madison's can be prepared let us

prepare a matrix for 1 a 1 see this was

a 0 original matrix now here I am going

to consider the intermediate vertex has

vertex 1 so is there any better shorter

path going where vertex 1 so when I say

vertex 1 then all the paths that belongs

to vertex 1 will remain unchanged so I

should not calculate them directly it

can take them here so those values are 0

3 infinity and 7 and these are 8 5 & 2

so first row and first column already I

have taken as it is then what about the

diagonals there are no cells loops or

and fill those diagonals also no

remaining values I have to find out what

are those first let us check this one

that is 2 2 3 so how do you get this

value how to check whether there is a

shorter part of our vertex 1 or not so 2

2 3 I will take a 0 of 2 2 3 so what is

there in this matrix 2 2 3 so 2 2 3 is a

2

and a zero of not in between I should

include vertex 1 so 2 to 1 and 1 to 3

from those matters from that matrix 2 to

1 and 1 to 3 2 2 1 is how much 8 1 2 3

is infinity so this is 8 plus infinity

this is infinity only this is less so

there is no better path where vertex 1

so let it be to only now I have to find

out next 1 that is 2 2 4 so a 0 of 2 to

4 what is the value there to 2 for 2 to

4 is infinity this is infinity now I

should include vertex 1 in between as an

intermediate vertex so a 0 of 2 to 1

plus a 0 of 1 to 4 so from that matrix

find out 2 to 1 and 1 to 4 to 2 1 is how

much 8 then 1 2 4 is 7 15 so this is 8

plus 7 this is 15 so this one is a

smaller than infinity so update this

part to 15 so this means that from 2 to

4 2 to 4 there is no direct edge path

but 2 to 1 then 1 to 4 and that is 8

plus 7 15 there is a part going where

vertex 1 that's what we got dancing here

now I have to fill up these values right

so that is 3 to 2 so I will find out a 0

of 3 2 in between I should add 1 3 1 1 2

so 3 to 2 is how much trying to 2 is

infinity 3 1 5 plus 1 2 is a 3 so you

can check there here infinite is greater

so this value is smaller that is 8 so we

got a smaller value 8

in the same way I should fill up all

these values so I have prepared this

matrix which is going via vertex 1 now I

will prepare a matrix which is going by

a vertex

- so I should generate this matrix from

this Mattox so what I am taking a second

matrix - as a intermediate vertex then

second row and second column remains as

it is so I will take the second row

second column as it is 8 0 2 and 15

second column is 3 0 8 8 3 0 8 8 and the

diagonals remains 0 only now I have to

find out few values here what are those

first one is 1 2 3 let me find out from

this matrix a 1 of 1 comma 3 a 1 of 1

comma 3 here 1 comma 3 is what infinity

then in between I should include vertex

2 so a1 off in between 1 2 3 so 1 2 2

plus a 1 of 2 2 3 check this 1 1 to 2 is

to 3 and 2 to 3 is 2 so this is 3 plus 2

that is 5 and this is smaller update

this now this was infinity now we got a

pathway our textu in between 1 & 3 1 2 3

there is a path going to 2 then 3 so 3 +

2 5

we got a path here so that's it now I

should give this value 1 to 4 so a1 of 1

comma 4 is how much here 7 then in

between I should introduce what x2 so 1

- 2 plus a 1 of 2 2 4 so 1 to 2 is how

much 3 plus 2 to 4 is how much 15 so

this 18 but this 7 which is already

there which is better so take this 7 now

in the same way I should fill up all

these values already I have prepared

this what extra as a intermediate vertex

now I have to find out what X 3 has

intermediate

and generate the maddox when I say three

as an intermediate vertex then the third

row and third column remains a city so

this is five eight zero one and this is

five two zero seven and the diagonals

are 0 a 2 of 1 comma 2 and in between I

should take intermediate vertex as 3

then a 2 of 3 comma 2 so 1 2 2 is there

so in between 3 is there and 3 1 2 3 and

3 2 - sort of this which one is smaller

1 2 2 1 2 2 is how much 3 there and 1 2

3 is how much 1 2 3 is 5 plus 3 2 2 3 2

2 is 8 5 plus 8 13 this 3 itself is

smaller so take 3 only in the same way I

can find out all these values by taking

three years intermediate vertex now hope

you have understood how I am getting the

values so I will prepare all the

mattresses so here are the four

mattresses the finally the fourth vertex

when I considered I got a shortest path

between all pair of vertices so we have

taken sequence of decision in each stage

we were getting a matrix here the table

is like a matrix here and finally these

are the shortest paths between every

pair of vertices what was the formula I

was using I will prepare the formula

getting the value of any matrix let us

say 4 is the intermediate vertex or 2 is

the intermediate vertex so when I was

selecting one of the vertex of the

intermediate vertex then how I was

getting the values here I was getting

from the previous matrix for 4 I was

getting from three for three I got from

two so how the formula can be framed so

now I will show you the formula for

getting a of I comma J of any

intermediate vertex any value from any

intermediate vertex I was taking minimum

of a of I comma J from which matrix

previous Mattox that is K minus 1 if I

am generating care to

than I was taking rally from K minus-1

either this or a of K minus one I to K

what XK intermediate vertex SK plus a of

K minus 1 then k 2 J so here you can see

that case introduced in between and

addition is done so either this one is a

smaller or this one is smaller out of

this whichever one is a smaller I was

getting that one and I was following the

same formula for generating all the

mattresses I have shown only few terms

that is sufficient for understanding the

approach and how the formula is use see

I have first shown you the working then

I have generated the formula right and

so following the formula I have deduced

the formula that's it now let me show

you how the code looks like if I am

writing the code now let us look at the

code every time I was generating the

matrix so how many such mattis's I have

generated for such mattresses I have

generated right now for generating a

matrix what I am supposed to do

I should generate each and every term so

total how many terms are there see the

number of vertices are 4 so let us say n

vertices so the number of elements are n

cross n this is a square matrix now

forgetting all the elements of a square

matrix I should have to follow so I'll

take two for loops for I assigns one I

less than or equal to n I plus plus and

for J assigned 1 J is less than equal to

n J plus plus and I should get the terms

of a of I comma J as minimum of a of I

comma J that is existing matrix as it is

going to be a single instance of 2d

array in the single instance only I will

be updating the values so that's why

this is same thing then a of I 2k plus a

of k2j out of this I should select any

one of them whichever is minimum so what

is K here K will be changing the

intermediate mitosis so this whole thing

will generate just one matrix and I have

to generate all the mattis's so for K

assign one K is less than equal to and k

plus plus now first time K will be one

so the intermediate vertex will be one

all the time then K is a two so the

intermediate vertex will be two all the

time so K will take this value so when K

is one the pneumatics is generated then

k is a tude in the second Matrix is

generated so this is for generating a

matrix that's it this is the code for

all pairs shortest path problem then if

you look at this code this is having

three nested for-loops so the time will

be order of n cube so that's theta of n

cube that's all about this problem