Dijkstra's Algorithm(last modified: 10 August, '06)
Implementation of dijkstra's algorithm to solve the shortest path problem.
It's an implementation of dijkstra's algorithm... in Python. Boring eh?
The module simply contains one class, `Vertex` - instantiations of which represent vertices on a network. To use the module simply create multiple vertex objects, connect them together, and then call the `solve` method on the starting vertex, passing the end vertex as a parameter. A brief demo can be seen below:
| 1 | import dijkstra |
| 2 | |
| 3 | a = b = c = d = dijkstra.Vertex() |
| 4 | a.connect(b, 5) |
| 5 | a.connect(c, 8) |
| 6 | b.connect(d, 10) |
| 7 | c.connect(d, 4) |
| 8 | print a.solve(d) # Output: ([<vertex A>, <vertex C>, <vertex D>], 12) |
While it's not a bad implementation there are some pretty impressive other ones out there. Have a look at the Python cookbook..
Download
(or view the source online)