Bellman Ford Algorithm

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

// Let's construct a simple graph which contains negatively weighted edge.

MutableDirectedWeightedGraph<String, Integer> graph = MutableDirectedWeightedGraph.create();
graph.insertVertex("A");
graph.insertVertex("B");
graph.insertVertex("C");
graph.addEdge("A", "C", 10);
graph.addEdge("A", "B", 15);
graph.addEdge("B", "C", -10); // negative weight is allowed.

// Then calculate distances from a single source 'A'

BellmanFordAlgorithm algorithm = BellmanFordAlgorithm.getInstance();
SingleSourceShortestPathResult<String, Integer, DirectedWeightedEdge<String, Integer>> result1 = algorithm.calc(graph, "A", IntegerNumberSystem.getInstance());

boolean reachabilityOfC = result1.isReachable("C"); // must be true
int distanceAToC = result1.getDistance("C"); // must be 5

See Also

• Shortest Path Algorithm
• Dijkstra Algorithm

Implementation

• BellmanFordAlgorithm.java in GitHub

---

Copyright 2014 psjava team. View on GitHub