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 Path from source vertex u to any other vertex can have at most |V|-1 number of edges.

Given problem can be defined as:

if sp(i,e) represents weight of the shortest path from source vertex u to vertex i

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…

Kapil Thukral

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store