Question

Recall the Matrix-Multiplication Algorithm for determining all-pairs distances in a graph. Provide a linear-time recursive implementation of the function
void print_path(Matrix D[], int n, int i, int j);
that takes as input the array of matrices D[1], D[2], . . . , D[n − 1] that have been computed by the algorithm, and prints the optimal path from vertex i to vertex j. Hint: for convenience you may use the notation Dr ij to denote the value D[r][i, j], i.e. entry i, j of matrix D[r].

Answer 1

Solution:

/* save file name as allpair.cpp */
// with .cpp extension


#include <iostream>
#include <cstdlib>
#define max 10
#define infi 999
using namespace std;
int p[max][max];

// All Pairs Shortest Path using Floyd's Algorithm

void allpairshortPath(int D[max][max], int n)
{
    int k, i, j;
    for (k = 0; k < n; k++)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if (D[i][k] + D[k][j] < D[i][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                    p[i][j] = k;
                }
            }
        }
    }
}
 
/*
 * Storing the shortest path
 */
void shortest(int i, int j)
{
    int k = p[i][j];
    if (k > 0)
    {
        shortest(i, k);
        cout<<"  "<<k<<"  ";
        shortest(k, j);
    }
}
/*
 * Display the Shortest Path
 */
void Print_path(int D[max][max], int i, int j, int n)
{
    cout<<"Optimal Path from vertex " << i <<" to  vertex "<< j << ":";
    if (D[i][j]  < infi)
    {
            cout<<"  "<<i<<"  ";
            shortest(i, j);
            cout<<"  "<<j<<" ";
    }
}
/*
 * Drive main function
 */
int main()
{
    //i is initial vertex or starting vertex and j is final vertex
    int i, j;
   //matrix of 4 x 5 that 4 row 5 column
    int D[][10] =  {{0, 10, infi, 30, 100},
                {infi, 0 , 50, infi, infi},
                {infi, infi , 0, infi, 10},
                {infi, infi , 20, 0, 60},
                {infi, infi , infi, infi, 0},
                };
   // function call
    allpairshortPath(D, 5);
    i=0;j=4;
    Print_path(D, i, j, 5);
    cout<<endl;
    return 0;
}

The above program includes Floyd Warshal Algorithm implementaion for finding all pair shortest path

In the above code all sortest path distance stored in matrix P and for given condition to find or print sort path

that prints the sortest path.

n denotes number of column and i initial vertex and j is final vertex.

The above code includes three function

1.allpairsortestPath(): This function takes argument as matrix d and n number of column and after that apply Floyd Warshall algorithm to calculating all pair sortest path

Algorithm :distance form vertex i to j via k

2.Sortest() :This is recursive function to chek distnace for i to j via k.

3.print_path(): print _path() function includes sortest function to check sortest path and printing them. it takes matrix D intial vertes as i and final vertex and j and number of column as n.

OUTPUT1.

The above image showing the sortest path for given matrix D of 4 row and 5 coloumn values.

Since in the matrix vertex 0 is starting vertex its sortest distence is 0 and final vertex is 4 and showing the

sortest path as 0 3 2 4

Screen sort of code: in given sequence

1.

2.

3.

/* if any confusion please comment kindly */