Wednesday 23 January 2013

To implement spanning tree using dijkstra's algorithm

#include<stdio.h>
 main()
 {
  int node[50],pred[50],dist[50],status[50],path[50];
  int n,source,dest,adj[50][50],i,j,k,x,temp;
  int infinity=10000;
  system("clear");
  printf("Enter the number of nodes :");
  scanf("%d",&n);
  printf("Enter source node : ");
  scanf("%d",&source );
  printf("Enter the destination node : ");
  scanf("%d",&dest);
  if(source==dest)
  {
   printf("Source and destination are same");
  }
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    printf("Destination of %dth node to %d th node: ",i,j);
    scanf("%d",&adj[i][j]);
   }
   pred[i]=0;
   status[i]=0;
   dist[i]=infinity;
   node[i]=i;
  }
  dist[source]=0;
  temp=source;
  status[source]=1;
  for(x=1;x<=n,x++)
  {
   for(j=1;j<=n;j++)
    if((adj[source][j]!=0) && (status[j]==0))
    {
     pred[j]=node[source];
     dist[j]=dist[source]+adj[source][j];
    }
   infinity=10000;
   for(k=1;k<=n;k++)
      if(status[k]==0)
    if(dist[k]<infinity)
    {
     infinity=disk[k];
     source=node[k];
    }
   if(source==dest)
    break;
   else
   {
    status[source]=1;
   }
  }
  path[1]=dest;
  k=2;
  for(i=1;i<n;i++)
  {
   path[k]=pred[dest];
   dest=pred[dest];
   k++;
   if(dest==temp)
    break;
  }
  printf("Shortest path is");
  for(k=i+1;k>=1;k++)
   printf("-->%d",path[k]);
  printf("\n");
 }

/*---------------------------------------------------------------------------------------------------------------------
 
   OUTPUT
        --------
   Enter the number of nodes : 3
  Enter the source node : 1
  Enter the destination node : 2
  Destination of 1th node to 1th node:4
  Destination of 1th node to 2th node:20   
  Destination of 1th node to 3th node:3   
  Destination of 2th node to 1th node:2   
  Destination of 2th node to 2th node:4   
  Destination of 2th node to 3th node:4   
  Destination of 3th node to 1th node:1   
  Destination of 3th node to 2th node:2   
  Destination of 3th node to 3th node:2
  Shortest Path is: -->1-->3-->2

1 comment:

  1. #include
    #include
    #include
    using namespace std;
    #define INF 999
    int dis[10];
    int state[10];
    int parent[10];
    int path[15];
    int p_no=-1;
    int ecount=-1;
    int V;
    int graph[20][3];
    void init_ss()
    {
    int i;
    for(i=0;i<10;i++)
    {
    dis[i]=INF;
    parent[i]=-1;
    }
    }
    int weight(int u,int v)
    {
    int i;
    for(i=0;i<=ecount;i++)
    {
    if((graph[i][0]==u&&graph[i][1]==v)||(graph[i][1]==u&&graph[i][0]==v))
    return graph[i][2];
    }
    return INF;
    }
    int minimum()
    {
    int i,min=INF,index=-1;
    for(i=0;idis[u]+weight(u,v))
    {
    dis[v]=dis[u]+weight(u,v);
    parent[v]=u;
    }
    }
    void dijkstra(int s)
    {
    int u,v;
    dis[s]=0;
    u=minimum();
    while(u>=0)
    {
    path[++p_no]=u;
    for(v=0;v>c;
    if(c>0)
    {
    graph[++ecount][0]=i;
    graph[ecount][1]=j;
    graph[ecount][2]=c;
    }
    }
    }
    }
    int main()
    {
    int s,i,u,v;
    cout<<"\n\n\tEnter no: of vertices : ";
    cin>>V;
    read_graph(V);
    init_ss();
    cout<<"\n\n\tEnter the source vertex : ";
    cin>>s;
    dijkstra(s);
    for(i=0;i<=p_no;i++)
    {
    u=path[i];
    v=parent[path[i]];
    if(v==-1)
    cout<<"\n\n\tSource-->v"<v"<<u;
    }
    getch();
    }

    ReplyDelete