retagged by
4,421 views
29 votes
29 votes

Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time

  1. $O(n)$
  2. $O(n . \log(n))$ but not $O (n)$
  3. $O(n^{1.5})$ but not $O (n \log n)$
  4. $O(n^{3})$ but not $O(n^{1.5})$
  5. $O(2^{n})$ but not $O(n^{3})$
retagged by

3 Answers

Best answer
14 votes
14 votes
I think arbitrary large weights means having positive weight cycle.

So, Bellman Ford algorithm can be used.

$O(VE)$

Changing sign of weights of edges.

Correct Answer: $D$
edited by
5 votes
5 votes

Some additional information ->

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.

The longest path problem is NP-hard.

However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems. But graph is acyclic it is not given.


First of all thanks to @VS ji for correcting me. Now, Determining whether there are paths(nothing is mentioned what kind of path is this) of arbitrarily large could be done in polynomial time. For any graph  we have two cases -

(1) Graph contains cycle -> In this case  Bellman-Ford  could be used because we have to just check existence cycle. 

(2) Graph does not contains cycle -> Linear time algorithm exists for this case also (as mentioned above).

So best possible Answer in provided option is (D) Part.


For more information please refer  - https://en.wikipedia.org/wiki/Longest_path_problem

edited by
0 votes
0 votes
arbitrary: based on random choice or personal whim, rather than any reason or system.

Using this description for 'arbitrary' I would say this problem is asking "If there is a path of weight k" and hence it boils down to subset sum problem.
Answer:

Related questions