@Test void braessTestFixed() { List<Path> shortPath = null; try { shortPath = SPAlgorithms.kShortestPaths(graph, A, D,3); } catch (Exception e) { fail(e); } Path abd = new Path(); abd.add(AB); abd.add(BD); Path acd = new Path(); acd.add(AC); acd.add(CD); Path abcd = new Path(); abcd.add(AB); abcd.add(BC); abcd.add(CD); LinkedList<Path> p = new LinkedList<Path>(); p.add(abcd); p.add(acd); p.add(abd); if (shortPath == null || !(shortPath.equals(p))) fail("K Short Path returned "+shortPath.toString()); assertTrue(shortPath != null && shortPath.equals(p)); assertEquals(shortPath,p); }
public static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K) throws Exception{ List<Path> A = new LinkedList<Path>(); PriorityQueue<Path> B = new PriorityQueue<Path>(); A.add(SPAlgorithms.dijkstra(g, origin,destination)); if (A.get(0) == null) throw new Exception(); for (Integer k = 1; k < K; k++) { for (Integer i = 0; i < A.get(k-1).size(); i++) { Graph gprime = new Graph(g); Node spurNode = A.get(k-1).node(i); Path rootPath = A.get(k-1).subPath(0,i); for (Path p : A) { if (rootPath.equals(p.subPath(0,i))){ gprime.remove(p.get(i)); } } for (Node rootPathNode : rootPath.nodes()) { if (!rootPathNode.equals(spurNode)){ gprime.remove(rootPathNode); } } Path spurPath = SPAlgorithms.dijkstra(gprime, spurNode, destination); if (spurPath != null) { rootPath.append(spurPath); B.add(rootPath); } } if (B.isEmpty()) break; A.add(B.poll()); } return A; }
SPAlgorithms { public static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K) throws Exception{ List<Path> A = new LinkedList<Path>(); PriorityQueue<Path> B = new PriorityQueue<Path>(); A.add(SPAlgorithms.dijkstra(g, origin,destination)); if (A.get(0) == null) throw new Exception(); for (Integer k = 1; k < K; k++) { for (Integer i = 0; i < A.get(k-1).size(); i++) { Graph gprime = new Graph(g); Node spurNode = A.get(k-1).node(i); Path rootPath = A.get(k-1).subPath(0,i); for (Path p : A) { if (rootPath.equals(p.subPath(0,i))){ gprime.remove(p.get(i)); } } for (Node rootPathNode : rootPath.nodes()) { if (!rootPathNode.equals(spurNode)){ gprime.remove(rootPathNode); } } Path spurPath = SPAlgorithms.dijkstra(gprime, spurNode, destination); if (spurPath != null) { rootPath.append(spurPath); B.add(rootPath); } } if (B.isEmpty()) break; A.add(B.poll()); } return A; } }
SPAlgorithms { public static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K) throws Exception{ List<Path> A = new LinkedList<Path>(); PriorityQueue<Path> B = new PriorityQueue<Path>(); A.add(SPAlgorithms.dijkstra(g, origin,destination)); if (A.get(0) == null) throw new Exception(); for (Integer k = 1; k < K; k++) { for (Integer i = 0; i < A.get(k-1).size(); i++) { Graph gprime = new Graph(g); Node spurNode = A.get(k-1).node(i); Path rootPath = A.get(k-1).subPath(0,i); for (Path p : A) { if (rootPath.equals(p.subPath(0,i))){ gprime.remove(p.get(i)); } } for (Node rootPathNode : rootPath.nodes()) { if (!rootPathNode.equals(spurNode)){ gprime.remove(rootPathNode); } } Path spurPath = SPAlgorithms.dijkstra(gprime, spurNode, destination); if (spurPath != null) { rootPath.append(spurPath); B.add(rootPath); } } if (B.isEmpty()) break; A.add(B.poll()); } return A; }  }
SPAlgorithms { public static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K) throws Exception{ List<Path> A = new LinkedList<Path>(); PriorityQueue<Path> B = new PriorityQueue<Path>(); A.add(SPAlgorithms.dijkstra(g, origin,destination)); if (A.get(0) == null) throw new Exception(); for (Integer k = 1; k < K; k++) { for (Integer i = 0; i < A.get(k-1).size(); i++) { Graph gprime = new Graph(g); Node spurNode = A.get(k-1).node(i); Path rootPath = A.get(k-1).subPath(0,i); for (Path p : A) { if (rootPath.equals(p.subPath(0,i))){ gprime.remove(p.get(i)); } } for (Node rootPathNode : rootPath.nodes()) { if (!rootPathNode.equals(spurNode)){ gprime.remove(rootPathNode); } } Path spurPath = SPAlgorithms.dijkstra(gprime, spurNode, destination); if (spurPath != null) { rootPath.append(spurPath); B.add(rootPath); } } if (B.isEmpty()) break; A.add(B.poll()); } return A; }  static Path dijkstra(Graph g, Node origin, Node destination); static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K); }
SPAlgorithms { public static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K) throws Exception{ List<Path> A = new LinkedList<Path>(); PriorityQueue<Path> B = new PriorityQueue<Path>(); A.add(SPAlgorithms.dijkstra(g, origin,destination)); if (A.get(0) == null) throw new Exception(); for (Integer k = 1; k < K; k++) { for (Integer i = 0; i < A.get(k-1).size(); i++) { Graph gprime = new Graph(g); Node spurNode = A.get(k-1).node(i); Path rootPath = A.get(k-1).subPath(0,i); for (Path p : A) { if (rootPath.equals(p.subPath(0,i))){ gprime.remove(p.get(i)); } } for (Node rootPathNode : rootPath.nodes()) { if (!rootPathNode.equals(spurNode)){ gprime.remove(rootPathNode); } } Path spurPath = SPAlgorithms.dijkstra(gprime, spurNode, destination); if (spurPath != null) { rootPath.append(spurPath); B.add(rootPath); } } if (B.isEmpty()) break; A.add(B.poll()); } return A; }  static Path dijkstra(Graph g, Node origin, Node destination); static List<Path> kShortestPaths(Graph g, Node origin, Node destination, Integer K);  }