Theory

Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree.

Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root.

We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree.

At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.

Algorithm

1. Create visited set, weghts and previous maps to keep 
		weights so far and previous node.
		Set<GraphNode<T>> visited = new HashSet<>();
    Map<GraphNode<T>, Integer> weights = new LinkedHashMap<>(); //weights so far
    Map<GraphNode<T>, GraphNode<T>> previous = new HashMap<>(); // previous node

2. Create min heap of nodes ranked by smallest weight first. Add root to weights and queue.
   PriorityQueue<GraphNode<T>> queue = new PriorityQueue<>((a, b) -> weights.get(a) - weights.get(b));

3. While queue is not empty, poll node, take distance so far, 
	 traverse over neighbors, add distance to edge weight 
	 and if it's less than distance in map put, put in map and update prevous.
   Don't forget to update visited.
4. Print weights.

Implementation

Adjacency Matrix Implementation

public <T> String findShortestPath(GraphAdjacencyMatrix<T> graph, GraphNode<T> root) {
    Set<GraphNode<T>> visited = new HashSet<>();
    Map<GraphNode<T>, Integer> weights = new LinkedHashMap<>(); //weights so far
    Map<GraphNode<T>, GraphNode<T>> previous = new HashMap<>(); // previous node

    PriorityQueue<GraphNode<T>> queue = new PriorityQueue<>((a, b) -> weights.get(a) - weights.get(b));
    weights.put(root, 0);
    queue.add(root);

    while (!queue.isEmpty()) {
        GraphNode<T> source = queue.poll();
        int distanceSoFar = weights.get(source);
        Map<GraphNode<T>, Integer> neighbors = graph.getNeighbors(source);
        for (Map.Entry<GraphNode<T>, Integer> destWeight : neighbors.entrySet()) {
            GraphNode<T> destination = destWeight.getKey();
            int distance = distanceSoFar + destWeight.getValue();
            if (weights.getOrDefault(destination, Integer.MAX_VALUE) > distance) {
                weights.put(destination, distance);
                previous.put(destination, source);
            }

            if (!visited.contains(destination)) {
                visited.add(destination);
                queue.add(destination);
            }
        }
        visited.add(source);
    }

    return toString(weights);
}

Complexities

Time complexity O(ElogV)

Space complexity O(V)

Adjacency List Implementation

public <T> String findShortestPath(WeightedGraphAdjacencyList<T> graph, GraphNode<T> root) {
    Set<GraphNode<T>> visited = new HashSet<>();
    Map<GraphNode<T>, Integer> weights = new LinkedHashMap<>(); //weights so far
    Map<GraphNode<T>, GraphNode<T>> previous = new HashMap<>(); // previous node

    PriorityQueue<GraphNode<T>> queue = new PriorityQueue<>((a, b) -> weights.get(a) - weights.get(b));
    weights.put(root, 0);
    queue.add(root);

    while (!queue.isEmpty()) {
        GraphNode<T> source = queue.poll();
        int distanceSoFar = weights.get(source);
        var edges = graph.getEdges(source);
        for (var edge : edges) {
            GraphNode<T> destination = edge.getDest();
            int distance = distanceSoFar + edge.getWeight();
            if (weights.getOrDefault(destination, Integer.MAX_VALUE) > distance) {
                weights.put(destination, distance);
                previous.put(destination, source);
            }

            if (!visited.contains(destination)) {
                visited.add(destination);
                queue.add(destination);
            }
        }
        visited.add(source);
    }

    return toString(weights);
}

Complexities

Time complexity O(V^2)

Space complexity O(V)