BFS_DJS_Matrix.java

package davex;

import java.util.Objects;

/**
 * The MATRIX Class for storing and operating weighted undirected grid
 * @author Dong Fang
 */
public class Matrix {
    private int mSize;
    private int[][] mMatrix;
    private static final int INF = Integer.MAX_VALUE;   // INFINITE value

    /**
     * Init the matrix
     * @param pSize
     */
    public Matrix(int pSize){
        mSize = (int) Math.pow(pSize, 2);
        mMatrix = new int[mSize][mSize];
    }

    /**
     * connect two point with weight and boundary check
     * @param X
     * @param Y
     * @param Weight
     * @throws Exception
     */
    public void connect(String X, String Y, String Weight) throws Exception {
        if(Integer.parseInt(X) - 1 < 0 || Integer.parseInt(Y) - 1 < 0) throw new Exception("Out of Boundary");
        if(Integer.parseInt(X) - 1 > mSize || Integer.parseInt(Y) - 1 > mSize) throw new Exception("Out of Boundary");
        mMatrix[Integer.parseInt(X) - 1][Integer.parseInt(Y) - 1] = Integer.parseInt(Weight);
        mMatrix[Integer.parseInt(Y) - 1][Integer.parseInt(X) - 1] = Integer.parseInt(Weight);
    }

    /**
     * Breadth First Search Algorithm
     * @param pStartPoint start point
     * @param pEndPoint end point
     * @return result
     */
    public String BreadthFirstSearch(String pStartPoint, String pEndPoint){
        if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;

        int[] edgeTo = new int[mSize];
        boolean[] marked = new boolean[mSize];
        for (int i = 0; i < mSize;i++) edgeTo[i] = -1;  // init the edgeTo, set -1

        Queue<Integer> queue = new Queue<Integer>();
        int startPoint = Integer.parseInt(pStartPoint) - 1;
        int endPoint = Integer.parseInt(pEndPoint) - 1;

        marked[startPoint] = true;    // mark the start point

        queue.enqueue(startPoint);
        while (!queue.isEmpty()){
            int v = queue.dequeue();
            for (int i = 0; i < mSize; i++){
                if(mMatrix[i][v] != 0){
                    if(!marked[i]){
                        // if marked, then it means duplicate
                        // if not, then it means unvisited and mark it
                        edgeTo[i] = v;
                        marked[i] = true;
                        queue.enqueue(i);
                    }
                }
            }
        }
        int i = endPoint;
        String result = "";
        while (edgeTo[i] != startPoint){
            if(edgeTo[i] == -1){
                result = "-1\t";
                break;
            }
            int num = edgeTo[i] + 1;
            result = num + "\t" + result;
            i = edgeTo[i];
        }
        return pStartPoint + "\t" + result + pEndPoint;
    }


    /**
     * Dijkstra Search Algorithm
     * @param pStartPoint start point
     * @param pEndPoint end point
     * @return result
     */
    public String dijkstraSearch(String pStartPoint, String pEndPoint){

        if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;
        int[] distTo = new int[mSize];
        int[] previous = new int[mSize];
        boolean[] visited = new boolean[mSize];

        int startPoint = Integer.parseInt(pStartPoint) - 1;
        int endPoint = Integer.parseInt(pEndPoint) - 1;

        // init the status
        for (int i = 0; i < mSize; i++) {
            visited[i] = false;         // all the points are not visited
            distTo[i] = INF;            // set paths of all the point are INFINITE
            previous[i] = startPoint;   // every point's parent is the start point
        }

        distTo[startPoint] = 0;         // shortest path(weight) from the start point
        previous[startPoint] = -1;      // parent of the point
        visited[startPoint] = true;     // set the start point is visited

        int current = startPoint;       // init the current point
        for (int i = 1; i < mSize; i++){
            // core of Dijkstra Search Algorithm
            int min = INF;
            for (int j = 0; j< mSize; j++){
                if(!visited[j] && distTo[j] < min){
                    // find the current minimum path and the unvisited point
                    min = distTo[j];
                    current = j;
                }
            }
            visited[current] = true;    // set the point is visited
            for (int v = 0; v < mSize; v++){
                if(mMatrix[current][v] > 0 && distTo[v] > distTo[current] + mMatrix[current][v]){
                    // calculate the path that the Current point to Adjacent point
                    // if the path is shorter than before, then overwrite it
                    distTo[v] = distTo[current] + mMatrix[current][v];
                    previous[v] = current;
                }
            }
        }

        int i = endPoint;
        String result = "";
        while (previous[i] != startPoint || distTo[i] == INF){
            // output the path
            if(previous[i] == -1 || distTo[i] == INF){
                result = "-1\t";
                break;
            }
            int num = previous[i] + 1;
            result = num + "\t" + result;
            i = previous[i];
        }
        return pStartPoint + "\t" + result + pEndPoint;
    }

}