Bellman-Ford and Floyd-Warshall

1.Bellman-Ford

Set dist[src] = 0. Repeat V − 1 times: for every edge (u, v, w), relax it. A shortest path has at most V − 1 edges, so after that many rounds all distances are final, even with negative edges. If a further round still improves something, there's a negative cycle reachable from the source (distances can drop forever).

To limit a path to at most k edges, run exactly k rounds and relax from a copy of the previous round's distances, so one round can't chain several edges together. Cost: O(V × E).

2.Floyd-Warshall

d[i][j] starts as the direct edge weight (0 on the diagonal, ∞ if none). For each intermediate k, for every pair, d[i][j] = min(d[i][j], d[i][k] + d[k][j]). After k has gone through all nodes, every pair has its shortest distance. O(V³) time, so use it for V up to a few hundred.

public class Main {
    public static void main(String[] args) {
        int n = 4, INF = 1_000_000_000;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = i == j ? 0 : INF;
        int[][] edges = {{0, 1, 5}, {0, 3, 10}, {1, 2, 3}, {2, 3, 1}};   // directed
        for (int[] e : edges) d[e[0]][e[1]] = e[2];

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

        for (int[] row : d) {
            StringBuilder sb = new StringBuilder();
            for (int x : row) sb.append(x >= INF ? "-" : String.valueOf(x)).append(' ');
            System.out.println(sb.toString().trim());
        }
    }
}

0 5 8 9
- 0 3 4
- - 0 1
- - - 0

3.Which one?

Non-negative weights, one source: Dijkstra. Unweighted: BFS. Weights 0/1: 0-1 BFS. Negative weights, or a limit on the number of edges: Bellman-Ford. All pairs on a small graph: Floyd-Warshall. A DAG (even with negative weights): DP in topological order (Module 24).