Aim:
Implementation of Bellman ford algorithm.
Theory:
Bellman-Ford algorithm solves the single-source
shortest-path problem in the general case in which edges of a given digraph can
have negative weight as long as G contains no negative cycles.
This algorithm, like Dijkstra's algorithm uses
the notion of edge relaxation but does not use with greedy method. Again, it
uses d[u] as an upper bound on the distance d[u, v] from u to v.
The algorithm progressively decreases an estimate
d[v] on the weight of the shortest path from the source vertex s to each vertex
v in V until it achieve the actual shortest-path. The algorithm returns Boolean
TRUE if the given digraph contains no negative cycles that are reachable from
source vertex s otherwise it returns Boolean FALSE.
BELLMAN-FORD
(G, w, s)
- INITIALIZE-SINGLE-SOURCE
(G, s)
- for each
vertex i = 1 to V[G] - 1 do
-
for each edge (u, v) in E[G] do
-
RELAX (u, v, w)
- For each
edge (u, v) in E[G] do
-
if d[u] + w(u, v) < d[v] then
-
return FALSE
- return
TRUE
Analysis
- The
initialization in line 1 takes
(v) time - For loop
of lines 2-4 takes O(E) time and For-loop of line 5-7 takes O(E) time.
Asymptotic complexity:
• Average case (random data): O(|V ||E|)
• Worst case: O(|V ||E|)
Conclusion:
Thus, the Bellman-Ford algorithm
runs in O(E) time.
Program:
Bellman.java
import java.io.*;
import java.util.*;
import java.io.DataInputStream;
class Edge
{
int source;
int dest;
int weight;
}
class Bellman
{
public static void BellmanFord(Edge edges[], int edgecount,
int nodecount, int source)
{
int infinity=50000;
int i, j;
int distance[]=new int[nodecount];
for(i=0; i<nodecount; i++)
distance[i]=infinity;
distance[source]=0;
for(i=0; i<nodecount; i++)
{
boolean somethingchanged=false;
for(j=0; j<edgecount; j++)
{
if(distance[edges[j].source]!=infinity)
{
int new_distance=distance[edges[j].source]+edges[j].weight;
if(new_distance<distance[edges[j].dest])
{
distance[edges[j].dest]=new_distance;
somethingchanged=true;
}
}
}
if(!somethingchanged)
break;
}
for(i=0; i<edgecount; ++i)
{
if(distance[edges[i].dest]>distance[edges[i].source]+edges[i].weight)
System.out.println("Negative edge weight cycles
detected!!!");
}
for(i=0; i<nodecount; ++i)
System.out.println("The shortest distance between nodes
"+source+" & "+i+" is "+distance[i]);
}
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
Edge edges[]=new Edge[10];
for( int i=0; i<10; i++)
{
edges[i]=new Edge();
System.out.print("Enter source number ["+i+"]
: ");
edges[i].source=in.nextInt();
System.out.print("Enter destination number
["+i+"] : ");
edges[i].dest=in.nextInt();
System.out.print("Enter weight number ["+i+"]
: ");
edges[i].weight=in.nextInt();
System.out.println();
}
BellmanFord(edges, 10, 5, 4);
}
}
OUTPUT:
C:\jdk1.6.0_18\bin>javac
Bellman.java
C:\jdk1.6.0_18\bin>java
Bellman
Enter source
number [0] : 0
Enter destination
number [0] : 1
Enter weight
number [0] : 10
Enter source
number [1] : 1
Enter destination
number [1] : 2
Enter weight
number [1] : 25
Enter source
number [2] : 2
Enter destination
number [2] : 3
Enter weight
number [2] : 35
Enter source
number [3] : 3
Enter destination
number [3] : 0
Enter weight
number [3] : 30
Enter source
number [4] : 0
Enter destination
number [4] : 2
Enter weight
number [4] : 20
Enter source
number [5] : 3
Enter destination
number [5] : 1
Enter weight
number [5] : 31
Enter source number
[6] : 4
Enter destination
number [6] : 3
Enter weight
number [6] : 32
Enter source
number [7] : 4
Enter destination
number [7] : 2
Enter weight
number [7] : 21
Enter source
number [8] : 4
Enter destination
number [8] : 0
Enter weight
number [8] : 33
Enter source
number [9] : 4
Enter destination
number [9] : 1
Enter weight
number [9] : 34
The shortest
distance between nodes 4 & 0 is 33
The shortest
distance between nodes 4 & 1 is 34
The shortest
distance between nodes 4 & 2 is 21
The shortest distance
between nodes 4 & 3 is 32
The shortest
distance between nodes 4 & 4 is 0
it says main method not mentioned inside bellman. How do we do that ? why here it is not mentioned ?
ReplyDeletetry this one
Delete// A Java program for Bellman-Ford's single source shortest path
// algorithm.
import java.util.*;
import java.lang.*;
import java.io.*;
// A class to represent a connected, directed and weighted graph
class Graph
{
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph,int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i=0; i<V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can
// have at-most |V| - 1 edges
for (int i=1; i<V; ++i)
{
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u]!=Integer.MAX_VALUE &&
dist[u]+weight<dist[v])
dist[v]=dist[u]+weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u]!=Integer.MAX_VALUE &&
dist[u]+weight<dist[v])
System.out.println("Graph contains negative weight cycle");
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i=0; i<V; ++i)
System.out.println(i+"\t\t"+dist[i]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}