Thursday 14 November 2013

Implementing Dijkstra's algorithm in Python

I wanted to write a script to run Dijkstra's algorithm for finding the shortest path through a weighted graph in Python. I found that I was able to write a script to run it fairly easily using a mixture of numpy and scipy functions, as scipy has a function for Dijkstra's algorithm, hurray!

An undirected graph
First, I tried implementing Dijkstra's algorithm to find the shortest path from 1 to 7 for the following undirected graph:

I implemented Dijkstra's algorithm in my script When I run it, it gives:
distance to g7= 42.0
path= ['g1', 'g4', 'g3', 'g2', 'g7']

That is, the shortest path from 1 to 7 has length 42, and is 1->4->3->2->7.

Note: the Dijkstra's algorithm finds the shortest path, and requires that you don't have any negative edge weights.

A directed graph
The next thing that I wanted to do was to find the highest-scoring path (longest path) through the following directed graph:

In this case the edges are directed. Apparently in numpy, to specify a directed graph, when you specify the matrix of edges, you only specify one of the edges between nodes i and j.

A key difference between this case and the previous one is that here I wanted the highest-scoring path, so actually this is the 'longest path problem'. Unfortunately, Dijkstra's algorithm can't be used for this. However, my husband Noel helped me find another algorithm to find the longest path in a weighted graph, see his blog post on this (thanks Noel!).