Dijkstra’s Shortest Path Algorithm

Single-source shortest path algorithm for graphs with non-negative edge weights.

Context

Dijkstra’s algorithm computes the shortest path from a single source to all other vertices in a graph with:

• Weighted edges
• No negative weights

If negative edges exist → this algorithm is incorrect. Use Bellman–Ford instead.

Time complexity depends on implementation:

• This version → O(V² + E) (because of linear scan for minimum)
• With a priority queue → O((V + E) log V)

Core idea

Dijkstra is greedy. At every step:

• Pick the unvisited vertex with the smallest known distance
• “Lock it in” (mark visited)
• Relax its outgoing edges:
  • If going through this vertex gives a shorter path → update distance
• Repeat

Key invariant:

Once a vertex is marked visited, its shortest distance is final.

That works only because weights are non-negative.

Implementation

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
import java.util.Collections;

class DijkstraShortestPath {
    List<Integer> find(GraphEdge[][] graph, int source, int target) {
        var n = graph.length;
        
        var visited = new boolean[n];
        
        var distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        
        var prev = new int[n];
        Arrays.fill(prev, -1);
        
        while(hasUnvisited(visited, distances)) {
            var lo = getLowestUnvisited(visited, distances);
            visited[lo] = true;
            
            for (var edge : graph[lo]) {
                if (!visited[edge.to]) {
                    var distance = distances[lo] + edge.weight;
                    if (distances[edge.to] > distance) {
                        distances[edge.to] = distance;
                        prev[edge.to] = lo;
                    }
                }
            }
        }
        
        if (prev[target] == -1 && target != source) return List.of();
        
        List<Integer> out = new ArrayList<>();
        for (var at = target; at != -1; at = prev[at]) {
            out.add(at);
        }
        
        Collections.reverse(out);
        return out;
    }
    
    private boolean hasUnvisited(boolean[] visited, int[] distances) {
        return IntStream.range(0, visited.length)
            .anyMatch(i -> !visited[i] && distances[i] != Integer.MAX_VALUE);
    }
    
    private int getLowestUnvisited(boolean[] visited, int[] distances) {
        var minIndex = -1;
        var minValue = Integer.MAX_VALUE;
        
        for (var i = 0; i < visited.length; i++) {
            if (!visited[i] && distances[i] < minValue) {
                minIndex = i;
                minValue = distances[i];
            }
        }
        
        return minIndex;
    }
    
    record GraphEdge(int to, int weight) {}
}