dijkstra, a FORTRAN90 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 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 a Python version
BELLMAN_FORD, a FORTRAN90 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.
DIJKSTRA_OPENMP, a FORTRAN90 code which uses OpenMP to parallelize a simple example of Dijkstra's minimum distance algorithm for graphs.
FLOYD, a FORTRAN90 code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.
GRAFPACK, a FORTRAN90 code which carries out operations on abstract graphs.
GRAPH_REPRESENTATION, a data directory of examples of ways of representing abstract mathematical graphs
LAUPACK, a FORTRAN90 code which carries out various operations on graphs.
TOMS097, a FORTRAN90 code which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.