Bellman-Ford Algorithm
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
- As we have seen in above example that Dijkstra Algorithm not always find the shortest path in case of negative edges. Bellman-Ford always give correct result even in case of negative edges (though it has its own drawback).
- As Dijkstra says relax the vertices's only once, Bellman-Ford says we can relax vertices's for n number of times, so that we can get perfect shortest path to all the vertices's.
- In Bellman-Ford we make list of all the edges and go one relaxing them for v-1 times (where v is the number of vertices) after which we will surely get the shortest path to all the edges even in case of negative edges.
We need to first make list of edges. In our case it would be (d,b), (c,d), (a,c), (a,b).
1). Take the list of all edges and mark the distances of all the vertices's as infinity, keep the first one ('a' in our case) as zero. Now we need to go and relax the vertices's for v-1 times (where v is number of vertices's), in our case it will be three. Lets start with d to b, d is infinity and b is infinity, so the shortest path from d to b would be infinity plus infinity which is infinity. Now we take c to d, again since both have infinity, so the shortest path at d would be infinity. Now take a to c, it would be 0+2, which is 2, we will change the shortest path at c from infinity to 2. Now we take a to b, and change the shortest path at b from infinity to 1. We have relaxed the vertices's for 1st time.
2). We repeat the process again, from d to b the shortest path would be infinity (value at d) minus 6 (since the edge has negative value), this will gives infinity. But the value at b is 1, which is less than infinity, so we are not going to change it. Now we take c to d, the shortest path would be 2+3 which is 5, shortest path at d was infinity, we will change it to 5. Now we take a to c, which gives shortest path as 2, which is already 2, so we are not going to change it. Same is the case from a to b. We have relaxed the vertices's for 2nd time.
3). Again we will go from d to b, the shortest path would be 5-6, thats -1. The shortest path at b is 1, which is greater than -1, so we will change it to -1. Then we will go from c to d, a to c, a to b, but the values remain unchanged.
4). We have relaxed vertices's for 3rd time. (v-1).
Bellman-Ford fails if there is a negative cycle in the graph. Like in the below case b-c-d has a cycle and total value is 1 + 3 + (-6), which is -3.
-K Himaanshu Shuklaa..
No comments:
Post a Comment