dijkstra_openmp

dijkstra_openmp, a C++ code which illustrates the use of the OpenMP application program interface by implementing Dijkstra's minimum graph distance algorithm.

The program 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 Programs:

dijkstra_openmp_test

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

dijkstra_spmd, a MATLAB code which uses the SPMD feature to parallelize a simple example of Dijkstra's minimum distance algorithm for graphs.

openmp_test, a C++ code which uses the OpenMP application program interface for 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 Programming 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 Program Interface,
   Version 3.0,
   May 2008.

Source code:

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