Can we use Dijkstra's algorithm to find cycles???
Negative cycles
Positive cycles
If we can what, are the changes we have to do?
Asked
Active
Viewed 5,140 times
0
-
3If you tried something and fallen in error, then you can ask, but if you are asking for a full algorithm on something, I guess this is not the right place – brainless coder Jul 02 '14 at 05:12
-
Possible answers lay hidden in: http://stackoverflow.com/questions/3911626/find-cycle-of-shortest-length-in-a-directed-graph-with-positive-weights http://stackoverflow.com/questions/20123076/can-dijkstras-single-source-shortest-path-algorithm-dectect-an-infinite-cycle-i – metsburg Jul 02 '14 at 05:31
2 Answers
2
1) Dijkstra's doesn't work on graphs with negative edges because you can (possibly) find a minimum distance of negative infinity.
2) Um, you normally run it on graphs with cycles (otherwise, you might as well be traversing a tree), so it can handle them just fine.
If your real question is just about finding cycles, look at Finding all cycles in graph
David Ehrmann
- 7,366
- 2
- 31
- 40
0
No We cant use Dijkstra algorithm if negative cycles exist as the algorithm works on the shortest path and for such graphs it is undefined.Once you get to a negative cycle, you can bring the cost of your "shortest path" as low as you wish by following the negative cycle multiple times.
This type of restriction is applicable to all sort of algorithms to find shortest path in a graph and this is the same reason that prohibits all negative edges in Dijkstra.
You may modify Dijkstra to find the cycles in the graph but i do not think it is the best practice.
Rather you can possibility Use: Tarjan's strongly connected components algorithm(Time complexity -O(|E| + |V|)) or Kosaraju's algorithm (uses DFS and is a linear time alogoritham)
or you may follow this link for better idea: https://en.wikipedia.org/wiki/Strongly_connected_component
Hope I answered your question.
Yashwin Gokavarapu
- 21
- 2