BF

import java.util.ArrayList;
import java.util.Arrays;

public class Ford {
    private int[][] adjacencyMatrix;

    public Ford(int totalNodes) {
        adjacencyMatrix = new int[totalNodes][totalNodes];
    }

    public void addConnection(int node1, int node2, int weight) {
        if (node1 >= 0 && node1 < adjacencyMatrix.length &&
            node2 >= 0 && node2 < adjacencyMatrix.length) {
            adjacencyMatrix[node1][node2] = weight;
            adjacencyMatrix[node2][node1] = weight;
        } else {
            System.out.println("Invalid nodes");
        }
    }

    public void printAdjacencyMatrix() {
        for (int i = 0; i < adjacencyMatrix.length; i++) {
            for (int j = 0; j < adjacencyMatrix[i].length; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public void bellmanFord() {
        for (int sourceNode = 0; sourceNode < adjacencyMatrix.length; sourceNode++) {
            int[] distances = new int[adjacencyMatrix.length];
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[sourceNode] = 0;

            ArrayList<ArrayList<Integer>> shortestPaths = new ArrayList<>();
            for (int i = 0; i < adjacencyMatrix.length; i++) {
                shortestPaths.add(new ArrayList<>());
            }

            for (int i = 0; i < adjacencyMatrix.length - 1; i++) {
                for (int u = 0; u < adjacencyMatrix.length; u++) {
                    for (int v = 0; v < adjacencyMatrix.length; v++) {
                        if (adjacencyMatrix[u][v] != 0) {
                            if (distances[u] != Integer.MAX_VALUE && distances[u] + adjacencyMatrix[u][v] < distances[v]) {
                                distances[v] = distances[u] + adjacencyMatrix[u][v];
                                shortestPaths.get(v).clear();
                                shortestPaths.get(v).addAll(shortestPaths.get(u));
                                shortestPaths.get(v).add(v);
                            }
                        }
                    }
                }
            }

            System.out.println("Shortest paths from node " + sourceNode + ":");
            for (int i = 0; i < distances.length; i++) {
                System.out.println("Node " + i + ": Distance = " + distances[i] + ", Path = " + shortestPaths.get(i));
            }
            System.out.println();
        }
    }

    public void bellmanFord_() {
        for (int sourceNode = 0; sourceNode < adjacencyMatrix.length; sourceNode++) {
            int[] distances = new int[adjacencyMatrix.length];
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[sourceNode] = 0;

            for (int i = 0; i < adjacencyMatrix.length - 1; i++) {
                for (int u = 0; u < adjacencyMatrix.length; u++) {
                    for (int v = 0; v < adjacencyMatrix.length; v++) {
                        if (adjacencyMatrix[u][v] != 0) {
                            if (distances[u] != Integer.MAX_VALUE && distances[u] + adjacencyMatrix[u][v] < distances[v]) {
                                distances[v] = distances[u] + adjacencyMatrix[u][v];
                            }
                        }
                    }
                }
            }

            System.out.println("Shortest distances from node " + sourceNode + ":");
            for (int i = 0; i < distances.length; i++) {
                System.out.println("Node " + i + ": " + distances[i]);
            }
            System.out.println();
        }
    }

    public void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        Ford graph = new Ford(12);

        graph.addConnection(0, 1, 1);

        graph.addConnection(1, 11, 1);
        graph.addConnection(1, 5, 4);
        graph.addConnection(1, 4, 1);

        graph.addConnection(2, 8, 1);
        graph.addConnection(2, 5, 1);

        graph.addConnection(5, 6, 1);

        graph.addConnection(11, 8, 1);

        graph.addConnection(6, 3, 1);
        graph.addConnection(6, 4, 1);

        graph.addConnection(4, 7, 1);

        graph.addConnection(7, 9, 1);

        graph.addConnection(9, 10, 1);
        graph.addConnection(9, 3, 1);

        graph.addConnection(10, 3, 1);


        System.out.println();

        graph.bellmanFord();


    }

}