# include # include # include # include "dijkstra.h" /******************************************************************************/ int *dijkstra_distance ( int nv, int *ohd ) /******************************************************************************/ /* 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: 17 June 2019 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int NV, the number of nodes. 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 j; int md; int *mind; int mv; int step; /* 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 ( j = 0; j < nv; j++ ) { mind[j] = ohd[0+j*nv]; } /* Attach one more node on each iteration. */ for ( step = 1; step < nv; step++ ) { /* Find the nearest unconnected node. */ find_nearest ( nv, mind, connected, &md, &mv ); if ( mv == - 1 ) { printf ( "\n" ); printf ( "DIJKSTRA_DISTANCE - Warning!\n" ); printf ( " Search terminated early.\n" ); printf ( " Graph might not be connected.\n" ); break; } /* Mark this node as connected. */ connected[mv] = 1; /* Having determined the minimum distance to node MV, see if that reduces the minimum distance to other nodes. */ update_mind ( nv, mv, connected, ohd, mind ); } /* Free memory. */ free ( connected ); return mind; } /******************************************************************************/ void find_nearest ( int nv, int *mind, int *connected, int *d, int *v ) /******************************************************************************/ /* Purpose: FIND_NEAREST finds the nearest unconnected node. Licensing: This code is distributed under the MIT license. Modified: 17 June 2019 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int NV, the number of nodes. 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. Output, int *V, the index of the nearest unconnected node. */ { int i; int i4_huge = 2147483647; *d = i4_huge; *v = -1; for ( i = 0; i < nv; i++ ) { if ( ( ! connected[i] ) && ( mind[i] < *d ) ) { *d = mind[i]; *v = i; } } return; } /******************************************************************************/ void timestamp ( ) /******************************************************************************/ /* 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 nv, int mv, int *connected, int *ohd, int *mind ) /******************************************************************************/ /* Purpose: UPDATE_MIND updates the minimum distance vector. Discussion: We've just determined the minimum distance to node MV. For each node I which is not connected yet, 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: 17 June 2019 Author: Original C version by Norm Matloff, CS Dept, UC Davis. This C version by John Burkardt. Parameters: Input, int NV, the number of nodes. 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. */ { int i; int i4_huge = 2147483647; for ( i = 0; i < nv; i++ ) { if ( ! connected[i] ) { /* If we really use the maximum integer (or something close) to indicate no link, then we'll get burned if we add it to another value; Integer arithmetic can "wrap around", so that 17 + i4_huge becomes a very negative number! So first we eliminate the possiblity that the link is infinite. */ if ( ohd[mv+i*nv] < i4_huge ) { if ( mind[mv] + ohd[mv+i*nv] < mind[i] ) { mind[i] = mind[mv] + ohd[mv+i*nv]; } } } } return; }