2007-01-04

dijkstra in python

Given an arbitrary network, I knew that Dijkstra's algorithm computes the shortest path between any pair of nodes of the network. In a distributed routing protocol, Dijkstra is often used to compute shortest paths to destinations. I already knew, but wanted to confirm, that for any shortest path computed centrally from one edge node to another, you could apply the same Dijkstra algorithm to each intermediate node in the path and obtain the same result. So I put my Python coding skills to good use and created a small program that generates lots of random graphs with lots of nodes and lots of links with random "distances" and, for each such graph picks a couple of nodes and checks the assertion above. I only had to convert the Dijkstra algorithm expressed as pseudo-code in wikipedia to Python, which was pretty easy. The assertion is confirmed.
/me loves Python.

2 comments:

Nelson Castillo said...

Hi Gustavo. I also like python a lot. You might want to use heapq for Extract_Min next time when Speed is a concern (not this time I think). Regards.

Tillie said...

Great work.