Pages

Subscribe:

Ads 468x60px

Sunday, August 26, 2012

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;
    }
}

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Hello,

    Thanks for sharing this algorithm. Could you please tell us how can we get the final longest path(the visited vertices) from this algorithm ?

    yours

    ReplyDelete