SINGLE SOURCE SHORTEST PATH PROBLEM(DIJKSTRA'S ALGORITHM) 'C' PROGRAM

1. #include<stdio.h>
2. #include<limits.h>
3. int n;
4. int adj[10][10],vi[10];
5. int dist[10];
6. void shortest(int v);
7. int min();
8. int main(){
9. int i,j,s;
10. printf("enter number of vertices\n");
11. scanf("%d",&n);
12. for(i=1;i<=n;i++){
13. dist[i]=INT_MAX;
14. printf("%d\t",dist[i]);
15. }
16. printf("enter adjacency matrix\n");
17. for(i=1;i<=n;i++)
18. for(j=1;j<=n;j++)
19. scanf("%d",&adj[i][j]);
20. printf("enter source vertex to start\n");
21. scanf("%d",&s);
22. shortest(s);
23. printf("shortest distances from vertex %d are\n",s);
24. for(i=1;i<=n;i++){
25. if(dist[i]<INT_MAX&&vi[i]==1)
26. printf("cost:%d\tedge:(%d,%d)\n",dist[i],s,i);
27. }
28. return 0;
29. }
30.  void shortest(int v){
31. int i,j,u;
32. for(i=1;i<=n;i++){
33. vi[i]=-1;
34. if(adj[v][i]!=0)
35. dist[i]=adj[v][i];
36. }
37. vi[v]=1;
38. for(j=2;j<=n;j++){
39. u=min();
40. printf("%d\n",u);
41. vi[u]=1;
42. for(i=1;i<=n;i++){
43. if((adj[u][i]!=0)&&(dist[i]>(dist[u]+adj[u][i]))&&(vi[i]==-1)){
44. dist[i]=(dist[u]+adj[u][i]);
45. }
46. }
47. }
48. return;
49. }
50. int min(){
51.  int i,t=dist[1],j;
52. for(i=1;i<=n;i++){
53. if((dist[i]<t)&&(vi[i]==-1))
54. {
55. t=dist[i];
56. }}
57. for(j=1;j<=n;j++){
58. if(t==dist[j]&&vi[j]==-1)
59. break;}
60. return j;
61. }

QUICK SORT -'C' PROGRAM

#include<stdio.h>
#include<limits.h>
#define max 25
int arr[max];
int partition(int arr[],int l,int h);
void quick(int l,int h);
int main(){
int n;
printf("enter num: \n");
scanf("%d",&n);
printf("enter array elements\n");
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
arr[n]=INT_MAX;
quick(0,n);
printf("elements after sorting are\n");
for(int i=0;i<n;i++)
printf("%d\t",arr[i]);
}
int partition(int arr[],int l,int h)
{
int v=arr[l],i=l,j=h,temp;
do{
do{
i=i+1;
}while(arr[i]<v);
do{
j=j-1;
}while(arr[j]>v);
if (i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}while(i<j);
arr[l]=arr[j];arr[j]=v;
return j;
}
void quick(int l,int h){
int j;
if(l<h)
{
j=partition(arr,l,h);
quick(l,j);
quick(j+1,h);
}
}