fork download
copy 
  1. # include <stdio.h>
  2. # include <stdlib.h>
  3.  
  4. void dijkstra(int *,int *,int *,int,int,int , int **);
  5. int minDistance(int dist[],int final[], int n) {
  6. 	int i, min=9999999, ind=-1;
  7. 	for(i=0; i<n; i++) {
  8. 		if(final[i]==-1 && dist[i]<min) {
  9. 			min=dist[i];
  10. 			ind=i;
  11. 		}
  12. 	}
  13. 	return ind;
  14. }
  15.  
  16. void copy(int p2[],int par[],int n) {
  17. 	int i;
  18. 	for(i=0; i<n; i++)
  19. 		p2[i]=par[i];
  20. }
  21.  
  22. int dist(int par[],int s,int t, int **adj) {
  23. 	int i,dis=0;
  24. 	for(i=t; i!=s; i=par[i]) {
  25. 		dis+=adj[par[i]][i];
  26. 	}
  27. 	return dis;
  28. }
  29.  
  30. void dj(int *p1,int s,int t, int n, int **graph)
  31. {
  32.   int dist[n], final[n];     
  33.   //initialize(dist,p1,final, n);
  34.  
  35.   int i,count,v;   // Initialize all distances as INFINITE and stpSet[] as false
  36.   for (i = 0; i < n; i++) {
  37.         dist[i] = 999999;
  38.         p1[i]=-1;
  39.         final[i]=-1;
  40.   }
  41.  
  42.      // Distance of source vertex from itself is always 0
  43.   dist[s] = 0;
  44.  
  45.   // Find shortest path for all vertices
  46.   for (count = 0; count < n-1; count++)
  47.      {
  48.        // Pick the minimum distance vertex from the set of vertices not
  49.        // yet processed. u is always equal to src in first iteration.
  50.        int u = minDistance(dist, final, n);
  51.        printf("u=%d", u);
  52.        // Mark the picked vertex as processed
  53.        final[u]=0;
  54.  
  55.        // Update dist value of the adjacent vertices of the picked vertex.
  56.        for (v = 0; v < n; v++)
  57.  
  58.          if (final[v]==-1 && graph[u][v]!=-1 && dist[u]+graph[u][v] < dist[v]) {
  59.             dist[v] = dist[u] + graph[u][v];
  60.             p1[v]=u;
  61.          }
  62.      }
  63. }
  64.  
  65. int main()
  66. {
  67.   int **adj, *parent1,*parent2,*parent3;
  68.   int n,k,i,j,s,t,w;
  69.   scanf("%d",&n);
  70.   adj = (int **)calloc(n,sizeof(int *));
  71.   for(i=0;i<n;i++)
  72.     {
  73.       adj[i] = (int *)calloc(n,sizeof(int));
  74.     }
  75.   parent1 = (int *)calloc(n,sizeof(int));
  76.   parent2 = (int *)calloc(n,sizeof(int));
  77.   parent3 = (int *)calloc(n,sizeof(int));
  78.  
  79.   for(i=0; i<n; i++)
  80.     for(j=0; j<n; j++)
  81.       adj[i][j]=-1;
  82.  
  83.   scanf("%d%d%d",&i,&j,&k);
  84.   while(i!=-1)
  85.     {
  86.       adj[i][j]=k;
  87.       scanf("%d%d%d",&i,&j,&k);
  88.     }
  89.   scanf("%d%d",&s,&t);
  90.   dijkstra(parent1,parent2,parent3,s,t,n,adj);
  91.   int temp=t;
  92.   printf("\n path1: %d",t);
  93.   while(temp!=s)
  94.     {
  95.       printf("->%d",parent1[temp]);
  96.       temp=parent1[temp];
  97.     }
  98.   temp=t;
  99.   printf("\n path2: %d",t);
  100.   while(temp!=s)
  101.     {
  102.       printf("->%d",parent2[temp]);
  103.       temp=parent2[temp];
  104.     }
  105.   temp=t;
  106.   printf("\n path3: %d",t);
  107.   while(temp!=s)
  108.     {
  109.       printf("->%d",parent3[temp]);
  110.       temp=parent3[temp];
  111.     }
  112.   return 0;
  113. }
  114.  
  115. void dijkstra(int *p1,int *ps,int *p3,int s,int t, int n, int **graph)
  116. {
  117. 	dj(p1,s,t,n,graph);
  118. 	int i,count,v;
  119. 	int arr[n],par[n];
  120. 	arr[0]=t;
  121. 	for(i=t,v=1; i!=s; v++) {
  122. 		arr[v]=p1[i];
  123. 		i=p1[i];
  124. 	}
  125. 	arr[v]=i;
  126. 	int v1=v;
  127. 	int c1,min=999999;
  128. 	for(i=0; i<v-1; i++) {
  129. 		c1=graph[arr[i]][arr[i+1]];
  130. 		graph[arr[i+1]][arr[i]]=-1;
  131. 		dj(par,s,t,n,graph);
  132. 		if(min>dist(par,s,t,graph)) {
  133. 			copy(ps,par,n);
  134. 		}
  135. 		graph[arr[i]][arr[i+1]]=c1;
  136. 	}
  137. 	/*int ar[n], c2,j;
  138. 	ar[0]=t;
  139. 	for(i=t,v=1; i!=s; v1++) {
  140. 		ar[v]=ps[i];
  141. 		i=ps[i];
  142. 	}
  143. 	ar[v1]=i;
  144. 	for(i=0; i<v-1; i++) {
  145. 		for(j=0; j<v1-1; j++) {
  146. 			c2=graph[ar[j]][ar[j+1]];
  147. 			c1=graph[arr[i]][arr[i+1]];
  148. 			graph[ar[j]][ar[j+1]]=-1;
  149. 			graph[arr[i+1]][arr[i]]=-1;
  150. 			dj(par,s,t,n,graph);
  151. 			if(min>dist(par,s,t,graph)) {
  152. 				copy(p3,par,n);
  153. 		}
  154. 		graph[ar[j]][ar[j+1]]=c2;
  155. 		graph[arr[i]][arr[i+1]]=c1;
  156. 	}
  157. }*/
  158.  
  159. }
Success #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
8
0 1 3
0 2 4
0 3 6
1 2 5
1 4 10
2 5 20
2 3 3
3 6 8
3 7 7
4 6 12
6 5 10
7 6 3
-1-1 -1
0 6
stdout
copy 
u=0u=1u=2u=3u=4u=7u=6u=0u=1u=2u=3u=4u=7u=6u=0u=1u=2u=3u=4u=7u=6
 path1: 6->3->0
 path2: 6->7->3->2->0
 path3: 6->0
https://ideone.com/fu2GvM
language:
C (gcc 8.3)
created:
7 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!