1 25 40 package org.jgrapht.alg; 41 42 import java.util.*; 43 44 import org.jgrapht.*; 45 import org.jgrapht.graph.*; 46 47 48 53 public class BellmanFordShortestPathTest 54 extends ShortestPathTestCase 55 { 56 57 59 62 public void testConstructor() 63 { 64 BellmanFordShortestPath<String , DefaultWeightedEdge> path; 65 Graph<String , DefaultWeightedEdge> g = create(); 66 67 path = new BellmanFordShortestPath<String , DefaultWeightedEdge>(g, V3); 68 69 assertEquals( 71 Arrays.asList(new DefaultEdge [] { 72 e13, 73 e12, 74 e24, 75 e45 76 }), 77 path.getPathEdgeList(V5)); 78 assertEquals(15.0, path.getCost(V5), 0); 79 80 path = 82 new BellmanFordShortestPath<String , DefaultWeightedEdge>( 83 g, 84 V3, 85 2); 86 assertEquals( 87 Arrays.asList(new DefaultEdge [] { 88 e34, 89 e45 90 }), 91 path.getPathEdgeList(V5)); 92 assertEquals(25.0, path.getCost(V5), 0); 93 94 path = 96 new BellmanFordShortestPath<String , DefaultWeightedEdge>( 97 g, 98 V3, 99 1); 100 assertNull(path.getPathEdgeList(V5)); 101 } 102 103 protected List findPathBetween( 104 Graph<String , DefaultWeightedEdge> g, 105 String src, 106 String dest) 107 { 108 return BellmanFordShortestPath.findPathBetween(g, src, dest); 109 } 110 111 public void testWithNegativeEdges() 112 { 113 Graph<String , DefaultWeightedEdge> g = createWithBias(true); 114 115 List path; 116 117 path = findPathBetween(g, V1, V4); 118 assertEquals(Arrays.asList(new DefaultEdge [] { 119 e13, 120 e34 121 }), path); 122 123 path = findPathBetween(g, V1, V5); 124 assertEquals(Arrays.asList(new DefaultEdge [] { e15 }), path); 125 } 126 } 127 128 | Popular Tags |