Java Program to Find the Longest Path in a Directed Acyclic Graph

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.sanfoundry.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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Check if a Given Graph must Contain Hamiltonian Cycle or Not

» Next - Java Program to Solve TSP using Minimum Spanning Trees

Related Posts:

Recommended Articles: