DIJKSTRA
Demonstration of Dijkstra's Minimum Distance Algorithm

DIJKSTRA is a FORTRAN90 library 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

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

DIJKSTRA is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version

Related Data and Programs:

BELLMAN_FORD, a FORTRAN90 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 FORTRAN90 program which uses OpenMP to parallelize a simple example of Dijkstra's minimum distance algorithm for graphs.

FLOYD, a FORTRAN90 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.

GRAPH_REPRESENTATION, a data directory of examples of ways of representing abstract mathematical graphs

LAUPACK, a FORTRAN90 library which carries out various operations on graphs.

TOMS097, a FORTRAN90 library which computes the distance between all pairs of nodes in a directed graph with weighted edges, using Floyd's algorithm.

Reference:

Edsger Dijkstra,
A note on two problems in connexion with graphs,
Numerische Mathematik,
Volume 1, 1959, pages 269-271.

Source Code:

dijkstra.f90, the source code.

Examples and Tests:

dijkstra.txt, the output file.

List of Routines:

MAIN runs an example of Dijkstra's minimum distance algorithm.
DIJKSTRA_DISTANCE uses Dijkstra's minimum distance algorithm.
FIND_NEAREST finds the nearest unconnected node.
INIT initializes the problem data.
TIMESTAMP prints the current YMDHMS date as a time stamp.
UPDATE_MIND updates the minimum distance vector.

You can go up one level to the FORTRAN90 source codes.

Last revised on 01 July 2010.

DIJKSTRA Demonstration of Dijkstra's Minimum Distance Algorithm