Shortest path problem-minimal cost

Question

Given a set of m things (1,2,...,m), 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?

Answer 1

You need to describe a directed, weighted graph so that there is a correspondence between paths (between two particular vertices) and a particular choice of clusters, and so that the shortest path corresponds to the lowest-cost grouping; then you should demonstrate that this correspondence holds.

Hint: Make a graph with an edge from $i$ to $j$ with cost $c_{i(j-1)}$ for each pair $1\leq i<j\leq m+1$. Why does finding the shortest path from $1$ to $m+1$ solve your problem?