dijkstra, a FORTRAN77 code which implements the Dijkstra algorithm for finding the minimum distance from a given node of a weighted graph to all the other nodes.
The program is mainly of interest as a starting point for a parallelization effort using OpenMP.
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 an Octave version and a Python version
bellman_ford, a FORTRAN77 library 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.
dijkstra_openmp, a FORTRAN77 program which uses OpenMP to parallelize a simple example of Dijkstra's minimum distance algorithm for graphs.
floyd, a FORTRAN77 library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
grafpack, a FORTRAN90 library which carries out operations on abstract graphs.
LAUPACK, a FORTRAN90 library which carries out various operations on graphs.
TOMS097, a FORTRAN77 library which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.