Task 1 (50 pts). Implement the bellman ford(int s) function as discussed in Lecture 19 in JAVA.

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 A[i][j] = 0, it means there is no edge between the i-th and j-th node. If A[i][j] 6= 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.

Below is the psescode, and skeleton code to modify for the above question/solution.

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();

}

}

BELLMAN-FORD(G, w,s) INITIALzE-SINGLE-SoURCE(G,s)Key idea: a shortest path contains at most for i= l tolG.VI-1 1 2 3 4 5 nodes that are connected by n-1 edges, so for each destination, relax at most n-1 times. for each edge (u, v) e G.E RELAX(u, v, w) for each edge (u, v) E G.E return FALSE 8 return TRUE