# Graphs 2: Bellman Ford & Floyd Warshall Algorithm
---
### Dijkstra Algorithm
Dijkstra Algorithm is used to find the Shortest Distance from the source node to every other node.
But in Dijkstra, we have a small condition,
* Weights of the Edges needs to be positive
---
### Belmann ford
How to find the shortest path to all nodes from a given source node if graph can have -ve weight edges.
**Example:**
Lets find the shortest distance from 1->6.
Answer : 10
### Edge case
Lets take an Edge case,
Find the shortest path from 1 -> 6.
Is it 10 ?
No.
Now, before moving from 4->6, lets move to 4->5, then 5->3 then 3->4 then 4->6.
Is it 7 ?
No. If we do the same thing, again and again then the cost will reduce to 4, then 1, then -2, -5, -8...
At this scenerio, we have a negative weighted Cycle.
### Observation
At this case, Shortest path does not exist.
---
### Find shortest path with -ve edges using Belmann Ford
Belmann ford uses a very interesting concept,
* Update / Relaxing an edge
Lets consider this graph,
Lets find the shortest distance between 1 and 2.
We have a direct edge from 1 -> 2 with weight as 7.
We have explore the neighbours of 1, we have 3.
> Minimum distance can be found by relaxing / updating all the edges (N - 1) times, irrespective of the order in which the edges are selected.
### Dry Run
Consider the below directed graph.
The Source node is 1.
Now lets initialize the distance array (which tells the shortest distance from the source node)
### Pseudo Code
```java
parent[N + 1] = {i} (Parent[i] = i)
dist[N + 1] = inf;
dist[source] = 0;
for(i = 0; i < N-1; i++){
bool stop = True;
for(all edges (u->v)){
if (dist[u] + W[u->v] < d[v]){
stop = false;
d[v] = dist[u] + W[u->v];
p[v] = u;
}
}
if(stop == True){
break;
}
}
```
### Complexity
**Time Completity: O(N * E)**
---
### Floyd Warshall algorithm
Given a graph with N nodes. What is the maximum number of edges present in the path between any 2 nodes ?
**Solution:**
Floyd Warshall algorithm => All pair shortest path algorithm.
**Example:**
### Dry Run:
**Lets Take Intermediate node as 0:**
Now, Fill the cells one by one.
Process for any pair of vertices, say (x, y).
Then
```cpp
d(x, y) = min(d(x, y), d(x, intermediate_node) + d(intermediate_node, y))
```
(1, 1) => d(1, 0) + d(0, 1) = 6 + 9 = 15
Is 15 better than 0 ? No. So mark as 0.
(1, 2) => d(1, 0) + d(0, 2) = 6 + (-4) = 2
Is 2 better than ∞ ? Yes, So mark as 2.
(1, 3) => d(1, 0) + d(0, 3) = 6 + ∞ = ∞
Is ∞ better than 2? No, So mark as 2.
Do the same process using the Intermediate node as 0.
After performing, the matrix will be.
Like wise the process will continue for each node as an Intermediate node!
### Psuedo code
```cpp
1, Create Adjacency matrix M
for (i = 0; i < N; i++) {
for(u = 0; u < N; u++){
if(u == i) {continue;}
if(m[u][i] == inf) {continue;}
for(v = 0; v < N; v++){
if(v == i) {continue;}
if(u == v) {continue;}
if(M[u][i] + M[i][v] < M[u][v]{
M[u][v] = M[u][i] + M[i][v];
}
}
}
}
```
---
## Spanning Tree
A spanning tree is a subset of Graph G, such that all the vertices are connected using minimum possible number of edges.
> What is the minimum number of Edges needed to make the graph of N nodes connected ?
> N - 1 edges are needed
Lets take an example to understand it better.
One of the Spanning Tree of the above Graph.
Another one,
Another one,
### Minimum Spanning Tree
Among all possible Spanning Trees, if the Sum of the weight of the remaining edges is minimum possible is know as Minimum Spanning Tree.
There can be many Minimum Spanning Trees possible.
---
### Find MST
Given an undirectred connected weighted graph. Find the edges of one of the MST.
**Recap: Prim's Algorithm**
The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, and the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
Now we are going to use Kruskal's Algorithm with the concept of DSU.
Lets take a connected graph.
List the edges with their weights.
Initially all the nodes are disconnected.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Parent | x | 1 | 2 | 3 | 4 | 5 | 6 |
We dont care 0.
Lets pick the edges one by one, with the minimum weight possible.
**Remove <2, <3 - 5>>**
Perform Union operation on 3 and 5.
As we can see that, 3 and 5 belongs to different sets.
Updated Parent array will be,
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Parent | x | 1 | 2 | 3 | 4 | 3 | 6 |
**Remove <3, <2 - 6>>**
Perform Union operation on 2 and 6
As we can see that, 2 and 6 belongs to different sets.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Parent | x | 1 | 2 | 3 | 4 | 3 | 2 |
**Remove <3, <6 - 5>>**
Perform Union operation on 6 and 5
As we can see that, 6 and 5 belongs to different sets.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Parent | x | 1 | 2 | 3 | 4 | 3 | 2 |
**Remove <4, <6 - 3>>**
Perform Union operation on 6 and 3
As we can see that, 6 and 3 belongs to belongs to the same group.
There is no need to udpate.
Whenever we are updating, we can perform path compression as well, which is used to minimise the time taken.
Update using the same process.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Parent | x | 3 | 3 | 3 | 3 | 3 | 3 |
### Pseudo code
```cpp
1) Parent array of (N + 1)
P[i] = i;
2) Add all edges in format <weight, <soruce, destination>> in a min heap.
List <int, Pair<int, int>> edges
3) While (! heap.isEmpty()) {
X = heap.getMin();
weight = X.first;
source = X.second.first;
dest = X.second.second;
}
bool isUnion = union(source, destination);
if(isUnion == True) {
// Add edges to list;
}
```
Sign in with Wallet
Connect another wallet