Algorithms/Longestpath,java at master · ravikiradoo/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.io.*;
import java.util.*;

class Edge
{
    int v;
    int weight;
}

class Graph{

    int V;
    ArrayList<Edge> Edges[];
    Stack<Integer>stack=new Stack<Integer>();
    boolean visited[];
    int dist[];
	Graph(int v)
	{
	    V=v;
	    visited=new boolean[V];
	    Edges=new ArrayList[V];
	    for(int i=0;i<V;i++)
	    Edges[i]=new ArrayList<Edge>();
	    dist=new int[V];


	}

public void	AddEdge(int a,int b,int weight)
	{
	    Edge edge=new Edge();
	    edge.v=b;
	    edge.weight=weight;
	    Edges[a].add(edge);

	}

	public Stack TopologicalSort()
	{

	 for(int i=0;i<V;i++)
	 {
	     if(visited[i]==false)
	     Topological(i);

	 }

	    return stack;

	}
	public void Topological(int v)
	{
	    visited[v]=true;

	    for(int i=0;i<Edges[v].size();i++)
	    {
	        int u=Edges[v].get(i).v;
	        if(visited[u]==false)
	        Topological(u);

	    }
	    stack.push(v);
	}

void longestPath(int s)
	{
	    for(int i=0;i<V;i++)
	    {
	        dist[i]=-100000;
	    }
	    dist[s]=0;

	    while(stack.empty()==false)
	    {
	        int u=stack.pop();
	       if(dist[u]!=-100000)

	     {
	         for(int i=0;i<Edges[u].size();i++)
	        {
	            if(dist[Edges[u].get(i).v]<dist[u]+Edges[u].get(i).weight)
	            {
	                dist[Edges[u].get(i).v]=dist[u]+Edges[u].get(i).weight;
	            }
	        }
	    }
	    }
	    for(int i=0;i<V;i++)
	    {
	        if(dist[i]==-100000)
	        System.out.println("INF");
	        else
	         System.out.println(dist[i]);
	    }

	}

}
class Main
{
    public static void main(String args[])
    {
        Scanner scan = new Scanner(System.in);


        int n= scan.nextInt();
        Graph graph=new Graph(n);

        int e=scan.nextInt();

          for(int i=0;i<e;i++)
          {
             graph.AddEdge(scan.nextInt(),scan.nextInt(),scan.nextInt());

          }
          Stack stack=graph.TopologicalSort();

         graph.longestPath(1);
   }

    }