package Graph; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Set; public class PathSearcher { public static List getShortestPath(Graph graph, Vertex start, Vertex end) { if (graph == null || start == null || end == null || !graph.vertexes.contains(start) || !graph.vertexes.contains(end)) { return null; } Map> adjacentEdges = new HashMap<>(); for (Edge edge : graph.edges) { if (adjacentEdges.containsKey(edge.source)) { adjacentEdges.get(edge.source).add(edge); } else { adjacentEdges.put(edge.source, new ArrayList(Arrays.asList(edge))); } } Set visitedVertexes = new HashSet<>(); PriorityQueue unvisitedVertex = new PriorityQueue<>(); start.distance = 0; unvisitedVertex.add(start); while (!unvisitedVertex.isEmpty()) { Vertex shortestPathVertex = unvisitedVertex.poll(); if (shortestPathVertex.equals(end)) { break; } List edges = adjacentEdges.get(shortestPathVertex); for (Edge edge : edges) { if (!visitedVertexes.contains(edge.destination) && shortestPathVertex.distance + edge.weight < edge.destination.distance) { edge.destination.distance = shortestPathVertex.distance + edge.weight; edge.destination.prev = shortestPathVertex; unvisitedVertex.add(edge.destination); } } visitedVertexes.add(shortestPathVertex); } List result = new ArrayList<>(); Vertex current = end; while (current != null) { result.add(current); current = current.prev; } Collections.reverse(result); return result; } }