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

by

You can easily modify Floyd-Warshall algorithm. (If you’re not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms).

Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won’t affect algorithm itself, as those zeroes weren’t used in computation anyway (since path path[i][j] will never change for k == i or k == j).

In the end, path[i][i] is the length the shortest cycle going through i. Consequently, you need to find min(path[i][i]) for all i. And if you want cycle itself (not only its length), you can do it just like it’s usually done with normal paths: by memorizing k during execution of algorithm.

In addition, you can also use Dijkstra’s algorithm to find a shortest cycle going through any given node. If you run this modified Dijkstra for each node, you’ll get the same result as with Floyd-Warshall. And since each Dijkstra is O(n^2), you’ll get the same O(n^3) overall complexity.

More Related Contents:

  1. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  2. How does Dijkstra’s Algorithm and A-Star compare?
  3. graph – Dijkstra for The Single-Source Longest Path
  4. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  5. Cycles in an Undirected Graph
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. Negative weights using Dijkstra’s Algorithm
  8. Millions of 3D points: How to find the 10 of them closest to a given point?
  9. Find the shortest path in a graph which visits certain nodes
  10. Graph auto-layout algorithm
  11. Find connected components in a graph [closed]
  12. Finding all the shortest paths between two nodes in unweighted undirected graph
  13. Algorithm for “nice” grid line intervals on a graph
  14. How to implement depth first search for graph with a non-recursive approach
  15. Longest acyclic path in a directed unweighted graph
  16. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  17. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  18. Enumerating all paths in a directed acyclic graph
  19. Why does Dijkstra’s algorithm use decrease-key?
  20. Planar Graph Layouts
  21. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  22. Bridges in a connected graph
  23. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  24. Finding connected components of adjacency matrix graph
  25. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
  26. Algorithm to beat Strassen’s Algorithm
  27. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  28. Fastest algorithm for circle shift N sized array for M position
  29. Lights out game algorithm
  30. How does this work? Weird Towers of Hanoi Solution

Leave a Comment