Question

1.What does a file index do? Why do we need a file index?

2.Modified All-Pairs Shortest Paths Problem

This is the All-Pairs Shortest Paths problem with the following modification. Let n be the number of nodes in input graph. There are additional inputs  k1, d in [1..n]. For every path that starts at, or ends at, or passes through node k1,distance d is added to the total distance of the path. Calculate shortest distances for all pairs of nodes (as in the original problem).

Write a program that solves the above problem. in c-language

The format of the input will be the following:

n k1, d (the number of nodes, node k1, and added distance d, e.g. 10 5 3)

i j w (direct edge from i to j with weight w; e.g. 2 3 8)

Answer 1

Answer 1:

   A file index is basically found in a file which contains an index. The index in the file basically allows easy random access to any file with the help of a particular key. The key should be unique. The key is used to identify a unique record in a table.

                                 We need a file index for sequential searching of a data in comparatively lesser time. The key in the file index helps us to uniquely identify a record.

Modified version:

#include <stdio.h>

#define infinity 9999

#define MAX 20

int minimum(int a,int b)

{

            if(a<=b)

            return a;

            else

            return b;

}/*End of minimum()*/

int display(int matrix[MAX][MAX],int n )

{

            int i,j;

            for(i=0;i<n;i++)

            {

                        for(j=0;j<n;j++)

                                    printf("%7d",matrix[i][j]);

                        printf("\n");

            }

}/*End of display()*/

main()

{

            int i,j,k,n;

            int adj[MAX][MAX],path[MAX][MAX];

            printf("Enter number of vertices : ");

            scanf("%d",&n);

            printf("Enter weighted matrix :\n");

            for(i=0;i<n;i++)

               for(j=0;j<n;j++)

                        scanf("%d",&adj[i][j]);

            printf("Weighted matrix is :\n");

            display(adj,n);

            /*Replace all zero entries of adjacency matrix with infinity*/

            for(i=0;i<n;i++)

               for(j=0;j<n;j++)

               if(adj[i][j]==0)

                        path[i][j]=infinity;

               else

                        path[i][j]=adj[i][j];

            for(k=0;k<n;k++)

            {

                        printf("Q%d is :\n",k);

                        display(path,n);

                        for(i=0;i<n;i++)

                        for(j=0;j<n;j++)

                            path[i][j]=minimum( path[i][j] , path[i][k]+path[k][j] );

            }

            printf("Shortest path matrix Q%d is :\n",k);

            display(path,n);

}