Posts

Floyd-Warshall Algorithm

Image
Floyd-Warshall Algorithm is an algorithm for locating the shortest path between all the pairs of vertices during a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But it doesn't work for the graphs with negative cycles (where the sum of the sides during a cycle is negative). Floyd-Warshall algorithm is additionally called as Floyd's algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, or WFI algorithm. This algorithm follows the dynamic programming approach to seek out the shortest paths. How to Floyd Warshall Algorithm Works? Let’s the given be a Graph Initial Graph Follow the steps below to seek out the shortest path between all the pairs of vertices. Step 1:   Create a matrix A0 of dimension n*n where n is that the number of vertices. The row and therefore the column are indexed as i and j respectively. i and j are the vertices of the graph.  Each cell A[i][j] is crammed with the space from the i th vertex to the j th vertex....

Brent's Algorithm

Image
Brent's Cycle detection Algorithm Given a linked list, check if the linked list has loop or not. Below diagram shows a linked list with a loop.   Brent’s cycle detection algorithm is analogous to Floyd's algorithm because it also uses two pointer technique. But there's some difference in their approaches. Here we make one pointer stationary till every iteration and teleport it to other pointer at every power of two. the beginning of the cycle is decided by the littlest power of two at which they meet. This improves upon the constant factor of Floyd’s algorithm by reducing the amount of calls. Move fast pointer (or second_pointer) in powers of two until we discover a loop. After every power, we reset slow pointer (or first_pointer) to previous value of second pointer. Reset length to 0 after every every power. The condition for loop testing is first_pointer and second_pointer become same. And loop isn't present if second_pointer becomes NULL. The condition for loop test...