GeezerVison is showing github.com — Java/Programs/BellmanFord.java at main · PandaWire/Java

Expand file tree

BellmanFord.java

Copy path

More file actions

Latest commit

History

107 lines (87 loc) · 2.47 KB

BellmanFord.java

Copy path

File metadata and controls

107 lines (87 loc) · 2.47 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

100

101

102

103

104

105

106

107

// Bellman Ford Algorithm in Java

class CreateGraph {

// CreateGraph - it consists of edges

class CreateEdge {

int s, d, w;

CreateEdge() {

s = d = w = 0;

}

};

int V, E;

CreateEdge edge[];

// Creates a graph with V vertices and E edges

CreateGraph(int v, int e) {

V = v;

E = e;

edge = new CreateEdge[e];

for (int i = 0; i < e; ++i)

edge[i] = new CreateEdge();

}

void BellmanFord(CreateGraph graph, int s) {

int V = graph.V, E = graph.E;

int dist[] = new int[V];

// Step 1: fill the distance array and predecessor array

for (int i = 0; i < V; ++i)

dist[i] = Integer.MAX_VALUE;

// Mark the source vertex

dist[s] = 0;

// Step 2: relax edges |V| - 1 times

for (int i = 1; i < V; ++i) {

for (int j = 0; j < E; ++j) {

// Get the edge data

int u = graph.edge[j].s;

int v = graph.edge[j].d;

int w = graph.edge[j].w;

if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])

dist[v] = dist[u] + w;

}

// Step 3: detect negative cycle

// if value changes then we have a negative cycle in the graph

// and we cannot find the shortest distances

for (int j = 0; j < E; ++j) {

int u = graph.edge[j].s;

int v = graph.edge[j].d;

int w = graph.edge[j].w;

if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {

System.out.println("CreateGraph contains negative w cycle");

return;

}

// No negative w cycle found!

// Print the distance and predecessor array

printSolution(dist, V);

}

// Print the solution

void printSolution(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]);

}

public static void main(String[] args) {

int V = 5; // Total vertices

int E = 8; // Total Edges

CreateGraph graph = new CreateGraph(V, E);

// edge 0 --> 1

graph.edge[0].s = 0;

graph.edge[0].d = 1;

graph.edge[0].w = 5;

// edge 0 --> 2

graph.edge[1].s = 0;

graph.edge[1].d = 2;

graph.edge[1].w = 4;

// edge 1 --> 3

graph.edge[2].s = 1;

graph.edge[2].d = 3;

graph.edge[2].w = 3;

// edge 2 --> 1

graph.edge[3].s = 2;

graph.edge[3].d = 1;

graph.edge[3].w = 6;

// edge 3 --> 2

graph.edge[4].s = 3;

graph.edge[4].d = 2;

graph.edge[4].w = 2;

graph.BellmanFord(graph, 0); // 0 is the source vertex

}