Skip to content

Shortest Paths

April 4, 2013

Dijkstra’s shortest path algorithm runs in O(E log V). The algorithm is: 1. Choose the closest vertex to the source 2. Relax all the edges.

Interestingly, Prim’s algorithm and Dijkstra’s algorithm are very similar algorithms.

For DAGs, the shortest path problem is simplified to O(E+V). The approach for this speed up is: Sort the vertices by topological sort order (can be done because it’s a directed acyclic graph), and then relax all the edges from the vertices going in topological sort order.

For DAGs, you can also easily find solutions to the longest path problem, by simply negating all the weights of the edges, and then running the DAG shortest path algorithm from above. An example use case of where longest path would be necessary is Parallel Job Scheduling or Critical Path Method.

Some points of note:

  1. Dijkstra’s algorithm does NOT work on graphs with negative edges.
  2. Adding some number to all the edges to make them all positive, also does not fix the problem, because then you’d be adding X some number of times for each path.
  3. Negative cycles in a graph means that solving for the shortest path is an intractable problem. Since a negative cycle would allow for an infinite loop of smaller and smaller paths.

Bellman-Ford is a shortest path algorithm that does operate on graphs with negative edges, and runs in O(VE) time. The algorithm is simply: 1. For V times 2. Relax all the edges in the graph in any order.

Advertisements

From → Algorithms

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: