Graph Algorithms

Shortest Paths

Dijkstra for non-negative weights, Bellman-Ford when edges can be negative, Floyd-Warshall for all pairs at once — the right algorithm is decided by the sign of the weights and how many sources you need.

Unweighted graph: plain BFS already gives shortest paths by edge count
Dijkstra: greedy, priority-queue driven, O((V+E) log V) — but silently wrong with negative edge weights
Bellman-Ford: relax every edge V−1 times, O(VE) — handles negative weights and detects negative cycles
Floyd-Warshall: O(V³) dynamic program over all pairs — best when you need every-source-to-every-sink distances
Both Dijkstra and Prim's MST share the same priority-queue-driven greedy shape, but they optimize different things

Dijkstra with a PriorityQueue

static int[] dijkstra(List<List<int[]>> adj, int source) {   // adj.get(u) -> {v, weight} pairs
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p[1]));
    pq.add(new int[]{source, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue;          // stale entry, a cheaper path was already found
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.add(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

Choosing a shortest-path algorithm
Algorithm	Handles negative weights	Complexity	Answers
BFS	n/a (unweighted)	O(V + E)	single-source
Dijkstra	no	O((V+E) log V)	single-source
Bellman-Ford	yes, detects negative cycles	O(VE)	single-source
Floyd-Warshall	yes (no negative cycles)	O(V³)	all-pairs