Objective:

Implement Johnson's algorithm to solve the all$-$pairs shortest path problem in a given graph. Use Java programming language.

Background:

Johnson's algorithm is a solution to finding the shortest paths between all pairs of vertices in a weighted graph. It combines Dijkstra's algorithm with some pre$-$processing steps to handle negative edge weights.

Task:

Your task is to implement Johnson's algorithm. You have the flexibility to use the provided Dijkstra's algorithm implementation. Additionally, your program shall get the graph data from the user.

Implementation Guidelines:

$1.$ Input: The user will provide the graph input in the following format: the first line contains two space$-$separated integers: V: The number of vertices in the graph, and E: The number of edges in the graph. The next E lines represent the edges, with each line containing three space$-$separated integers: u: The source vertex, v: The destination vertex, and w: The weight of the edge. The number of vertices $($V$)$ and edges $($E$)$ must be positive integers. Vertex indices must be in the range $[0,$ V$-1].$ Edge weights $($w$)$ can be positive, negative, or zero. An example input is here:

$68$

$023$

$035$

$23-2$

$343$

$45-4$

$354$

$256$

Make sure to represent the given graph using an appropriate data structure. You can use an adjacency list, matrix, or any other suitable representation. Implement Dijkstra's algorithm as a subroutine within Johnson's algorithm and ensure that it correctly calculates the shortest paths from a given source vertex to all other vertices. Implement the Bellman$-$Ford algorithm as a pre$-$processing step in Johnson's algorithm.

Final Output: Provide the implementation that outputs the shortest paths between all pairs of vertices in the given graph.