FloydWarshall Algorithm With Path Printing

Back To Coding ...
Below code is for Finding All Pair Shortest Path Using Floyd Warshall Algorithm . Floyd Warshall Algorithm has O(n^3) time complexity and O(n^2) Space complexity .

Below code  is able to display the paths traverse between nodes .


#include<stdio.h>
#define size 4
#define INF 234334

int pathMatrix[size][size];

void pathdisplay(int pathMatrix[size][size],int u,int v);

void floydWarshall(int graph[][size]);
void display(int graph[][size]);
void main()
{

  int u,v;
  int vertex[size][size]={ {0,11,1,6},
                        {11, 0,7, 3},
                        {1, 7, 0, 2},
                        {6,3,2, 0}
                    };


  floydWarshall(vertex);

/*printf("Enter u \n");
scanf("%d",&u);
printf("Enter v \n");
scanf("%d",&v);
*/

for(u=0;u<size;u++)
{
  for(v=0;v<size;v++)
{
pathdisplay(pathMatrix,u,v);
printf("\n");
}
  printf("\n");
}
}

void floydWarshall(int vertex[size][size])
{
int graph[size][size];
int i,j,k;

for(i=0;i<size;i++)
{
  for(j=0;j<size;j++)
  {
    graph[i][j]=vertex[i][j];
    pathMatrix[i][j]=i;
  }
}


for(k=0;k<size;k++)
{
  for(i=0;i<size;i++)
  {
    for(j=0;j<size;j++)
    {
      if(graph[i][k]+graph[k][j]<graph[i][j])
      {

      graph[i][j]=graph[i][k]+graph[k][j];
      pathMatrix[i][j]=k;
    }
    }
  }
}
display(graph);
printf("\n\nPathMatrix\n");
display(pathMatrix);

}


void display(int graph[size][size])
{
int i,j;
for(i=0;i<size;i++)
{
  for(j=0;j<size;j++)
  {
   printf("%d ",graph[i][j]);
  }
  printf("\n");
}
}

void pathdisplay(int pathMatrix[size][size],int u,int v)
{
  if(u==v)
  printf("-> %d ",u);
   else if(pathMatrix[u][v]==INF)
        printf("No Path Exits\n");
     else
     {
     pathdisplay(pathMatrix,u,pathMatrix[u][v]);
      printf("-> %d ",v);
      }

}

UOH Ethnic Day Celebration Photos and Videos

UOH Ethnic Day 14 Sep 2018 Photos and Videos 

Charming Ramp Walk UOH 

Ethnic Day Promo Trailer 

Ethnic Day Ending Ceremony Video . Guest was Mrs Hari Chandana ,alumnus of UOH .Now she is Commissioner GHMC .

Best Dance Performance BY Bhargavi Das And Shanti Priya on UOH Ethnic Day | Super Performance

Ne Kanchinghon La Nepi Karbi Poem By Amphu Terangpi | Ethnic Day UOH 

Chatak Matak Dance by Student | UOH Ethnic Day

Bodo Dance performed at UOH Ethnic Day in HD

 

Beautiful Bharatanatyam performed at University Of Hyderabad ETHNIC DAY  

Guitar Performance at University Of Hyderabad Ethnic Day

Ramp Walk Video will available on Friday .

UOH Ethnic Day Photos

https://drive.google.com/open?id=1Fun9h5K_xp_kMjReitHSGGTQ1Gki0qSq

Please share the below link to your  friends .

http://hemchandralive.blogspot.com/2018/09/uoh-ethnic-day-celebration-photos-and.html

Knowledge Representation And Reasoning (KRR) Study Material and Slides

Welcome in hemchandralive.blogspot.com .

This page is Only for student of  University Of Hyderabad . 

KRR Subject Complete Slides  are below :

https://drive.google.com/open?id=0Bwe6MpkMbNMxdDNGYkUxREZBSVdtU3pQRDRSclpHb2IzYkJv

KRR Subject Some Question Papers

https://drive.google.com/open?id=0Bwe6MpkMbNMxeU9tU1B5RGxubE5pX3pVX2J1bXBZN0FEX2JJ

Below video is of University Of Hyderabad Ethnic Day 

Josephus Problem Solution Using Circular Linked List

The problem statement: 

There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

 
Josephus Problem Solution Using Circular Linked List in C :

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int num;
    struct node *next;
};
struct node *head=NULL;

void create();
void display();
int survivor(int);

int main()
{
int survive,skip;
create();
display();   
printf("Enter the number of persons to be skipped\n");
scanf("%d",&skip);
survive=survivor(skip);
printf("The person to survive is : %d \n",survive);
free(head);
}

void create()
{
    struct node *temp,*rear;
    int a,ch;
    do
    {
        printf("Enter a number : ");
        scanf("%d",&a);
        temp=(struct node *)malloc(sizeof(struct node));
        temp->num=a;
        temp->next=NULL;
       
        if(head==NULL)
        {
            head=temp;
            temp->next=head;
        }
        else
        {
            rear=head;
            while(rear->next!=head)
            {
                rear=rear->next;
            }
            rear->next=temp;
            temp->next=head;
        }
       
        printf("Do you want to add a number [1/0]?");
        scanf("%d",&ch);
    }
    while(ch!=0);
}

void display()
{
    struct node *temp;
    temp=head;
    do
    {
        printf("%d ",temp->num);
        temp=temp->next;
    }
    while(temp!=head);
    printf("\n");
}


int survivor(int k)
{
    struct node *p,*q;
    int i;
    p=q=head;
    while(p->next!=p)
    {
        for(i=0;i<k-1;i++)
        {
            q=p;
            p=p->next;
        }
        q->next=p->next;
        printf("%d has been killed \n",p->num);
        free(p);
        p=q->next;
    }
    head=p;
    return (p->num);
}