Longest Path Algorithm (Java Code)

The longest path algorithm is used to find the maximum length of a given graph. The maximum length may be measured by the maximum number of edges or the sum of the weights in a weighted graph. Following is a sample java code to find the Longest Path. It has two classes. CreateMatrix.java class to create the matrix and LongestPath.java to find the Longest Path to the created matrix. 

Download Source From Here.. DOWNLOAD

/********************* LongestPathAlgo.java ********************/ 
class LongestPathAlgo {

    public static void main(String[] args) {

        int length = 13;//length of the 2-D array
        int adjMatrix[][] = new int[length][length];
        CreateMatrix cm = new CreateMatrix();
        cm.createMatrix(length);
        adjMatrix = cm.readMatrix(adjMatrix);

        long starttime = System.nanoTime();
        LongestPathAlgo lpa = new LongestPathAlgo();
        boolean visited[] = new boolean[adjMatrix.length];
        lpa.initialize(adjMatrix, visited);
        int max = lpa.longestPath(0, visited, adjMatrix);
        long runtime = System.nanoTime()-starttime;
        System.out.println("Runtime =" + runtime +" nano seconds");
        System.out.println("Longest Path Length = "+max);
    }

    public void initialize(int adjMatrix[][], boolean visited[]) {
        for (int u = 0; u < adjMatrix.length; u++) {
            visited[u] = false;
        }
    }

    int longestPath(int vertex, boolean visited[], int adjMatrix[][]) {
        int dist, max = 0;
        visited[vertex] = true;

        for (int u = 0; u < adjMatrix[vertex].length; u++) {
            if (adjMatrix[vertex][u] != -1) {
                if (!visited[u]) {
                    dist = adjMatrix[vertex][u] + longestPath(u, visited, adjMatrix);
                    if (dist > max) {
                        max = dist;
                    }
                }
            }
        }
        visited[vertex] = false;
        return max;
    }
}

/********************* CreateMatrix.java ********************/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;


public class CreateMatrix {

    public void createMatrix(int length) {
        Random ran = new Random();
        FileWriter fw;
        try {
            File file = new File("matrix.txt");
            fw = new FileWriter(file);
            BufferedWriter bw = new BufferedWriter(fw);
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if (i == j) {
                        bw.write("" + -1);
                    } else {
                        bw.write("" + (i+j));
                    }
                    bw.write("@");
                }
                bw.newLine();
            }
            for (int i = 0; i < length; i++) {
            }
            bw.close();
            fw.close();
        } catch (IOException ex) {
            System.out.println("File Not Found");
          }

    }

    public int[][] readMatrix(int adjMatrix[][]) {

        try {
            File file = new File("matrix.txt");
            FileReader fr = new FileReader(file);
            BufferedReader br = new BufferedReader(fr);
            int i = 0;
            while (br.ready()) {
                String line = br.readLine();
                String array[] = line.split("@");
                for (int j = 0; j < adjMatrix.length; j++) {
                    adjMatrix[i][j] = Integer.parseInt(array[j]);
                }
                i++;
            }
        } catch (Exception e) {
            System.out.println("Error " + e);
        }
        return adjMatrix;
    }
}