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.

  1.  
  2. package com.sanfoundry.hardgraph;
  3.  
  4. import java.util.Scanner;
  5. import java.util.Vector;
  6.  
  7. class Node
  8. {
  9.     int             name; // node ID, started from 0 to n-1
  10.     Vector<Integer> preds; // predecessors (String)
  11.     Vector<Integer> neibs; // neighbors (String)
  12.     Vector<Integer> backs; // backward edges -node is end vertex (Integer)
  13.     Vector<Integer> fors; // forward edges -node is start vertex (Integer)
  14.     int             pNode; // previous node on the augmenting path
  15.     int             pEdge; // from which edge this node comes on the augmenting
  16.                            // path
  17.  
  18.     public Node(int id)
  19.     {
  20.         name = id;
  21.         backs = new Vector<Integer>();
  22.         fors = new Vector<Integer>();
  23.         pNode = -1;
  24.         pEdge = -1;
  25.     }
  26. }
  27.  
  28. class Edge
  29. {
  30.     int name;    // edge ID, started from 0 to n-1
  31.     int start;   // start vertex of this edge
  32.     int end;     // end vertex of this edge
  33.     int direct;  // forwards (+1) or backwards (-1) on augmenting path
  34.                   // if 0 then not part of augmenting path
  35.     int capacity; // capacity
  36.     int flow;    // current flow
  37.  
  38.     public Edge(int id)
  39.     {
  40.         name = id;
  41.         start = -1;
  42.         end = -1;
  43.         direct = 0; // default is neither
  44.         capacity = 0;
  45.         flow = 0;
  46.     }
  47.  
  48.     public String toString()
  49.     {
  50.         return name + ": s=" + start + " e=" + end + " d=" + direct;
  51.     }
  52. }
  53.  
  54. public class LongestPathinDAG
  55. {
  56.     int    n;                      // number of nodes
  57.     int    target;                 // destination node
  58.     int    minLength;              // the minimal length of each path
  59.     Node[] v;                      // used to store Nodes
  60.     Edge[] e;                      // used to store Edges
  61.     int[]  path;                   // used to store temporary path
  62.     int    length       = 0;       // length of the path
  63.     int    distance     = 0;       // distance of the path
  64.     int[]  bestPath;               // used to store temporary path
  65.     int    bestLength   = 0;       // length of the longest path
  66.     int    bestDistance = -1000000; // distance of the longest path
  67.     int[]  visited;                // used to mark a node as visited if set as
  68.                                     // 1
  69.  
  70.     public LongestPathinDAG()
  71.     {
  72.         Scanner sc = new Scanner(System.in);
  73.         System.out.println("Enter the number of vertices: ");
  74.         n = sc.nextInt();
  75.         System.out.println("Enter the number of edges: ");
  76.         int m = sc.nextInt();
  77.         v = new Node[n];
  78.         e = new Edge[m];
  79.         System.out.println(n + " nodes and " + m + " edges.");
  80.         for (int i = 0; i < n; i++)
  81.             v[i] = new Node(i);
  82.         int i = 0;
  83.         while (i < e.length)
  84.         {
  85.             Edge edge = new Edge(i);
  86.             int sVal = sc.nextInt();
  87.             edge.start = sVal;// sc.nextInt();
  88.             int eVal = sc.nextInt();
  89.             edge.end = eVal;// sc.nextInt();
  90.             edge.capacity = sc.nextInt();
  91.             System.out.println(" edge: " + edge.start + " - " + edge.end
  92.                     + " : " + edge.capacity);
  93.             edge.flow = 0;
  94.             e[i] = edge;
  95.             v[sVal].fors.add(i);
  96.             v[eVal].backs.add(i);
  97.             i++;
  98.             if (i == m)
  99.                 break;
  100.         }
  101.         visited = new int[v.length];
  102.         path = new int[v.length];
  103.         bestPath = new int[v.length];
  104.         sc.close();
  105.     }
  106.  
  107.     /*
  108.      * this function looks for a longest path starting from being to end,
  109.      * using the backtrack depth-first search.
  110.      */
  111.     public boolean findLongestPath(int begin, int end, int minLen)
  112.     {
  113.         /*
  114.          * compute a longest path from begin to end
  115.          */
  116.         target = end;
  117.         bestDistance = -100000000;
  118.         minLength = minLen;
  119.         dfsLongestPath(begin);
  120.         if (bestDistance == -100000000)
  121.             return false;
  122.         else
  123.             return true;
  124.     }
  125.  
  126.     private void dfsLongestPath(int current)
  127.     {
  128.         visited[current] = 1;
  129.         path[length++] = current;
  130.         if (current == target && length >= minLength)
  131.         {
  132.             if (distance > bestDistance)
  133.             {
  134.                 for (int i = 0; i < length; i++)
  135.                     bestPath[i] = path[i];
  136.                 bestLength = length;
  137.                 bestDistance = distance;
  138.             }
  139.         }
  140.         else
  141.         {
  142.             Vector<Integer> fors = v[current].fors;
  143.             for (int i = 0; i < fors.size(); i++)
  144.             {
  145.                 Integer edge_obj = (Integer) fors.elementAt(i);
  146.                 int edge = edge_obj.intValue();
  147.                 if (visited[e[edge].end] == 0)
  148.                 {
  149.                     distance += e[edge].capacity;
  150.                     dfsLongestPath(e[edge].end);
  151.                     distance -= e[edge].capacity;
  152.                 }
  153.             }
  154.         }
  155.         visited[current] = 0;
  156.         length--;
  157.     }
  158.  
  159.     public String toString()
  160.     {
  161.         String output = "v" + bestPath[0];
  162.         for (int i = 1; i < bestLength; i++)
  163.             output = output + " -> v" + bestPath[i];
  164.         return output;
  165.     }
  166.  
  167.     public static void main(String arg[])
  168.     {
  169.         LongestPathinDAG lp = new LongestPathinDAG();
  170.         /*
  171.          * find a longest path from vertex 0 to vertex n-1.
  172.          */
  173.         if (lp.findLongestPath(0, lp.n - 1, 1))
  174.             System.out.println("Longest Path is " + lp
  175.                     + " and the distance is " + lp.bestDistance);
  176.         else
  177.             System.out.println("No path from v0 to v" + (lp.n - 1));
  178.         /*
  179.          * find a longest path from vertex 3 to vertex 5.
  180.          */
  181.         if (lp.findLongestPath(3, 5, 1))
  182.             System.out.println("Longest Path is " + lp
  183.                     + " and the distance is " + lp.bestDistance);
  184.         else
  185.             System.out.println("No path from v3 to v5");
  186.         /*
  187.          * find a longest path from vertex 5 to vertex 3.
  188.          */
  189.         if (lp.findLongestPath(lp.n - 1, 3, 1))
  190.             System.out.println("Longest Path is " + lp
  191.                     + " and the distance is " + lp.bestDistance);
  192.         else
  193.             System.out.println("No path from v5 to v3");
  194.     }
  195. }

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.