Answer:
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:\\";//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:\\";//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<<"\\";
}
}
//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:\\"; // 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<<"\\";
}
}
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]<<"\\"; //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:
1111 5 3 1111 1111 1111 1111
1111 1111 2 1111 3 1111 1
1111 1111 1111 7 7 1111 1111
2 1111 1111 1111 1111 6 1111
1111 1111 1111 2 1111 1 1111
1111 1111 1111 1111 1111 1111 1111
1111 1111 1111 1111 1 1111 1111
Adjecent matrix of lowest cost between the vertices:
11 5 3 9 7 8 6
6 11 2 4 2 3 1
9 14 12 7 7 8 15
2 7 5 11 9 6 8
4 9 7 2 11 1 10
1111 1111 1111 1111 1111 1111 1111
5 10 8 3 1 2 11
Enter the source vertex:0
0
5
3
9
7
8
6
Step-by-step 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.