CODEWITHSUNDEEP
algorithmgraph
AmirHosein Adavoudi
AmirHosein Adavoudi

Reputation: 117

Find the shortest cycle in a directed graph with positive weights

A similar question of mine was asked in the below link, where one of the comments states that "The problem is certainly NP-hard because TSP can be reduced to it".

Finding shortest circuit in a graph that visits X nodes at least once

On the other hand, in another link shown below, one of the solutions says that by modifying Dijkstra's algorithm, the complexity would be $O(n^3)$.

Find cycle of shortest length in a directed graph with positive weights

I am wondering which solution in one of those links is correct.

Upvotes: 1

Views: 105

Answers (1)

pasthec
pasthec

Reputation: 339

From your description you only want to find any shortest cycle, so the second link applies to you and you can find an efficient algorithm. In the first case the question asked for the shortest cycle going through some set of vertices.

Upvotes: 1

Related Questions