# include # include # include # include # define NV 6 int main ( int argc, char **argv ); int *dijkstra_distance ( int ohd[NV][NV] ); void find_nearest ( int s, int e, int mind[NV], int connected[NV], int *d, int *v ); void init ( int ohd[NV][NV] ); void timestamp ( void ); void update_mind ( int s, int e, int mv, int connected[NV], int ohd[NV][NV], int mind[NV] ); /******************************************************************************/ int main ( int argc, char **argv ) /******************************************************************************/ /* Purpose: MAIN runs an example of Dijkstra's minimum distance algorithm. Discussion: Given the distance matrix that defines a graph, we seek a list of the minimum distances between node 0 and all other nodes. This program sets up a small example problem and solves it. The correct minimum distances are: 0 35 15 45 49 41 Licensing: This code is distributed under the MIT license. Modified: 01 July 2010 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. */ { int i; int i4_huge = 2147483647; int j; int *mind; int ohd[NV][NV]; timestamp ( ); fprintf ( stdout, "\n" ); fprintf ( stdout, "DIJKSTRA_OPENMP\n" ); fprintf ( stdout, " C version\n" ); fprintf ( stdout, " Use Dijkstra's algorithm to determine the minimum\n" ); fprintf ( stdout, " distance from node 0 to each node in a graph,\n" ); fprintf ( stdout, " given the distances between each pair of nodes.\n" ); fprintf ( stdout, "\n" ); fprintf ( stdout, " Although a very small example is considered, we\n" ); fprintf ( stdout, " demonstrate the use of OpenMP directives for\n" ); fprintf ( stdout, " parallel execution.\n" ); /* Initialize the problem data. */ init ( ohd ); /* Print the distance matrix. */ fprintf ( stdout, "\n" ); fprintf ( stdout, " Distance matrix:\n" ); fprintf ( stdout, "\n" ); for ( i = 0; i < NV; i++ ) { for ( j = 0; j < NV; j++ ) { if ( ohd[i][j] == i4_huge ) { fprintf ( stdout, " Inf" ); } else { fprintf ( stdout, " %3d", ohd[i][j] ); } } fprintf ( stdout, "\n" ); } /* Carry out the algorithm. */ mind = dijkstra_distance ( ohd ); /* Print the results. */ fprintf ( stdout, "\n" ); fprintf ( stdout, " Minimum distances from node 0:\n"); fprintf ( stdout, "\n" ); for ( i = 0; i < NV; i++ ) { fprintf ( stdout, " %2d %2d\n", i, mind[i] ); } /* Free memory. */ free ( mind ); /* Terminate. */ fprintf ( stdout, "\n" ); fprintf ( stdout, "DIJKSTRA_OPENMP\n" ); fprintf ( stdout, " Normal end of execution.\n" ); fprintf ( stdout, "\n" ); timestamp ( ); return 0; } /******************************************************************************/ int *dijkstra_distance ( int ohd[NV][NV] ) /******************************************************************************/ /* Purpose: DIJKSTRA_DISTANCE uses Dijkstra's minimum distance algorithm. Discussion: We essentially build a tree. We start with only node 0 connected to the tree, and this is indicated by setting CONNECTED[0] = 1. We initialize MIND[I] to the one step distance from node 0 to node I. Now we search among the unconnected nodes for the node MV whose minimum distance is smallest, and connect it to the tree. For each remaining unconnected node I, we check to see whether the distance from 0 to MV to I is less than that recorded in MIND[I], and if so, we can reduce the distance. After NV-1 steps, we have connected all the nodes to 0, and computed the correct minimum distances. Licensing: This code is distributed under the MIT license. Modified: 02 July 2010 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int OHD[NV][NV], the distance of the direct link between nodes I and J. Output, int DIJKSTRA_DISTANCE[NV], the minimum distance from node 0 to each node. */ { int *connected; int i; int i4_huge = 2147483647; int md; int *mind; int mv; int my_first; int my_id; int my_last; int my_md; int my_mv; int my_step; int nth; /* Start out with only node 0 connected to the tree. */ connected = ( int * ) malloc ( NV * sizeof ( int ) ); connected[0] = 1; for ( i = 1; i < NV; i++ ) { connected[i] = 0; } /* Initial estimate of minimum distance is the 1-step distance. */ mind = ( int * ) malloc ( NV * sizeof ( int ) ); for ( i = 0; i < NV; i++ ) { mind[i] = ohd[0][i]; } /* Begin the parallel region. */ # pragma omp parallel private ( my_first, my_id, my_last, my_md, my_mv, my_step ) \ shared ( connected, md, mind, mv, nth, ohd ) { my_id = omp_get_thread_num ( ); nth = omp_get_num_threads ( ); my_first = ( my_id * NV ) / nth; my_last = ( ( my_id + 1 ) * NV ) / nth - 1; /* The SINGLE directive means that the block is to be executed by only one thread, and that thread will be whichever one gets here first. */ # pragma omp single { printf ( "\n" ); printf ( " P%d: Parallel region begins with %d threads\n", my_id, nth ); printf ( "\n" ); } fprintf ( stdout, " P%d: First=%d Last=%d\n", my_id, my_first, my_last ); for ( my_step = 1; my_step < NV; my_step++ ) { /* Before we compare the results of each thread, set the shared variable MD to a big value. Only one thread needs to do this. */ # pragma omp single { md = i4_huge; mv = -1; } /* Each thread finds the nearest unconnected node in its part of the graph. Some threads might have no unconnected nodes left. */ find_nearest ( my_first, my_last, mind, connected, &my_md, &my_mv ); /* In order to determine the minimum of all the MY_MD's, we must insist that only one thread at a time execute this block! */ # pragma omp critical { if ( my_md < md ) { md = my_md; mv = my_mv; } } /* This barrier means that ALL threads have executed the critical block, and therefore MD and MV have the correct value. Only then can we proceed. */ # pragma omp barrier /* If MV is -1, then NO thread found an unconnected node, so we're done early. OpenMP does not like to BREAK out of a parallel region, so we'll just have to let the iteration run to the end, while we avoid doing any more updates. Otherwise, we connect the nearest node. */ # pragma omp single { if ( mv != - 1 ) { connected[mv] = 1; printf ( " P%d: Connecting node %d.\n", my_id, mv ); } } /* Again, we don't want any thread to proceed until the value of CONNECTED is updated. */ # pragma omp barrier /* Now each thread should update its portion of the MIND vector, by checking to see whether the trip from 0 to MV plus the step from MV to a node is closer than the current record. */ if ( mv != -1 ) { update_mind ( my_first, my_last, mv, connected, ohd, mind ); } /* Before starting the next step of the iteration, we need all threads to complete the updating, so we set a BARRIER here. */ #pragma omp barrier } /* Once all the nodes have been connected, we can exit. */ # pragma omp single { printf ( "\n" ); printf ( " P%d: Exiting parallel region.\n", my_id ); } } free ( connected ); return mind; } /******************************************************************************/ void find_nearest ( int s, int e, int mind[NV], int connected[NV], int *d, int *v ) /******************************************************************************/ /* Purpose: FIND_NEAREST finds the nearest unconnected node. Licensing: This code is distributed under the MIT license. Modified: 02 July 2010 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int S, E, the first and last nodes that are to be checked. Input, int MIND[NV], the currently computed minimum distance from node 0 to each node. Input, int CONNECTED[NV], is 1 for each connected node, whose minimum distance to node 0 has been determined. Output, int *D, the distance from node 0 to the nearest unconnected node in the range S to E. Output, int *V, the index of the nearest unconnected node in the range S to E. */ { int i; int i4_huge = 2147483647; *d = i4_huge; *v = -1; for ( i = s; i <= e; i++ ) { if ( !connected[i] && ( mind[i] < *d ) ) { *d = mind[i]; *v = i; } } return; } /******************************************************************************/ void init ( int ohd[NV][NV] ) /******************************************************************************/ /* Purpose: INIT initializes the problem data. Discussion: The graph uses 6 nodes, and has the following diagram and distance matrix: N0--15--N2-100--N3 0 40 15 Inf Inf Inf \ | / 40 0 20 10 25 6 \ | / 15 20 0 100 Inf Inf 40 20 10 Inf 10 100 0 Inf Inf \ | / Inf 25 Inf Inf 0 8 \ | / Inf 6 Inf Inf 8 0 N1 / \ / \ 6 25 / \ / \ N5----8-----N4 Licensing: This code is distributed under the MIT license. Modified: 02 July 2010 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Output, int OHD[NV][NV], the distance of the direct link between nodes I and J. */ { int i; int i4_huge = 2147483647; int j; for ( i = 0; i < NV; i++ ) { for ( j = 0; j < NV; j++ ) { if ( i == j ) { ohd[i][i] = 0; } else { ohd[i][j] = i4_huge; } } } ohd[0][1] = ohd[1][0] = 40; ohd[0][2] = ohd[2][0] = 15; ohd[1][2] = ohd[2][1] = 20; ohd[1][3] = ohd[3][1] = 10; ohd[1][4] = ohd[4][1] = 25; ohd[2][3] = ohd[3][2] = 100; ohd[1][5] = ohd[5][1] = 6; ohd[4][5] = ohd[5][4] = 8; return; } /******************************************************************************/ void timestamp ( void ) /******************************************************************************/ /* Purpose: TIMESTAMP prints the current YMDHMS date as a time stamp. Example: 31 May 2001 09:45:54 AM Licensing: This code is distributed under the MIT license. Modified: 24 September 2003 Author: John Burkardt Parameters: None */ { # define TIME_SIZE 40 static char time_buffer[TIME_SIZE]; const struct tm *tm; time_t now; now = time ( NULL ); tm = localtime ( &now ); strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm ); printf ( "%s\n", time_buffer ); return; # undef TIME_SIZE } /******************************************************************************/ void update_mind ( int s, int e, int mv, int connected[NV], int ohd[NV][NV], int mind[NV] ) /******************************************************************************/ /* Purpose: UPDATE_MIND updates the minimum distance vector. Discussion: We've just determined the minimum distance to node MV. For each unconnected node I in the range S to E, check whether the route from node 0 to MV to I is shorter than the currently known minimum distance. Licensing: This code is distributed under the MIT license. Modified: 02 July 2010 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int S, E, the first and last nodes that are to be checked. Input, int MV, the node whose minimum distance to node 0 has just been determined. Input, int CONNECTED[NV], is 1 for each connected node, whose minimum distance to node 0 has been determined. Input, int OHD[NV][NV], the distance of the direct link between nodes I and J. Input/output, int MIND[NV], the currently computed minimum distances from node 0 to each node. On output, the values for nodes S through E have been updated. */ { int i; int i4_huge = 2147483647; for ( i = s; i <= e; i++ ) { if ( !connected[i] ) { if ( ohd[mv][i] < i4_huge ) { if ( mind[mv] + ohd[mv][i] < mind[i] ) { mind[i] = mind[mv] + ohd[mv][i]; } } } } return; }