fork download 
  1. /* Single Source Shortest Paths */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define MAXLINE       100   /* maximum length of input line  */
  7. //#define SIZE          8
  8. char line[MAXLINE];         /* stores next input line */
  9.  
  10. int n, m;     /* number of nodes, number of edges */
  11.  
  12. /* adjacency lists of input graph */ 
  13. typedef struct node *link; /* pointer to adjacency list node */
  14. struct node { int id; int weight; link next; }; /* adjacency list node */
  15. link *adj;  /* node array */
  16. int *D;
  17. /* priority queue */
  18.  
  19. /* ... insert your code ... */
  20.  
  21. void Queue(int j){ 
  22.  
  23. int i;
  24. D = (int *)malloc(n*sizeof(D));
  25. for (i=0; i<j; i++)
  26.     {
  27.         D[i]=9999; //9999 stands for infinite
  28.     }
  29. }
  30.  
  31.  
  32. /* ... end of code ... */
  33.  
  34.  
  35. /* initialization of array adj */
  36. void init(int N)
  37. {
  38.     int i;
  39.  
  40.     adj = (link *) malloc(N*sizeof(link));
  41.     for (i=0; i<N; i++)
  42.     {
  43.         adj[i]=NULL;
  44.     }
  45. }
  46.  
  47.  
  48. /* create new list node */
  49. link NEW(int v, int w, link next)
  50. {	
  51.     link x = (link) malloc(sizeof(link));
  52.     x->id = v; 
  53.     x->weight = w;
  54.     x->next = next;
  55.     return x;	
  56. }
  57.  
  58.  
  59. /* print all adjacency lists of the graph */
  60. void printGraph()
  61. {
  62.     link x;
  63.     int i;
  64.  
  65.     printf("Printing adjacency lists\n");
  66.     for (i=1; i<=n; i++)
  67.     {
  68.         printf("node %d : ", i);
  69.         x = adj[i];
  70.         while (x != NULL)
  71.         {
  72.             printf("%d[%d] ", x->id, x->weight);
  73.             x=x->next;
  74.         }
  75.         printf("\n");
  76.     }
  77. }
  78.  
  79.  
  80. /* read graph from input file */
  81. void readGraph(const char *file) 
  82. {
  83.         FILE *input = fopen (file, "r");
  84. 	if (!input) 
  85.         {
  86. 		fprintf (stderr, "Error opening file \"%s\".\n", file);
  87. 		exit(-1);
  88. 	}
  89.  
  90.         int x, y, w;
  91.  
  92. 	while ( fgets (line, MAXLINE, input) != NULL )
  93. 	{
  94. 		switch (line[0])
  95. 		{
  96.                     case '\n':  ;                /* ignore emplty lines */
  97.                     case '\0':  break;           /* ignore empty lines at the end of file */
  98.                     case 'p' :  /* read problem parameters: number of nodes, number of edges */        
  99. 				if (sscanf (line, "p %d %d", &n, &m) != 2)
  100. 				{
  101.                                     fprintf (stderr, "Error reading graph size (%s).\n", file);
  102.                                     exit(-1);
  103. 				}
  104.                                 init(n+1); /* initialize structures */
  105.                                 break;
  106.                     case 'a' :  /* read next edge */
  107. 				if (sscanf (line, "a %d %d %d", &x, &y, &w)!=3) 
  108. 				{
  109.                                     fprintf (stderr, "Error reading graph (%s).\n", file);
  110.                                     exit(-1);
  111. 				}
  112.                                 adj[x] = NEW(y, w, adj[x]); /* add edge (x,y) with weight w */
  113. 				break;
  114.                     default:    fprintf (stderr, "Error reading graph (%s).\n", file);
  115. 				exit(-1);
  116. 		}
  117. 	}
  118.  
  119. 	fclose (input);
  120. }
  121.  
  122.  
  123.  
  124. /*void Relax()
  125. {
  126. D[p]=q;
  127. if (D[p]>)
  128. }
  129. */
  130.  
  131. /* Dijkstra's algorithm  */
  132. void Dijkstra(int k)
  133. {
  134. Queue(n+1);
  135. D[k]=0;
  136. int di, done[n+1], pi[n+1]; // done[] array includes already examined nodes. pi[]array is the predecessor array for implementing Dijkstra's algorithm
  137. for (di=0; di<n+1; di++)
  138.     {
  139. 	done[di]=-2; //initialize done[] elements with -2.
  140. 	pi[di]=-1; //initialize pi[] elements with -1 (void).
  141.     }
  142. done[1]=0;//initialize 1st element to be 0
  143. pi[1]=0;//initialize 1st element to be 0
  144.  
  145. int i, fl=1, p, q, dp, m=D[1]; // Var i is for the for-loop counter, dp is for the done[] array 
  146. //int flag=0;
  147. for (i=1; i<=n; i++){
  148.   while ( fl != n )
  149. 	{ 
  150. 		//Find node with min weight. The value -1 means that the node is "done".
  151. 		for (i=1; i <= n; i++)
  152. 		{
  153.       		  if (D[i] <= m && D[i] != -1 && D[i] != 9999) { 
  154. 		  m = D[i];
  155. 		  dp = i;}
  156. 		}
  157.  
  158. 		//Updating queues	
  159. 		done[dp] = 1; //1 means that the node "dp" has been successfully examined
  160. 		D[dp] = -1;
  161.  
  162. 		//Add neighbours of node we are currently examining
  163.  
  164. 		link x;
  165. 		x=adj[dp];
  166.  
  167. 		while (x != NULL)
  168.         	{
  169. 		  p = x->id;
  170. 		  q = x->weight;
  171. 		  D[p]=q;
  172. 		  x=x->next; 
  173.        	}
  174. //>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>PROVLIMATIKOS KODIKAS>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  175. //We have to relax the edges now...
  176. for (i=1; i<n; i++){
  177. 	int w;
  178. 	link tmp;
  179. 	tmp=adj[dp];	
  180.  
  181. 	//This while-loop is useful in order to determine the edge (if any) between the current node (dp) and the node running by the for-loop (i)
  182. 	while (tmp != NULL)
  183.         	{
  184. 		  p = tmp->id;
  185. 		  q = tmp->weight;
  186. 		  tmp=tmp->next;
  187. 		  if (p==i) {w=q;}
  188. 		  else{
  189. 		  	if (tmp == NULL){
  190. 			  w=0;			
  191. 			  break;
  192. 			}
  193. 		  }
  194.         	}//close while
  195.  
  196. 	if ((D[i] > D[dp] + w) && D[i]!=9999 && D[i] !=-1 ){
  197. 		D[i] = D[dp] + w;
  198. 		pi[i]=dp;
  199.  
  200. 	}//close if
  201. }//close for
  202. //>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>TELOS PROVLIMATIKOU TMIMATOS>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  203. 		//Prevent the minimum search routine from including -1 values in search
  204. 		int el;
  205. 		for(el=1; el<n-1; el++){
  206. 			if (D[dp+el] != -1 && (dp+el)<n){		
  207. 				m = D[dp+el];}
  208. 		}
  209.  
  210. 		//Print done[] (NOT NECESSARY)
  211. 		int cnt;	
  212. 		for (cnt=1; cnt <=n; cnt++){printf("%d \n", pi[cnt]);}//<<
  213. 		printf("====================================================\n");
  214.  
  215. 		//Check whether the priority queue (D) is "empty"		
  216. 		while(D[fl]==-1){fl++;}
  217. 		if (fl==n+1){break;}
  218.  
  219. 	}//while close
  220.  
  221.    }//for close
  222.  
  223. }//Dijkstra close
  224.  
  225. int main(int argc, char *argv[])
  226. {   
  227.     int i;
  228.     if (argc != 2) 
  229.     {
  230. 	printf("\n usage: %s <input file> \n\n", argv[0]);
  231. 	return 0;
  232.     }
  233.  
  234.     char *file = argv[1];
  235.     readGraph(file); 
  236.  
  237.     //printGraph(); 
  238.  
  239.     Dijkstra(1);
  240.  
  241.     return 0;
  242. }
Success #stdin #stdout 0.02s 1676KB
comments (?)
stdin 
Standard input is empty
stdout 
 usage: ./prog <input file>
https://ideone.com/piJqA
language:
C (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!