Java Program to Find the Longest Path in a DAG

This is a java program to find longest path in DAG.

Here is the source code of the Java Program to Find the Longest Path in a DAG. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.maixuanviet.hardgraph;
 
import java.util.Scanner;
import java.util.Vector;
 
class Node
{
    int             name; // node ID, started from 0 to n-1
    Vector<Integer> preds; // predecessors (String)
    Vector<Integer> neibs; // neighbors (String)
    Vector<Integer> backs; // backward edges -node is end vertex (Integer)
    Vector<Integer> fors; // forward edges -node is start vertex (Integer)
    int             pNode; // previous node on the augmenting path
    int             pEdge; // from which edge this node comes on the augmenting
                           // path
 
    public Node(int id)
    {
        name = id;
        backs = new Vector<Integer>();
        fors = new Vector<Integer>();
        pNode = -1;
        pEdge = -1;
    }
}
 
class Edge
{
    int name;    // edge ID, started from 0 to n-1
    int start;   // start vertex of this edge
    int end;     // end vertex of this edge
    int direct;  // forwards (+1) or backwards (-1) on augmenting path
                  // if 0 then not part of augmenting path
    int capacity; // capacity
    int flow;    // current flow
 
    public Edge(int id)
    {
        name = id;
        start = -1;
        end = -1;
        direct = 0; // default is neither
        capacity = 0;
        flow = 0;
    }
 
    public String toString()
    {
        return name + ": s=" + start + " e=" + end + " d=" + direct;
    }
}
 
public class LongestPathinDAG
{
    int    n;                      // number of nodes
    int    target;                 // destination node
    int    minLength;              // the minimal length of each path
    Node[] v;                      // used to store Nodes
    Edge[] e;                      // used to store Edges
    int[]  path;                   // used to store temporary path
    int    length       = 0;       // length of the path
    int    distance     = 0;       // distance of the path
    int[]  bestPath;               // used to store temporary path
    int    bestLength   = 0;       // length of the longest path
    int    bestDistance = -1000000; // distance of the longest path
    int[]  visited;                // used to mark a node as visited if set as
                                    // 1
 
    public LongestPathinDAG()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of vertices: ");
        n = sc.nextInt();
        System.out.println("Enter the number of edges: ");
        int m = sc.nextInt();
        v = new Node[n];
        e = new Edge[m];
        System.out.println(n + " nodes and " + m + " edges.");
        for (int i = 0; i < n; i++)
            v[i] = new Node(i);
        int i = 0;
        while (i < e.length)
        {
            Edge edge = new Edge(i);
            int sVal = sc.nextInt();
            edge.start = sVal;// sc.nextInt();
            int eVal = sc.nextInt();
            edge.end = eVal;// sc.nextInt();
            edge.capacity = sc.nextInt();
            System.out.println(" edge: " + edge.start + " - " + edge.end
                    + " : " + edge.capacity);
            edge.flow = 0;
            e[i] = edge;
            v[sVal].fors.add(i);
            v[eVal].backs.add(i);
            i++;
            if (i == m)
                break;
        }
        visited = new int[v.length];
        path = new int[v.length];
        bestPath = new int[v.length];
        sc.close();
    }
 
    /*
     * this function looks for a longest path starting from being to end,
     * using the backtrack depth-first search.
     */
    public boolean findLongestPath(int begin, int end, int minLen)
    {
        /*
         * compute a longest path from begin to end
         */
        target = end;
        bestDistance = -100000000;
        minLength = minLen;
        dfsLongestPath(begin);
        if (bestDistance == -100000000)
            return false;
        else
            return true;
    }
 
    private void dfsLongestPath(int current)
    {
        visited[current] = 1;
        path[length++] = current;
        if (current == target && length >= minLength)
        {
            if (distance > bestDistance)
            {
                for (int i = 0; i < length; i++)
                    bestPath[i] = path[i];
                bestLength = length;
                bestDistance = distance;
            }
        }
        else
        {
            Vector<Integer> fors = v[current].fors;
            for (int i = 0; i < fors.size(); i++)
            {
                Integer edge_obj = (Integer) fors.elementAt(i);
                int edge = edge_obj.intValue();
                if (visited[e[edge].end] == 0)
                {
                    distance += e[edge].capacity;
                    dfsLongestPath(e[edge].end);
                    distance -= e[edge].capacity;
                }
            }
        }
        visited[current] = 0;
        length--;
    }
 
    public String toString()
    {
        String output = "v" + bestPath[0];
        for (int i = 1; i < bestLength; i++)
            output = output + " -> v" + bestPath[i];
        return output;
    }
 
    public static void main(String arg[])
    {
        LongestPathinDAG lp = new LongestPathinDAG();
        /*
         * find a longest path from vertex 0 to vertex n-1.
         */
        if (lp.findLongestPath(0, lp.n - 1, 1))
            System.out.println("Longest Path is " + lp
                    + " and the distance is " + lp.bestDistance);
        else
            System.out.println("No path from v0 to v" + (lp.n - 1));
        /*
         * find a longest path from vertex 3 to vertex 5.
         */
        if (lp.findLongestPath(3, 5, 1))
            System.out.println("Longest Path is " + lp
                    + " and the distance is " + lp.bestDistance);
        else
            System.out.println("No path from v3 to v5");
        /*
         * find a longest path from vertex 5 to vertex 3.
         */
        if (lp.findLongestPath(lp.n - 1, 3, 1))
            System.out.println("Longest Path is " + lp
                    + " and the distance is " + lp.bestDistance);
        else
            System.out.println("No path from v5 to v3");
    }
}

Output:

$ javac LongestPathinDAG.java
$ java LongestPathinDAG
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
6 nodes and 7 edges.
 
0 1 2
 edge: 0 - 1 : 2
1 2 3
 edge: 1 - 2 : 3
1 3 4
 edge: 1 - 3 : 4
3 4 5
 edge: 3 - 4 : 5
4 5 6
 edge: 4 - 5 : 6
5 3 7
 edge: 5 - 3 : 7
5 2 8
 edge: 5 - 2 : 8
Longest Path is v0 -> v1 -> v3 -> v4 -> v5 and the distance is 17
Longest Path is v3 -> v4 -> v5 and the distance is 11
Longest Path is v5 -> v3 and the distance is 7

Related posts:

Java Program to Implement HashTable API
Java Program to Implement SynchronosQueue API
Java Program to Implement Booth Algorithm
Hướng dẫn Java Design Pattern – Memento
Spring Cloud – Securing Services
DistinctBy in the Java Stream API
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Implement ConcurrentLinkedQueue API
Spring Boot - Application Properties
Java Program to Check if a Matrix is Invertible
Spring Boot Tutorial – Bootstrap a Simple Application
Java Program to Implement Control Table
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Generate Random Numbers Using Middle Square Method
Spring MVC Content Negotiation
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Guide to ThreadLocalRandom in Java
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Java Program to Represent Graph Using Adjacency List
Quick Guide to Spring Bean Scopes
Java Program to Describe the Representation of Graph using Adjacency Matrix
Spring WebClient Requests with Parameters
The Java 8 Stream API Tutorial
Java Program to Construct a Random Graph by the Method of Random Edge Selection
How to Get All Spring-Managed Beans?
Implementing a Binary Tree in Java
Extra Login Fields with Spring Security
Hướng dẫn Java Design Pattern – Singleton
Intro to Inversion of Control and Dependency Injection with Spring
Spring Boot - Admin Server
How to Remove the Last Character of a String?
JUnit5 @RunWith