longest path in a directed weighted graph from a given vertex to another one

Question

The graph is positive weighted and might be acyclic or not.

input file consists of

vertex number, edge number, begining vertex, ending vertex

edge1(from, to, weight)

edge2(from, to, weight) and so on.

the length of the path will be infinite if there is cycle in the graph and will be 0 if there is no way

the way I do is that I remove the same edges with less lengths and use bellman ford or dijkstra's algorithm in adjecent list or matrix and both work fine.

however, program should find the path at most 2 seconds and some input files contain 10000 vertices and 100000 edges

what should I do?

Answer 1

The time limit is 2 sec, it means the program should have near about ~10^6 iterations. See the limits of V = 10000 and e = 100000. This means an algorithm of O(V) or O(E) or O(V + E) or even O(E + VlogV)will easily compute your requirement well in given time.

Note E + Vlogv ~ (100000 + ~132877) which is less than 10^6

// This 10^6 limit is quit good for processors with 10^9 Hz frequency. So, even if your algo has 1000 instructions for each iteration, you will be in safe zone.

So, here is the proposed algorithm:

1. You will build the graph in O(E). Use Adjacency list data structure to represent the graph. -> While building this data structure, store indegree of each vertex and also store count of vertices.

   countV := V;
   foreach edge_i 
       inDegree[to] := inDegree[to] + 1;
   

2. Check if there is cycle in the graph in O(V + E).

   if no vertex with indegree = 0 and countV = 0 
       graph has no cycle 
   else if no vertex with indegree = 0 and countV != 0 
       graph has cycle
   else select any vertex having 0 indegree
       countV := countV - 1;
       decrease all its directed neighbours' inDegree by 1.
   

So if you get a cycle, your answer is directly infinite.

1. Make a BFS or DFS to get whether the ending vertex is reachable from beginning vertex or not. This can be done in O(V + E) or even O(E). Let us take O(V + E). If not reacable your answer is directly 0.

2. Now, apply dijkstra but in relax condition, just check the opposite. i.e in the pseudocode given here, instead of doing

   if alt < dist[v]:
       dist[v]  := alt;
   

do

    if alt > dist[v]:                                 
        dist[v]  := alt;

This can be done in O(E + VlogV). Hence overall complexity of the solution will be O(E + VlogV) which is well in constraints.