dijkstra_openmp

dijkstra_openmp, a Fortran90 code which uses OpenMP to parallelize Dijkstra's minimum graph distance algorithm.

The code is an interesting example, because it does not involve parallelization of a loop. Instead, a parallel region is defined, and the nodes of the graph are divided up among the threads. The resulting parallel algorithm naturally requires some of the more advanced OpenMP directives, including critical, single and barrier, in order to work correctly.

The actual graph that is analyzed is very small (6 nodes), but of course the same algorithm would work for larger graphs. The point is rather to see how the OpenMP directives can be put together correctly.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

dijkstra_openmp is available in a C version and a C++ version and a Fortran90 version.

Related Data and codes:

dijkstra_openmp_test

dijkstra, a Fortran90 code which runs a simple example of Dijkstra's minimum distance algorithm for graphs.

openmp_test, a Fortran90 code which uses the OpenMP application code interface for carrying out parallel computations in a shared memory environment.

Reference:

1. Peter Arbenz, Wesley Petersen,
   Introduction to Parallel Computing - A practical guide with examples in C,
   Oxford University Press,
   ISBN: 0-19-851576-6,
   LC: QA76.58.P47.
2. Rohit Chandra, Leonardo Dagum, Dave Kohr, Dror Maydan, Jeff McDonald, Ramesh Menon,
   Parallel codeming in OpenMP,
   Morgan Kaufmann, 2001,
   ISBN: 1-55860-671-8,
   LC: QA76.642.P32.
3. Barbara Chapman, Gabriele Jost, Ruud vanderPas, David Kuck,
   Using OpenMP: Portable Shared Memory Parallel Processing,
   MIT Press, 2007,
   ISBN13: 978-0262533027,
   LC: QA76.642.C49.
4. OpenMP Architecture Review Board,
   OpenMP Application code Interface,
   Version 3.0,
   May 2008.

Source code:

• dijkstra_openmp.f90, the source code;
• dijkstra_openmp.sh, compiles the source code.