# DIJKSTRA Demonstration of Dijkstra's Minimum Distance Algorithm

DIJKSTRA is a Python 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.

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

### Languages:

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

### Related Data and Programs:

BELLMAN_FORD, a Python 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.

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

### Reference:

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

### Source Code:

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

Last revised on 30 September 2016.