dijkstra, a Python code which implements a simple version of Dijkstra's algorithm for determining the minimum distance from one node in a graph to all other nodes.
The program is mainly of interest as a starting point for a parallelization effort.
The example graph handled by the program has 6 nodes and 8 links, each with a positive length:
N0--15--N2-100--N3 \ | / \ | / 40 20 10 \ | / \ | / N1 / \ / \ 6 25 / \ / \ N5----8-----N4
Using "Inf" to indicate that there is no link between two nodes, the distance matrix for this graph is:
0 40 15 Inf Inf Inf 40 0 20 10 25 6 15 20 0 100 Inf Inf Inf 10 100 0 Inf Inf Inf 25 Inf Inf 0 8 Inf 6 Inf Inf 8 0
Dijkstra's algorithm efficiently determines the length of the shortest path from node 0 to other nodes as:
From 0 to: 0 1 2 3 4 5 Distance: 0 35 15 45 49 41
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
dijkstra is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version
bellman_ford, a Python code which implements the Bellman-Ford algorithm for finding the shortest distance from a given node to all other nodes in a directed graph whose edges have been assigned real-valued lengths.
toms097, a Python code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.