Trigraphs Problem using Dynamic Programming

This is a C++ Program that Solves Trigraphs Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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.

Expected Input and Output

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:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
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

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

If you find any mistake above, kindly email to [email protected]

« Prev - Mixtures Problem using Dynamic Programming

» Next - Army Problem – Dynamic Programming Solutions

Related Posts:

Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Apply for Computer Science Internship
Practice Programming MCQs

Recommended Articles: