The idea is simple - relax all the edges V-1 number of times.
Proof -
Path-relaxation property - If p = {v0, v1, ..., vk) is a shortest path from s = v0 to vk, and we relax the edges of p in the order (v0, v1), (v1, v2), ..., (vk-1, vk), then vk.d = f(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.
Let us consider we have a graph with 5 vertices and 8 edges. Relaxations are as follows (we set the source as vertex 0 from where we have to find the shortest path to all other vertices):
Let us say
The shortest path from Vertex 0 to Vertex 1 needs relaxations in the order E2 E4 E1 E0
The shortest path from Vertex 0 to Vertex 2 needs relaxations in the order E3 E8 E6
Pass 1 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 2 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 3 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 4 E0 E1 E2 E3 E4 E5 E6 E7 E8
The highlighted edges shows that the shortest path edges for vertex 0 to vertex 1 has been relaxed. You can trace out the edge relaxations for other paths as well.
Example for Worst Case (Wikipedia) -
Source:
Output:
Results :
0 - 1 : distTo[1] -> 4.0
0 - 2 : distTo[2] -> 2.0
2 - 3 : distTo[3] -> 1.0
3 - 4 : distTo[4] -> -3.0
3 - 5 : distTo[5] -> 4.0
Proof -
Path-relaxation property - If p = {v0, v1, ..., vk) is a shortest path from s = v0 to vk, and we relax the edges of p in the order (v0, v1), (v1, v2), ..., (vk-1, vk), then vk.d = f(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.
Let us consider we have a graph with 5 vertices and 8 edges. Relaxations are as follows (we set the source as vertex 0 from where we have to find the shortest path to all other vertices):
Let us say
The shortest path from Vertex 0 to Vertex 1 needs relaxations in the order E2 E4 E1 E0
The shortest path from Vertex 0 to Vertex 2 needs relaxations in the order E3 E8 E6
The shortest path from Vertex 0 to Vertex 3 needs relaxations in the order E2 E0 E8
The shortest path from Vertex 0 to Vertex 4 needs relaxations in the order E3 E1
Pass 1 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 2 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 3 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 4 E0 E1 E2 E3 E4 E5 E6 E7 E8
The highlighted edges shows that the shortest path edges for vertex 0 to vertex 1 has been relaxed. You can trace out the edge relaxations for other paths as well.
Example for Worst Case (Wikipedia) -
Source:
import java.util.ArrayList; import java.util.Arrays; public class BellmanFord { class DWEdge{ int from, to; double weight; DWEdge(int from, int to, double weight){ this.from = from; this.to = to; this.weight = weight; } } private ArrayList<ArrayList<DWEdge>> graph; private int edgeTo[]; private double distTo[]; private int V; BellmanFord(int V){ graph = new ArrayList<>(); edgeTo = new int[V]; distTo = new double[V]; Arrays.fill(distTo, Double.POSITIVE_INFINITY); this.V = V; graph.ensureCapacity(V); for(int i=0;i<V;++i)graph.add(new ArrayList<>()); } public void addEdge(int from, int to, double weight){ graph.get(from).add(new DWEdge(from, to, weight)); } public void relax(DWEdge e){ if(distTo[e.to] > distTo[e.from] + e.weight){ distTo[e.to] = distTo[e.from] + e.weight; edgeTo[e.to] = e.from; } } public void BellmanFord(int source){ distTo[source] = 0; for(int i=0;i<V-1;++i){ for(int j=0;j<V;++j){ for(DWEdge e:graph.get(j)){ relax(e); } } } } public static void main(String[] args){ BellmanFord bf = new BellmanFord(6); bf.addEdge(0,1,4);bf.addEdge(0,2,2); bf.addEdge(3,4,-4);bf.addEdge(0,3,2); bf.addEdge(2,3,-1);bf.addEdge(1,2,3); bf.addEdge(1,4,1);bf.addEdge(4,2,6); bf.addEdge(1,5,5);bf.addEdge(3,5,3); bf.addEdge(5,4,7); int source = 0; bf.BellmanFord(source); System.out.println("Results : "); for(int i=0;i<bf.V;++i){ if(i==source)continue; System.out.println(bf.edgeTo[i]+" - "+i+" : distTo["+i+"] -> "+bf.distTo[i]); } } }
Output:
Results :
0 - 1 : distTo[1] -> 4.0
0 - 2 : distTo[2] -> 2.0
2 - 3 : distTo[3] -> 1.0
3 - 4 : distTo[4] -> -3.0
3 - 5 : distTo[5] -> 4.0
No comments:
Post a Comment