Question

write a program that will find the shortest path from a given vertex to a given vertex. Your program must allow the user to enter any start vertex and any destination vertex and output the shortest path.

A B F E D Using the attached graph, write a program that will find the shortest path from a given vertex to a given vertex. Your program must allow the user to enter any start vertex and any destination vertex and output the shortest path. Also send cpp as email attachment

Answer 1

C++ code for above problem

#include<iostream>
using namespace std;

#define V 6
#define MAX 9999999

void floyd_warshall(int graph[][V],int distances[][V])
{
   for(int i=0;i<V;i++)
   {
        for(int j=0;j<V;j++)
        {
           distances[i][j]=graph[i][j];
           if(i!=j && distances[i][j]==0)
           {
               distances[i][j]=MAX;
           }
        }
    }

   for(int k=0;k<V;k++)
    {
        for(int i=0;i<V;i++)
       {
            for(int j=0;j<V;j++)
            {
               distances[i][j]=min(distances[i][j],distances[i][k]+distances[k][j]);
            }
        }
    }
}  

int main()
{
   int graph[V][V]={{0,1,0,0,1,0},
                   {1,0,1,0,0,1},
                   {0,1,0,1,0,0},
                   {0,0,1,0,1,0},
                   {1,0,0,1,0,1},
                   {0,1,0,0,1,0},
                   };
                  
   int distances[V][V];
   floyd_warshall(graph,distances);
  
   char src,dest;
   cout << "Enter source vertex: ";
   cin >> src;
  
   cout << "Enter destination vertex: ";
   cin >> dest;
  
   cout << "Distance from " << src << " to " << dest << ": " << distances[src-'A'][dest-'A'] << endl;
  
   return 0;
}

Sample output

Enter source vertex: A Enter destination vertex: D Distance from A to D: 2

Mention in comments if any mistakes or errors are found. Thank you.