Bellman Ford Algorithm - Single Source Shortest Path

  Explanation Video

Relax values of edges V-1 times.


This algorithm won't work if there is -ve weight edge and form a circle. To verify if there is a circle we can run algorithm 1 additional time and see if weight is getting relaxed for any edge.

Greeksforgreeks 

Comments

Post a Comment

Popular posts from this blog

Tree terminologies

Image
 Tree : Tree is collection of nodes and edges. Or, it's collection of nodes where one node is taken as root node and rest of the nodes are divided into disjoint subsets and each subset is tree or subtree.  Tree terminologies :  Level starts from 1 onwards (we count nodes) and height starts from 0 onwards (we counts edges).  Binary Tree : A tree that can have 0, 1 or 2 sub trees, is called binary tree. How many binary trees can be generated from given number of nodes (n)? 1. Unlabelled Nodes : How many trees with maximum height? 2. Labelled Nodes :  Height vs Nodes Formula :  1. If height of binary tree is given? Minimum No. of Nodes (n) = h + 1 Maximum No. of Nodes (n) = 2^(n+1) - 1 2. If nodes of binary tree is given? Minimum Height (h) = log(n+1) - 1 Maximum  Height (h)  = n-1 Relationship b/w nodes with degree 0 and degree 2: Number of nodes with degree(0) = Number of nodes with degree(2) + 1
Read more

Circular Queue implementation

import java.util.Arrays; /** * Key points : * 1. Max capecity can be size-1. As 1 space in queue will alway be empty * 2. Next index = (currentIndex+1)%size * 3. Empty condition : front == rear * 4. Full condition : (front+1)%size == rear */ class CircularQueue { // for dequeue operation private int front; // for enqueue operation private int rear; private int capacity; private int[] array; private static final int DEFAULT_CAPACITY = 6; // we can insert 5 elements public CircularQueue() { this(DEFAULT_CAPACITY); } public CircularQueue(int capacity) { this.front = this.rear = 0; this.capacity = capacity queue.enqueue(d)); // Display System.out.println("Display queue"); queue.display(); // Overflow System.out.println("\nInsert 10"); queue.enqueue(10); // Dequeue System.out.println("Deletin...
Read more