# 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:

```
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.

1. ` `
2. `//trigraphs`
3. `#include<bits/stdc++.h>`
4. `using namespace std;`
5. ` `
6. `int main()`
7. `{`
8. `    int n;`
9. `    int x,y,z;`
10. `    int a,b,c;`
11. `    int i;`
12. ` `
13. `    cout<<"Enter the number of rows in the trigraph"<<endl;`
14. `    cin>>n;`
15. ` `
16. `    cout<<"Enter the weight of vertices in each row "<<endl;`
17. ` `
18. `    cin>>a>>b>>c;    `
19. `    c=b+c;`
20. `    a=INT_MAX;`
21. ` `
22. `    for(i=1;i<n;i++)`
23. `    {`
24. `        cin>>x>>y>>z;`
25. ` `
26. `        x=min(a,b)+x;`
27. `        y=min(min(x,a),min(b,c))+y;`
28. `        z=min(min(y,b),c)+z;`
29. ` `
30. `        a=x;`
31. `        b=y;`
32. `        c=z;`
33. `    }`
34. ` `
35. `    cout<<"Cost of the shortest path from the top middle vertex to the bottom middle vertex equals "<<endl<<b<<endl;`
36. ` `
37. `    return 0;`
38. `}`
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.