Graph Theory: Shortest Path Algorithm

“The mind is a wonderful thing. You start off on one journey but it decides to take you somewhere completely different. The path of least resistance is the way to go. Don’t fight it ā€“ enjoy the ride.”
David Alejandro Fearnhead

Following an introduction by my colleague Ben Cohen, I’ve continued studying Steven Wolfman’s presentation on graph theory with the aid of some other resources.

Here, we’ll consider the shortest path problem:

Given: A graph G with (positively) weighted edges

Find: the least costly path from nodes X to Y

For this problem, we’ll explore Dijkstra’s algorithmic solution. Note that an unweighed graph shortest path can be solved using a simple breadth first search. A more general, but less efficient Bellman-Ford algorithm offers a solution for graphs with negatively weighted edges. Also consider that the algorithm being presented is not suitable for graphs with negative cost cycles, which make cost of transversal arbitrarily small.

Our implementation of Dijkstra’s shortest path algorithm should execute with O(n^2) (more precisely, O(|v|log|v|+|e|))time complexity. However, a simpler topological sort provides an answer for directed acyclic graphs in linear time.

An implementation of this algorithm using Python’s NetworkX package is in the works.

reference: Algorithm Design Manual, Skiena (2010)

 

 

 

Advertisements
Graph Theory: Shortest Path Algorithm

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