@Test public void testSingleNode() { final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); g.addNode("a"); final DijkstraOutput<String> output = Dijkstra.dijkstra(g, "a", edge -> 0); assertEquals(0, output.getDistance("a")); assertNull(output.getPrevious("a")); }
public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) { final DijkstraOutput<NODE> output = initializeOutput(graph, start); final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes()); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance)); unprocessed.remove(current); for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) { final NODE next = entry.getKey(); final EDGE edgeToNext = entry.getValue(); final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext); if (alt < output.getDistance(next)) { output.setDistance(next, alt); output.setPrevious(next, current); } } } return output; }
Dijkstra { public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) { final DijkstraOutput<NODE> output = initializeOutput(graph, start); final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes()); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance)); unprocessed.remove(current); for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) { final NODE next = entry.getKey(); final EDGE edgeToNext = entry.getValue(); final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext); if (alt < output.getDistance(next)) { output.setDistance(next, alt); output.setPrevious(next, current); } } } return output; } }
Dijkstra { public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) { final DijkstraOutput<NODE> output = initializeOutput(graph, start); final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes()); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance)); unprocessed.remove(current); for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) { final NODE next = entry.getKey(); final EDGE edgeToNext = entry.getValue(); final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext); if (alt < output.getDistance(next)) { output.setDistance(next, alt); output.setPrevious(next, current); } } } return output; }  }
Dijkstra { public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) { final DijkstraOutput<NODE> output = initializeOutput(graph, start); final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes()); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance)); unprocessed.remove(current); for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) { final NODE next = entry.getKey(); final EDGE edgeToNext = entry.getValue(); final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext); if (alt < output.getDistance(next)) { output.setDistance(next, alt); output.setPrevious(next, current); } } } return output; }  static DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter); }
Dijkstra { public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) { final DijkstraOutput<NODE> output = initializeOutput(graph, start); final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes()); while (!unprocessed.isEmpty()) { final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance)); unprocessed.remove(current); for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) { final NODE next = entry.getKey(); final EDGE edgeToNext = entry.getValue(); final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext); if (alt < output.getDistance(next)) { output.setDistance(next, alt); output.setPrevious(next, current); } } } return output; }  static DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter);  }