SSP: Dijkstra's Algorithm

This algorithm solves the single-source shortest-path problem s-ss-p problem on a weighted, directed graph for the case in which all edge weights are non negative. A good implementation of this algorithm is faster than BF.

This algorithm maintains a set S of vertices whose final s-p weights from the source s have already been determined. The algorithm repeatedly selects the vertex u $\in$ V-S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u.

DIJKSTRA (G,w,s)
    // set d to infinite and parent to null except for s which has d set to 0.
    initializeSingleSource(G,s)

    // priority queue keyed by d values.
    // Note that whenever d changes (during relax), the Q must sort itself accordingly.
    Q = G.V  
  
    while Q is not empty
        u = Q.getMin() 
        for v in G.Adj[u]
            // if d[v] > d[u] + w[u,v], update v and reorder Q
            relax (u,v,w)

We say that it uses a greedy strategy because it chooses the lightest (or closest) vertex in V-S to add to set S. While greedy algorithm often do not yield optimal result due to their greedy strategies, this does because each time we add a vertex u to S we have that the u.d = $\delta(s,u)$

Finally. note that if we run this algorithm on a weighted directed graph G with a non-negative weight function w and source s, then at termination, the predecessor subgraph $G_p$ is a shortest-path tree rooted at s.

Java impl

import java.util.*;

class Graph {
    private final Map<String, List<Edge>> adjList = new HashMap<>();

    static class Edge {
        String target;
        int weight;

        Edge(String target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    static class NodeDistance {
        String node;
        int dist;

        NodeDistance(String node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    public void addEdge(String source, String target, int weight) {
        adjList.computeIfAbsent(source, k -> new ArrayList<>()).add(new Edge(target, weight));
        adjList.computeIfAbsent(target, k -> new ArrayList<>()).add(new Edge(source, weight)); // For undirected graph
    }

    public Map<String, Integer> dijkstra(String start) {
        // Priority queue to pick the node with the smallest distance
        PriorityQueue<NodeDistance> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dist));
        Map<String, Integer> distances = new HashMap<>();

        for(String node : adjList.keySet()) {
            distance.put(node, Integer.MAX_VALUE);
        }
        distances.put(start, 0);

        // Start with the starting node
        pq.add(new NodeDistance(start, 0));

        while (!pq.isEmpty()) {
            NodeDistance curr = pq.poll();
            String currNode = curr.node;
            int currDist = curr.dist;

            // Skip if the node is already visited
            if (currDist > distances.get(currNode)) continue;

            // Process neighbors
            for (Edge neighbor : adjList.getOrDefault(currentNode, Collections.emptyList())) {
                int newDist = currDist + neighbor.weight;

                // If a shorter path is found
                if (newDist < distances.get(neighbor.target)) {
                    distances.put(neighbor.target, newDist);
                    pq.add(new NodeDistance(neighbor.target, newDist));
                }
            }
        }
        return distances;
    }
}