BFS using shortest path between 2 nodes in adjacent matrix

import java.util.ArrayList;

public class BfsData

{

// Graph adjacency matrix (unweighted graph)

static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3

{0,0,0,33,0}, // 1->2, 1->3

{0,0,0,22,0}, // 2->4

{0,0,0,0,3}, // 3->2, 3->4

{0,0,0,0,0} // 4->1

};

//--------------------------------------------------------------

public static void main (String[] args)

{

ArrayList<Integer> Start = new ArrayList();

Start.add(0); // The start node

ArrayList<ArrayList> Queue = new ArrayList();

Queue.add(Start); // inserted in the initial queue of paths as [[Start]]

// Use one search at a time (comment the others)

// ArrayList Path = depth_first(Queue,4); // Depth first search

ArrayList Path = breadth_first(Queue,4); // Breadth first search

// ArrayList Path = uni_cost(Queue,4); // Uniform cost search

System.out.println(Path);

// System.out.println(path_cost(Path));

}

//--------------------------------------------------------------

// Adds to the queue paths extending the first path in the queue

public static ArrayList<ArrayList> extend (ArrayList<Integer> Path)

{

ArrayList<ArrayList> NewPaths = new ArrayList();

for (int i=0;i<graph.length;i++)

if (graph[Path.get(0)][i]>0 && !Path.contains(i))

{

ArrayList Path1 = (ArrayList)Path.clone();

System.out.println(Path1+"=====jjjj====");

Path1.add(0,i);

NewPaths.add(Path1);

System.out.println(NewPaths+"====NewPaths==");

}

return NewPaths;

}

//--------------------------------------------------------------

// Appends y to x and returns the result in a new ArrayList z

public static ArrayList append (ArrayList x, ArrayList y)

{

ArrayList z = (ArrayList)x.clone();

for (int i=0;i<y.size();i++) z.add(y.get(i));

return z;

}

//--------------------------------------------------------------

// Breadth first search for a path from Start to Goal.

// The Start node must be in the initial queue of paths as [[Start]]

public static ArrayList<ArrayList> breadth_first(ArrayList<ArrayList> Queue, int Goal)

{

if (Queue.size()==0) return Queue; // path not found

if ((Integer)Queue.get(0).get(0) == Goal) // if Goal is the first node in the first path

return Queue.get(0); // return path

else // replace the first path with all its extensions and put them at the end of the queue

{

ArrayList<ArrayList> NewPaths = extend(Queue.get(0));

Queue.remove(0);

return breadth_first(append(Queue,NewPaths),Goal);

}

}

//--------------------------------------------------------------

public static int path_cost (ArrayList<Integer> Path)

{

int cost = 0;

for (int i=0;i<Path.size()-1;i++)

cost = cost + graph[Path.get(i+1)][Path.get(i)];

return cost;

}

public static void sort(ArrayList<ArrayList> Queue)

{

int out, in;

for(out=Queue.size()-1; out>=1; out--)

for(in=0; in<out; in++)

if( path_cost(Queue.get(in)) > path_cost(Queue.get(in+1)) )

swap(Queue, in, in+1);

}

//--------------------------------------------------------------

private static void swap(ArrayList<ArrayList> a, int one, int two)

{

ArrayList<Integer> temp = a.get(one);

a.set(one,a.get(two));

a.set(two,temp);

}

}

As Above program, in that place i will directly send the adjacent matrix file through file reader, that file is

a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad

a 0 3 0 0 2 1 0 0 0 2 0 0 42 1 0 0 11 0 6 0 0 0 0 43 0 36 0 23 0 24

b 0 0 0 33 0 25 0 36 0 0 0 3 24 0 2 0 0 47 0 0 8 3 0 17 0 0 0 0 4 20

c 0 0 0 22 0 12 16 0 34 0 0 7 0 2 0 0 0 0 0 16 0 13 0 0 0 25 0 0 0 10

d 0 0 0 0 3 4 0 0 0 0 5 12 8 0 0 0 2 12 0 0 3 0 0 24 32 0 0 0 0 0

e 0 0 0 0 0 0 1 4 0 12 0 20 0 0 0 0 13 0 1 16 0 0 0 0 2 4 5 6 0 0

f 0 0 0 0 0 0 1 0 2 0 13 8 0 0 1 0 4 0 0 8 0 0 0 12 1 0 0 0 1 0

g 0 0 0 0 0 0 0 1 12 0 3 5 0 2 0 3 0 0 1 2 0 0 0 5 10 0 1 2 1 0

h 0 0 0 0 0 0 0 0 3 34 5 0 0 0 0 0 1 12 1 0 0 0 0 0 2 0 3 0 1 0

i 0 0 0 0 0 0 0 0 0 1 2 0 0 42 0 1 5 34 1 0 0 1 0 0 0 0 0 1 0 0

j 0 0 0 0 0 0 0 0 0 0 0 1 22 0 11 0 25 41 0 0 0 0 0 0 0 1 0 1 0 4

k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 23 0 12 0 2 0 3 0 1 0 0 1 1

l 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 19 12 0 0 1 0 0 0 0 2 0 4 0 2 0

m 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5 1 0 0 0 0 3 0 2 0 0 0 0 0 0

n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 23 0 5 32 0 50 0 1 0 3 4

o 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 0 0 2 53 0 2 21 3 0 0 0 1

p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 24 0 0 12 38 0 2 0 0

q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 24 0 0 24 0 0 12 0 5 0 0 0

r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 12 0 57 0 0 2 0

s 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 24 0 1 0 5 12 0

t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 24 1 6 0 0 1

u 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 1 0 0

v 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 22 1 1 4 0

w 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 38 0 0 5 7 0

x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 5 0 1

y 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 21 0 1

z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1

aa 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0 0

ab 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0

ac 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5

ad 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

"" static private int[][] graph = { {0,3,0,0,2}, // 0->1 0->3

{0,0,0,33,0}, // 1->2, 1->3

{0,0,0,22,0}, // 2->4

{0,0,0,0,3}, // 3->2, 3->4

{0,0,0,0,0} // 4->1

};"" ....in that ""---"" i will set that above matrix file ?how to set that file??