Dijkstra's and Bellman-Ford Algorithm

I guess BF algorithm in Java must be something like this:

package shortest_path;

import java.util.Arrays;

import java.util.Vector;

public class BellmanFord {

public static int INF = Integer.MAX_VALUE;

// this class represents an edge between two nodes

static class Edge {

int source; // source node

int destination; // destination node

int weight; // weight of the edge

public Edge() {}; // default constructor

public Edge(int s, int d, int w) { source = s; destination = d; weight = w; }

}

public static void main(String[] args) {

Vector<Edge> edges = new Vector<Edge>(); // a sample vector of edges of some graph

edges.add(new Edge(0, 1, 5));

edges.add(new Edge(0, 2, 8));

edges.add(new Edge(0, 3, -4));

edges.add(new Edge(1, 0, -2));

edges.add(new Edge(2, 1, -3));

edges.add(new Edge(2, 3, 9));

edges.add(new Edge(3, 1, 7));

edges.add(new Edge(3, 4, 2));

edges.add(new Edge(4, 0, 6));

edges.add(new Edge(4, 2, 7));

bellmanFord(edges, 5, 4);

}

public static void bellmanFord(Vector<Edge> edges, int nnodes, int source) {

// the 'distance' array contains the distances from the main source to all other nodes

int[] distance = new int[nnodes];

// at the start - all distances are initiated to infinity

Arrays.fill(distance, INF);

// the distance from the main source to itself is 0

distance[source] = 0;

// in the next loop we run the relaxation 'nnodes' times to ensure that

// we have found new distances for ALL nodes

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

// relax every edge in 'edges'

for (int j = 0; j < edges.size(); ++j) {

// analyze the current edge (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):

// if the distance to the SOURCE node is equal to INF then there's no shorter path from our main source to DESTINATION through SOURCE

if (distance[edges.get(j).source] == INF) continue;

// newDistance represents the distance from our main source to DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')

int newDistance = distance[edges.get(j).source] + edges.get(j).weight;

// if the newDistance is less than previous shortest distance from our main source to DESTINATION

// then record that new shortest distance from the main source to DESTINATION

if (newDistance < distance[edges.get(j).destination])

distance[edges.get(j).destination] = newDistance;

}

// next loop analyzes the graph for cycles

for (int i = 0; i < edges.size(); ++i)

// 'if (distance[edges.get(i).source] != INF)' means:

// "

//if the distance from the main source node to the DESTINATION node is equal to infinity then there's no path between them

// "

// 'if (distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight)' says that there's a negative edge weight cycle in the graph

if (distance[edges.get(i).source] != INF && distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight) {

System.out.println("Negative edge weight cycles detected!");

return;

}

// this loop outputs the distances from the main source node to all other nodes of the graph

for (int i = 0; i < distance.length; ++i)

if (distance[i] == INF)

System.out.println("There's no path between " + source + " and " + i);

else

System.out.println("The shortest distance between nodes " + source + " and " + i + " is " + distance[i]);

}

}

Nikaustra at 2007-7-15 4:23:09 >