This is a C++ Program that Solves Trigraphs Problem using Dynamic Programming technique.
A tri-graph is an acyclic graph of (N >= 2) rows and exactly 3 columns. Unlike regular graphs, the costs in a tri-graph are associated with the vertices rather than the edges.
The problem is to find the shortest path from the top-middle vertex to the bottom-middle vertex in a given tri-graph.
This is a simple DP problem. Proceed in a bottom up fashion from the top middle vertex to the bottom middle vertex. In each iteration, find the cost of reaching all the three vertices of the current row and use this information to calculate values for the next row and so on.
Case-1:
number of rows=1 weights of vertices of rows 22 45 53 Cost of shortest path=45
Case-2:
number of rows=1 weights of vertices of rows 12 43 55 21 46 22 42 84 51 5 18 7 23 75 12 Cost of shortest path=186
Case-3:
number of rows=4 weights of vertices of rows 13 7 5 7 13 6 14 3 12 15 6 16 Cost of shortest path=22
Here is source code of the C++ Program to solve Trigraphs problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
//trigraphs
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int x,y,z;
int a,b,c;
int i;
cout<<"Enter the number of rows in the trigraph"<<endl;
cin>>n;
cout<<"Enter the weight of vertices in each row "<<endl;
cin>>a>>b>>c;
c=b+c;
a=INT_MAX;
for(i=1;i<n;i++)
{
cin>>x>>y>>z;
x=min(a,b)+x;
y=min(min(x,a),min(b,c))+y;
z=min(min(y,b),c)+z;
a=x;
b=y;
c=z;
}
cout<<"Cost of the shortest path from the top middle vertex to the bottom middle vertex equals "<<endl<<b<<endl;
return 0;
}
In the main function, we take the input for number of rows in the trigraph. Then for each row, we take the input for vertex weights and calculate the minimum cost to reach them. Finally the result is displayed.
Case-1: $ g++ trigraphs.cpp $ ./a.out Enter the number of rows in the trigraph 4 Enter the weight of vertices in each row 13 7 5 7 13 6 14 3 12 15 6 16 Cost of the shortest path from the top middle vertex to the bottom middle vertex equals 22 Case-2: $ ./a.out Enter the number of rows in the trigraph 1 Enter the weight of vertices in each row 22 45 53 Cost of the shortest path from the top middle vertex to the bottom middle vertex equals 45 Case-3: $ ./a.out Enter the number of rows in the trigraph 5 Enter the weight of vertices in each row 12 43 55 21 46 22 42 84 51 5 18 7 23 75 12 Cost of the shortest path from the top middle vertex to the bottom middle vertex 186
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Data Structure Books
- Practice Design & Analysis of Algorithms MCQ
- Check Computer Science Books