Input: Given a weighted graph G with vertex set V and Edges E.

V represents the set of all vertices, E is a collection of pairs (i,j) representing an edge from i to j

Problem: Find the weight of the shortest path for all possible pair of vertices.

If we are having a graph with vertices V = {1,2,3….,n}.

If sp(i,j,k) = weight of the shortest path from vertex i to vertex j which can have vertices 1,2,3…k as intermediate nodes in that shortest path.

Then the final solution of the shortest path from vertex i to vertex j would…

Input: Given a weighted graph G with vertex set V and Edges E, a **source vertex u** ∈ V

V represents the set of all vertices, E is a collection of pairs (i,j) representing an edge from i to j

Problem: Find the weight of the shortest path from source vertex u to all the other vertices belonging to set V.

Shortest Pathfrom source vertex u to any other vertexcan have at most |V|-1 number of edges.

Given problem can be defined as:

if

sp(i,e)representsweight of theshortest path from source vertex u to vertexi…

Bucket sort is a non-comparison based sorting algorithm helpful in scenarios where your **data to be sorted is uniformly distributed over a particular range**.

Let’s say we are having an array with n elements. And all the elements in the range 0 to m-1.

Example: input arr: [23,15,21,9,2,10], here the range of elements is 0 to 23. So, n=6, m=24

To sort this array using bucket sort, we have to take the help of n buckets. Each bucket can store a list of elements from input array.

Note: here the Number of buckets we have taken is equal to the…