Java (I use Eclipse)

Implement bellman ford(int s) and dijkstra(int s). Please make sure the program works. Screenshots will be help full. Fill in missing funtions in the provided skeleton.

public class Graph {

int n;

int[][] A;

int[] d; //shortest distance

/**

* @param args

*/

public Graph () {

}

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

n = _n;

A = _A;

d = new int[n];

}

public void initialize_single_source(int s) {

for (int i = 0; i < n; 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 < n; 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}

};

Graph g1 = new Graph(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}

};

Graph g2 = new Graph(n, B);

g2.dijkstra(0);

g2.display_distance();

}

}