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 MIT 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.