KAMEN1973

Longest Path in DAG

Jan 19th, 2021
988
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace LongestPath
  6. {
  7.     class Program
  8.     {
  9.         private class Edge
  10.         {
  11.             public int From { get; set; }
  12.  
  13.             public int To { get; set; }
  14.  
  15.             public int Weight { get; set; }
  16.         }
  17.  
  18.         static void Main(string[] args)
  19.         {
  20.             int nodesCount = int.Parse(Console.ReadLine());
  21.             int edgesCount = int.Parse(Console.ReadLine());
  22.             List<Edge>[] graph = ReadGraph(nodesCount, edgesCount);
  23.             int start = int.Parse(Console.ReadLine());
  24.             int end = int.Parse(Console.ReadLine());
  25.  
  26.             Stack<int> sorted = TopologicalSort(graph);
  27.  
  28.             double pathLength = GetLongestPath(graph, sorted, start, end);
  29.  
  30.             Console.WriteLine(pathLength);
  31.         }
  32.  
  33.         private static double GetLongestPath(List<Edge>[] graph, Stack<int> sorted, int start, int end)
  34.         {
  35.             double[] distances = new double[graph.Length];
  36.             Array.Fill(distances, double.NegativeInfinity);
  37.             distances[start] = 0;
  38.  
  39.             int[] previous = new int[graph.Length];
  40.             Array.Fill(previous, -1);
  41.  
  42.             foreach (int node in sorted)
  43.             {
  44.                 foreach (Edge child in graph[node])
  45.                 {
  46.                     double newDistance = distances[node] + child.Weight;
  47.                     if (newDistance > distances[child.To])
  48.                     {
  49.                         distances[child.To] = newDistance;
  50.                         previous[child.To] = node;
  51.                     }
  52.                 }
  53.             }
  54.  
  55.             Stack<int> path = ReconstructPath(previous, end);
  56.  
  57.             Console.WriteLine(string.Join(" ", path));
  58.  
  59.             return distances[end];
  60.         }
  61.  
  62.         private static Stack<int> ReconstructPath(int[] previous, int end)
  63.         {
  64.             Stack<int> path = new Stack<int>();
  65.             int node = end;
  66.  
  67.             while (node != -1)
  68.             {
  69.                 path.Push(node);
  70.                 node = previous[node];
  71.             }
  72.  
  73.             return path;
  74.         }
  75.  
  76.         private static Stack<int> TopologicalSort(List<Edge>[] graph)
  77.         {
  78.             Stack<int> sorted = new Stack<int>();
  79.             bool[] visited = new bool[graph.Length];
  80.  
  81.             for (int node = 1; node < graph.Length; node++)
  82.             {
  83.                 TraverseDFS(graph, node, sorted, visited);
  84.             }
  85.  
  86.             return sorted;
  87.         }
  88.  
  89.         private static void TraverseDFS(List<Edge>[] graph, int node, Stack<int> sorted, bool[] visited)
  90.         {
  91.             if (visited[node])
  92.             {
  93.                 return;
  94.             }
  95.  
  96.             visited[node] = true;
  97.  
  98.             foreach (Edge child in graph[node])
  99.             {
  100.                 TraverseDFS(graph, child.To, sorted, visited);
  101.             }
  102.  
  103.             sorted.Push(node);
  104.         }
  105.  
  106.         private static List<Edge>[] ReadGraph(int nodesCount, int edgesCount)
  107.         {
  108.             List<Edge>[] graph = new List<Edge>[nodesCount + 1];
  109.  
  110.             for (int i = 0; i < edgesCount; i++)
  111.             {
  112.                 int[] data = Console.ReadLine().Split().Select(int.Parse).ToArray();
  113.                 int from = data[0];
  114.                 int to = data[1];
  115.                 int weight = data[2];
  116.  
  117.                 if (graph[from] == null)
  118.                 {
  119.                     graph[from] = new List<Edge>();
  120.                 }
  121.  
  122.                 if (graph[to] == null)
  123.                 {
  124.                     graph[to] = new List<Edge>();
  125.                 }
  126.  
  127.                 graph[from].Add(new Edge
  128.                 {
  129.                     From = from,
  130.                     To = to,
  131.                     Weight = weight,
  132.                 });
  133.             }
  134.  
  135.             return graph;
  136.         }
  137.     }
  138. }
  139.  
RAW Paste Data