'Tweaking Dijkstra's Algorithm to detect minimum length cycle in directed graph

I am trying to find the minimum length cycle in a directed graph but this time using a greedy algorithm.

I think the smartest way to do it is using Dijkstra's Algorithm using some kind of tweak. (I also know that the Graph has positive weights which makes it a bit obvious), but I can't seem to be able to find a nice way to do it.

I thought of probably splitting a node into its ingoing and outgoing edges, and running Dijkstra's algorithm for every node like this, which ends up being O(V^3). Can I do better using another greedy algorithm maybe?

algorithmgraph-theorygreedy


Solution 1:[1]

  • remove all leaf nodes ( nodes with only in edges ) since they cannot be part of a cycle
  • remove all root nodes ( nodes with only out edges ) since they cannot be part of a cycle
  • start a breadth first search from every remaining node
  • increment depth of each search by one ( easy optimization using threads on a multi-processor machine )
  • first search to revisit starting node is the minimum length cycle

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 ravenspoint

Related Questions