Solving Single Source Shortest Paths Problem Using Bellman-Ford's Algorithm

This is an implementation of Bellman-Ford’s algorithm which solves the single-source shortest paths problem. The implementation can support any type of nodes (i.e. String, Integer, etc.).

According to Wikipedia (2012), the Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra’s algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights.

You can read more about the algorithm here.

The Graph implementation can be found here.

SSSPBellmanFord.java

import java.util.*;
import java.io.*;

// Written by: Yancy Vance M. Paredes.

// Finding single source shortest paths using Bellman Ford's algorithm.

public class SSSPBellmanFord {
	
	public static void main(String[] args) throws Exception {
		Scanner iFile = new Scanner(new FileReader("ssspBellmanFord.in"));
		Graph graph = new Graph();
		graph.setDirected();
		
		while(iFile.hasNext()) {
			Node<String> a = new Node<String>(iFile.next());
			Node<String> b = new Node<String>(iFile.next());
			
			int aPos = graph.indexOf(a);
			int bPos = graph.indexOf(b);
			
			// If a does not exist in the graph yet.
			if(aPos == -1)
				aPos = graph.addNode(a);
			
			// If b does not exist in the graph yet.
			if(bPos == -1)
				bPos = graph.addNode(b);
			
			double weight = iFile.nextDouble();
			
			Edge edge = new Edge(graph.getNodeAt(aPos), graph.getNodeAt(bPos), weight);
			
			graph.addEdge(edge);
		}
		
		//graph.printNodes();
		//graph.printEdges();
	
		Vector<Node> nodes = graph.getNodes();
		
		for(Node source : nodes) {		
			System.out.println("From " + source + ":");
			
			// Step 1: Initialize the graph.
			for(Node destination : nodes) {
				if(source == destination)
					destination.distance = 0;
				else
					destination.distance = Double.POSITIVE_INFINITY;
				
				destination.predecessor = null;
			}
			
			Vector<Edge> edges = graph.getEdges();
			
			// Step 2: Relax edges repeatedly.
			for(int j = 0; j < nodes.size(); j++) {				
				for(Edge edge : edges) {
					Node a = edge.a;
					Node b = edge.b;
					
					if(Double.compare(a.distance + edge.weight, b.distance) < 0) {
						b.distance = a.distance + edge.weight;
						b.predecessor = a;
					}
				}
			}
			
			for(int j = 0; j < nodes.size(); j++) {
				Node node = nodes.elementAt(j);
				
				System.out.println("\tShortest Path Cost to " + node + " is: " + node.distance);
				
				if(Double.compare(node.distance, Double.POSITIVE_INFINITY) != 0) {
					Stack<Node> stack = new Stack<Node>();
					Node ptr = node;
					
					do {
						stack.push(ptr);
						ptr = ptr.predecessor;
					} while(ptr != null);
					
					System.out.print("\t\t");
					
					while(!stack.isEmpty())
						System.out.print(stack.pop() + " -> ");
						
					System.out.println();
				}
					
			}
			
			System.out.println();
		}
		
		iFile.close();		
	}

}

ssspBellmanFord.in

hongkong thailand 3
thailand singapore 1
hongkong malaysia 4
malaysia singapore 1
hongkong singapore 4
singapore hongkong 1
thailand hongkong 2
thailand malaysia 2
singapore japan 10

The input file describes a directed connection between two places and its weight.

Sample Output:

From hongkong:
	Shortest Path Cost to hongkong is: 0.0
		hongkong -> 
	Shortest Path Cost to thailand is: 3.0
		hongkong -> thailand -> 
	Shortest Path Cost to singapore is: 4.0
		hongkong -> thailand -> singapore -> 
	Shortest Path Cost to malaysia is: 4.0
		hongkong -> malaysia -> 
	Shortest Path Cost to japan is: 14.0
		hongkong -> thailand -> singapore -> japan -> 

From thailand:
	Shortest Path Cost to hongkong is: 2.0
		thailand -> singapore -> hongkong -> 
	Shortest Path Cost to thailand is: 0.0
		thailand -> 
	Shortest Path Cost to singapore is: 1.0
		thailand -> singapore -> 
	Shortest Path Cost to malaysia is: 2.0
		thailand -> malaysia -> 
	Shortest Path Cost to japan is: 11.0
		thailand -> singapore -> japan -> 

From singapore:
	Shortest Path Cost to hongkong is: 1.0
		singapore -> hongkong -> 
	Shortest Path Cost to thailand is: 4.0
		singapore -> hongkong -> thailand -> 
	Shortest Path Cost to singapore is: 0.0
		singapore -> 
	Shortest Path Cost to malaysia is: 5.0
		singapore -> hongkong -> malaysia -> 
	Shortest Path Cost to japan is: 10.0
		singapore -> japan -> 

From malaysia:
	Shortest Path Cost to hongkong is: 2.0
		malaysia -> singapore -> hongkong -> 
	Shortest Path Cost to thailand is: 5.0
		malaysia -> singapore -> hongkong -> thailand -> 
	Shortest Path Cost to singapore is: 1.0
		malaysia -> singapore -> 
	Shortest Path Cost to malaysia is: 0.0
		malaysia -> 
	Shortest Path Cost to japan is: 11.0
		malaysia -> singapore -> japan -> 

From japan:
	Shortest Path Cost to hongkong is: Infinity
	Shortest Path Cost to thailand is: Infinity
	Shortest Path Cost to singapore is: Infinity
	Shortest Path Cost to malaysia is: Infinity
	Shortest Path Cost to japan is: 0.0
		japan -> 

The output shows the minimal cost to travel from the source to the destination if there is a path. However, if it is impossible to reach the destination (no path exists), it will output an Infinity. There may be more than one shortest path available to travel from source to destination. The program provides only one.

About these ads