Java O(N^3) Floyd–Warshall
Intuition\nTo solve this problem, we can use the Floyd-Warshall algorithm to find the shortest paths between all pairs of nodes in a graph.\n# Approach\nInitial
# Intuition\nTo solve this problem, we can use the Floyd-Warshall algorithm to find the shortest paths between all pairs of nodes in a graph.\n# Approach\nInitialize a matrix to represent the graph, setting all distances to a large value except for the diagonal, which is set to 0.\nSet the distance between adjacent nodes to 1.\nIf the given nodes x and y are different, set their distance to 1 as well.\nApply the Floyd-Warshall algorithm to update the shortest distances between all pairs of nodes.\nCount the number of paths of each length in the resulting matrix.\n# Complexity\n- Time complexity:\nThe time complexity of the Floyd-Warshall algorithm is O(n^3), where n is the number of nodes.\n\n\n- Space complexity:\nThe space complexity is also O(n^2) to store the adjacency matrix.\n\n\n# Code\n```\nclass Solution {\n    public int[] countOfPairs(int n, int x, int y) {\n        int[][] mat = new int[n][n];\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tfor (int j = 0; j < mat.length; j++) {\n\t\t\t\tmat[i][j] = 99999;\n\t\t\t}\n\t\t}\n\t\tfor (int i = 0; i < n-1; i++) {\n\t\t\tmat[i][i] = 0;\n\t\t\tmat[i][i+1] = 1;\n\t\t\tmat[i+1][i] = 1;\n\t\t}\n\t\tmat[mat.length-1][mat.length-1] = 0;\n\t\tif(x!=y)\n\t\t{\n\t\t\tmat[x-1][y-1] = 1;\n\t\t\tmat[y-1][x-1] = 1;\n\t\t}\n\t\tfor (int i = 0; i < mat.length; i++) {\n\t\t\tfor (int j = 0; j < mat.length; j++) {\n\t\t\t\tfor (int k = 0; k < mat.length; k++) {\n\t\t\t\t\tmat[j][k] = Math.min(mat[j][k], mat[j][i] + mat[i][k]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t//System.out.println("floyd applied");\n\t\tint[] res = new int[n];\n\t\tfor (int i = 0; i < mat.length; i++) {\n\t\t\tfor (int j = 0; j < mat.length; j++) {\n\t\t\t\t// System.out.print(mat[i][j] + " ");\n\t\t\t\tif(mat[i][j]==0)continue;\n\t\t\t\tres[mat[i][j]-1]++;\n\t\t\t}\n\t\t}\n        return res;\n    }\n}\n```
['Java']