Write a program to solve the single-source shortest-path problem that gives this output Sample Output: Enter the number of vertices in the graph: 7
Enter the adjacency matrix of the graph Type 1111 to enter infinity
Enter non-negative weights for the row 0 0 5 3 1111 1111 1111 1111
Enter non-negative weights for the row 1 1111 02 1111 3 1111 1
Enter non-negative weights for the row 2 1111 1111 0 7 7 1111 1111
Enter non-negative weights for the row 3 2 1111 1111 0 1111 6 1111
Enter non-negative weights for the row 4 1111 1111 1111 2 0 1 1111
Enter non-negative weights for the row 5 1111 1111 1111 1111 1111 0 1111
Enter non-negative weights for the row 6 1111 1111 1111 1111 1 1111 0
Enter the source vertex: 0 a_0 rightarrow 0 a_b_rightarrow 5 a_c_rightarrow 3 a_b_g_e_d_rightarrow 9 a_b_g_e_rightarrow 7 a_b_g_e_f_rightarrow 8 a_b_g_rightarrow 6

Following are the code to this question:

#include<iostream>//defining a header file

using namespace std;//using namespace

const int data=1111;//defining const integer variable data  

int main()//defining main method

{

int i,j,k,number,source;//defining integer variables

int m[10][10];//defining 2 dimensonal arry m

int c[10][10];//defining 2 dimensonal arry c

cout<<"Enter the number of vertices in the graph:";//print message

cin>>number; // input value in number variable

cout<<"Enter the adjecent matrix of the graph:\n";//print message

for(i=0;i<number;i++)//defining loop for input weight values to c array  

{  

cout<<"Enter non negative weights for the row "<<i<<":";//print message

for(j=0;j<number;j++)//loop for input value

{

   cin>>c[i][j];//input value  

}

}

//defining loop for check element value equal to 0

for(i=0;i<number;i++)//loop for columns value

{

for(j=0;j<number;j++)//loop for rows value

{

if(c[i][j]==0) //defining if block that checks element value equal 0

m[i][j]=data; // defining m array to set data value

else //defining else block

m[i][j]=c[i][j]; //use the m array to c array value

}

}

cout<<"Adjecent matrix of cost of edges:\n";//print message

for(i=0;i<number;i++)//defining loop for print columns value

{

for(j=0;j<number;j++)//defining loop for print rows value

{

cout<<m[i][j]<<"\t";//print value using Dijkstra's algorithm  

cout<<"\n";

}

}  

//use Dijkstra's algorithm for find short path

for(k=0;k<number;k++)//defining loop for  

{  

for(i=0;i<number;i++)//defining loop for print columns value

{

for(j=0;j<number;j++)//defining loop for print rows value

{

if(m[i][j]>m[i][k]+m[k][j])//defining if block to calculate Dijkstra value

{

m[i][j]=m[i][k]+m[k][j];//use m array to store Dijkstra value

}

}

}

}

cout<<"Adjecent matrix of lowest cost between the vertices:\n"; // print full matrix after implementing the algorithm

for(i=0;i<number;i++)//defining loop for print columns value

{

for(j=0;j<number;j++)//defining loop for print rows value

{

cout<<m[i][j]<<"\t";//print m array

cout<<"\n";

}

}

cout<<"Enter the source vertex:";//print message

cin>>source; //use s variable for input source value

m[source][source]=0;//use m array that store a value 0

for(j=0;j<number;j++)//defining loop for print value

cout<<m[0][j]<<"\n"; //print shortest path

return 0;

}

Output:

Enter the number of vertices in the graph:7

Enter the adjecent matrix of the graph:

Enter non negative weights for the row 0:0 5 3 0 0 0 0

Enter non negative weights for the row 1:0 0 2 0 3 0 1

Enter non negative weights for the row 2:0 0 0 7 7 0 0  

Enter non negative weights for the row 3:2 0 0 0 0 6 0

Enter non negative weights for the row 4:0 0 0 2 0 1 0

Enter non negative weights for the row 5:0 0 0 0 0 0 0

Enter non negative weights for the row 6:0 0 0 0 1 0 0

Adjecent matrix of cost of edges:

1111531111111111111111  

111111112111131111    1  

1111111111117711111111  

2111111111111111161111  

1111111111112111111111  

1111111111111111111111111111  

1111111111111111111111111  

Adjecent matrix of lowest cost between the vertices:

11539786  

61124231  

9141277815  

27511968  

497211110  

1111111111111111111111111111  

510831211  

Enter the source vertex:0

0

5

3

9

7

8

6

Explanation:

In the above given C++ language code, a constant integer variable data is defined, that store an integer value that is "1111", inside the main method, integer variable "i, j, k, number, and source" is defined, in which "i, j, and k" is used in the loop and "number, and source" is used for input the value.

In the next step, two arrays "c and m" is defined, that uses the multiple for loop and conditional block, in which "c" is used to input the value from the user end and apply the "Dijkstra algorithm" and uses the m array to calculate the Dijkstra algorithm value and print its value.    

answer

it would be true.