Floyd Warshall 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 graph.

MutableDirectedWeightedGraph<String, Integer> graph = MutableDirectedWeightedGraph.create();
graph.insertVertex("A");
graph.insertVertex("B");
graph.insertVertex("C");
graph.addEdge("A", "C", 100);
graph.addEdge("A", "B", 10);
graph.addEdge("B", "C", 20);

// Let's get the shortest paths of all pairs.

AllPairShortestPath floyd = FloydWarshallAlgorithm.getInstance();
AllPairShortestPathResult<String, Integer, DirectedWeightedEdge<String, Integer>> res = floyd.calc(graph, IntegerNumberSystem.getInstance());

int distanceAToB = res.getDistance("A", "B"); // must be 10
int distanceBToC = res.getDistance("B", "C"); // must be 20

See Also

Implementation

Copyright 2014 psjava team. View on GitHub