package org.psjava.example;

import junit.framework.Assert;

import org.junit.Test;
import org.psjava.algo.graph.shortestpath.BellmanFord;
import org.psjava.algo.graph.shortestpath.Dijkstra;
import org.psjava.algo.graph.shortestpath.SingleSourceShortestPathResult;
import org.psjava.algo.graph.shortestpath.SingleSourceShortestPath;
import org.psjava.ds.graph.MutableDirectedWeightedGraph;
import org.psjava.ds.heap.BinaryHeapFactory;
import org.psjava.goods.GoodSingleSourceShortestPath;
import org.psjava.math.ns.IntegerNumberSystem;

public class ShortestPathExample {

	@Test
	public void example() {

		// Let's construct a graph.

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

		// Then calculate distances from a single source - 'A'.
		// Choose algorithm, and do it.

		SingleSourceShortestPath algorithm = GoodSingleSourceShortestPath.getInstance();
		SingleSourceShortestPathResult<Integer> result = algorithm.calc(graph, "A", IntegerNumberSystem.getInstance());

		int distanceAToC = result.getDistance("C");

		Assert.assertEquals(30, distanceAToC);

		// The good one should be Dijkstra's Algorithm with binary heap. but you
		// can specify to another algorithm. Followings are some possibles.

		new Dijkstra(new BinaryHeapFactory());
		new BellmanFord();
	}
}

@@ -35,30 +35,33 @@
 ort 
-junit.framework
+static org.junit
 .Assert
+.*
 ;%0D%0A%0D
@@ -131,72 +131,316 @@
 ath.
-BellmanFord;%0D%0Aimport org.psjava.algo.graph.shortestpath.Dijkstra
+AllPairShortestPath;%0D%0Aimport org.psjava.algo.graph.shortestpath.AllPairShortestPathResult;%0D%0Aimport org.psjava.algo.graph.shortestpath.BellmanFord;%0D%0Aimport org.psjava.algo.graph.shortestpath.Dijkstra;%0D%0Aimport org.psjava.algo.graph.shortestpath.FloydWarshall;%0D%0Aimport org.psjava.algo.graph.shortestpath.Johnson
 ;%0D%0Ai
@@ -1335,16 +1335,17 @@
 lgorithm
+1
  = GoodS
@@ -1432,16 +1432,17 @@
 %3E result
+1
  = algor
@@ -1445,16 +1445,17 @@
 lgorithm
+1
 .calc(gr
@@ -1509,28 +1509,19 @@
 %0D%0A%09%09int 
-distanceAToC
+a2c
  = resul
@@ -1521,16 +1521,17 @@
 = result
+1
 .getDist
@@ -1546,48 +1546,114 @@
 );%0D%0A
-%0D%0A%09%09Assert.assertEquals(30, distanceAToC
+%09%09boolean reachableOfD = result1.isReachable(%22D%22);%0D%0A%0D%0A%09%09assertEquals(30, a2c);%0D%0A%09%09assertFalse(reachableOfD
 );%0D%0A
@@ -1865,16 +1865,709 @@
 nFord();
+ // Capable for negative edge.%0D%0A%0D%0A%09%09// Let's get the shortest paths of all pairs. Floyd Warshall's algorithm is the simplest implementation.%0D%0A%0D%0A%09%09AllPairShortestPath algoritm2 = new FloydWarshall();%0D%0A%09%09AllPairShortestPathResult%3CInteger%3E result2 = algoritm2.calc(graph, IntegerNumberSystem.getInstance());%0D%0A%0D%0A%09%09int a2b = result2.getDistance(%22A%22, %22B%22);%0D%0A%09%09int b2a = result2.getDistance(%22B%22, %22C%22);%0D%0A%0D%0A%09%09assertEquals(10, a2b);%0D%0A%09%09assertEquals(20, b2a);%0D%0A%0D%0A%09%09// There are other algorithms to get shortest paths of all pairs.%0D%0A%0D%0A%09%09new FloydWarshall(); // Most simple.%0D%0A%09%09new Johnson(new BellmanFord(), new Dijkstra(new BinaryHeapFactory())); // Good for spase tree. Also capable in negative edges.%0D%0A
 %0D%0A%09%7D%0D%0A%7D%0D

improve example for all pair shortest path algorithms