c(pp)/dijkstra-sequential-random.c
// Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra ' s algorithm ; taking a graph its dimension and the starting point
void dijkstra(int **graph, int dim, int start, clock_t *time_dijkstra){
	int i, j, k, minDistance, next = 1, dimPath = 20;
	int distance[dim], parent[dim], path[dimPath];
	bool visited[dim];
	for (i = 0; i < dim; i++){
		distance[i] = graph[start][i]; 
		parent[i] = 0; 
		visited[i] = false; 
	}
	for (i = 0; i < dimPath; i++){
		path[i] = INF;
	}
	distance[start] = 0; 
	visited[start] = true; 
	for (i = 0; i < dim; i++){
		minDistance = INF; 
		for (j = 0; j < dim; j++){
			if (!visited[j]){
				if (distance[j] < minDistance){
					minDistance = distance[j]; 
					next = j; 
				}
			}
		}
		visited[next] = true;
		for (j = 0; j < dim; j++){
			if (!visited[j]){
				if (minDistance + graph[next][j] < distance[j]){
					distance[j] = minDistance + graph[next][j];
					parent[j] = next;
				}
			}
		}
	}
	*time_dijkstra = clock();
	if (dim < 21){
		printf("\n");
		printf("Adjacency matrix:\n-----------------\n");
		printMatrix(graph, dim);
		printf("\n\nPaths:\n------");
		for (i = 0; i < dim; i++){
			printPath(i, start, dimPath, path, parent, distance);
			printf("\n");
		}
	}
	else {
		printf("\nPath (start to last):\n---------------------\n");
		printPath(dim - 1, start, dimPath, path, parent, distance);
	}
	printf("\n");
	return;
}
void dijkstra ( int * * graph , int dim , int start , clock_t * time_dijkstra ) { int i , j , k , minDistance , next = 1 , dimPath = 20 ; int distance [ dim ] , parent [ dim ] , path [ dimPath ] ; bool visited [ dim ] ; for ( i = 0 ; i < dim ; i ++ ) { distance [ i ] = graph [ start ] [ i ] ; parent [ i ] = 0 ; visited [ i ] = false ; } for ( i = 0 ; i < dimPath ; i ++ ) { path [ i ] = INF ; } distance [ start ] = 0 ; visited [ start ] = true ; for ( i = 0 ; i < dim ; i ++ ) { minDistance = INF ; for ( j = 0 ; j < dim ; j ++ ) { if ( ! visited [ j ] ) { if ( distance [ j ] < minDistance ) { minDistance = distance [ j ] ; next = j ; } } } visited [ next ] = true ; for ( j = 0 ; j < dim ; j ++ ) { if ( ! visited [ j ] ) { if ( minDistance + graph [ next ] [ j ] < distance [ j ] ) { distance [ j ] = minDistance + graph [ next ] [ j ] ; parent [ j ] = next ; } } } } * time_dijkstra = clock ( ) ; if ( dim < 21 ) { printf ( " \n " ) ; printf ( " \n \n " ) ; printMatrix ( graph , dim ) ; printf ( " \n \n \n " ) ; for ( i = 0 ; i < dim ; i ++ ) { printPath ( i , start , dimPath , path , parent , distance ) ; printf ( " \n " ) ; } } else { printf ( " \n \n \n " ) ; printPath ( dim - 1 , start , dimPath , path , parent , distance ) ; } printf ( " \n " ) ; return ; }
Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra ' s algorithm ; taking a graph its dimension and the starting point
// loop 1: initializing // vector of distances from start to adjescent nodes  // no exisiting parents yet // no nodes visited yet // loop 1': initializing path array separately, since dimPath << dim // set distance of start node to itself to zero // not necessary, since zero is minDistance anyway; saves a bit of time as it circumvents the second if statement in loop 3  // loop 2: iterating over number of nodes // initializing minimum distance in every iteration /* loop 3: finding node with lowest distance value in distance vector
		(if node was not already visited); already processed nodes are
		excluded according to their visited status (true) */ // minimal distance value // index of the closest node /* closest node in current distance list is found and thus given a
		processed flag, which will leave it untouched in further iterations*/ /* loop 4: updating the distance vector with distances from next node 
		(graph[next][j]) -> including new connections (replacing INF) and
		shorter indirect paths; by adding the minDistance we keep track of the 
		distance already travelled w.r.t the start node; already processed
		nodes must again be excluded */ // time for dijkstra algorithm // printing; only for small values of dim (legibility in terminal, w=160) // only print path from start to last node