Graph3.java is shown below:

package graph;

public class Graph3 {

int n;

int[][] A;

int[] d; //shortest distance

/**

* @param args

*/

public Graph3 () {

}

public Graph3 (int _n, int[][] _A) {

n = _n;

A = _A;

d = new int[n];

}

public void initialize_single_source(int s) {

for (int i = 0; i

d[i] = Integer.MAX_VALUE;

d[s] = 0;

}

public void relax (int u, int v) {

if (d[v] > (d[u] + A[u][v]))

d[v] = d[u] + A[u][v];

}

public boolean bellman_ford (int s) {

//fill in your program

}

public void dijkstra (int s) {

//fill in your program

}

public void display_distance () {

for (int i = 0; i

System.out.println(i + ": " + d[i]);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int n = 5;

int[][] A = {

{0, 6, 0, 7, 0},

{0, 0, 5, 8, -4},

{0, -2, 0, 0, 0},

{0, 0, -3, 0, 9},

{2, 0, 7, 0, 0}

};

Graph3 g1 = new Graph3(n, A);

g1.bellman_ford(0);

g1.display_distance();

System.out.println("-----------------------");

int[][] B = {

{0, 10, 0, 5, 0},

{0, 0, 1, 2, 0},

{0, 0, 0, 0, 4},

{0, 3, 9, 0, 2},

{7, 0, 6, 0, 0}

};

Graph3 g2 = new Graph3(n, B);

g2.dijkstra(0);

g2.display_distance();

}

}

1 Problem Description Instructions. You are provided one skeleton program named Graph3.java. The source files are available on Canvas in a folder named HW9. Please modify the skeleton code to solve the following tasks. . Task 1 (50 pts). Implement the bellman ford(int s) function as discussed in Lecture 19 Note: You should return an boolean value. . Task 2 (50 pts) Implement the dijkstra(int s) function as discussed in Lecture 20. - Hint 1: We use an adjacent matrix to represent the graph. If AH 0, it means there is no edge between the i-th and j-th node. If A[i][j]0, then it means the weight of the edge between the i-th and j-th node -Hint 2: You do not need to do any operation for the variable in the pseudocode in Task 1 and Task 2. . Task 3 (50 pts (Extra Credit) Implement a function to organize the shortest path for each node as a string. For example, if a node 4's shortest path is 0 2 1 4, you can generate a string variable s-" 2 1 4". Modify the display-distance() function to show the shortest distance and the shortest path for each node. -Hint 1: You definitely need to do operation for the variable in this task. Feel free to add any class member data based on your need