“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)