- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Given a set of n things (1,2,...,n), we want to group them in clusters that contain adjacent things. For each cluster there is a cost $c_{ij}$. We are looking for the grouping in clusters so that the total cost is minimal.
I am asked to write this problem as a shortest path problem.
What do I have to do?
Do I have to draw a directed weighted graph?
Since the problem is general, do I have to draw the first vertex, the last vertex, and some between them for example the vertex $i$ and $j$,and at the edge from $i$ to $j$ there is a cost $c_{ij}$??
I am asked to write this problem as a shortest path problem.
What do I have to do?
Do I have to draw a directed weighted graph?
Since the problem is general, do I have to draw the first vertex, the last vertex, and some between them for example the vertex $i$ and $j$,and at the edge from $i$ to $j$ there is a cost $c_{ij}$??