# Question about Dynamic programming-Shortest Path Problem

#### mathmari

##### Well-known member
MHB Site Helper
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}$??

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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}$??
Things? What kind of things?
Marbles?
That's important!

Hmm, are you sure you're supposed to use a shortest path algorithm?
Seems to me it should be a minimal spanning tree (or forest).
I think that for a general problem you would need to specify an algorithm.

#### mathmari

##### Well-known member
MHB Site Helper
Things? What kind of things?
Marbles?
That's important!

Hmm, are you sure you're supposed to use a shortest path algorithm?
Seems to me it should be a minimal spanning tree (or forest).
I think that for a general problem you would need to specify an algorithm.
At the first subquestion I have to write the problem as a shortest path problem, at the second subquestion I have to specify an algorithm, and at the third I have to apply this algorithm in a specific problem.

We could consider the problem as a system of nodes (0,...,n) and curves $\text arc(i,j)$ with $j>i$. Each $\text arc(i,j)$ with $i<n$ corresponds to a cluster of edges $i+1,i+2,...,j$, whose cost is $c_{ij}$, while $\text arc(n,n)$ has cost $0$.

Last edited:

#### mathmari

##### Well-known member
MHB Site Helper
What is meant by writing the problem as a shortest path problem?

Last edited:

#### mathmari

##### Well-known member
MHB Site Helper
To understand the exericse, to find the grouping so that the total cost is minimal, do I have to find the shortest path? Or how can I find it? Could you give me an example because I'm really confused..

#### Klaas van Aarsen

##### MHB Seeker
Staff member
The problem statement for the shortest path problem is finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

In my opinion that really does not apply to your problem.
So I think it may be a typo.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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.
I assume $i$ and $j$ in $c_{ij}$ are indices of the first and last objects in a cluster; thus there is a $c_{ij}$ for each $1\le i\le j\le n$.

I suggest checking if the following idea works. Given a grouping problem, we construct a directed graph. The vertices are $1,\dots,n+1$. There is an edge from $i$ to $j$ iff $i<j$, and its weight is $c_{ij-1}$. Then the minimum grouping cost is the shortest distance between 1 and $n+1$.

#### mathmari

##### Well-known member
MHB Site Helper
I assume $i$ and $j$ in $c_{ij}$ are indices of the first and last objects in a cluster; thus there is a $c_{ij}$ for each $1\le i\le j\le n$.

I suggest checking if the following idea works. Given a grouping problem, we construct a directed graph. The vertices are $1,\dots,n+1$. There is an edge from $i$ to $j$ iff $i<j$, and its weight is $c_{ij-1}$. Then the minimum grouping cost is the shortest distance between 1 and $n+1$.
Could you explain me why the weight for the edge from $i$ to $j$ iff $i<j$ is $c_{ij-1}$ ?
And also, why are the vertices denoted till $n+1$ ?

Last edited:

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Could you explain me why the weight for the edge from $i$ to $j$ iff $i<j$ is $c_{ij-1}$ ?
Are you wondering why the edge from $i$ to $j$ corresponds to $c_{ij-1}$ as opposed to $c_{ij}$? For one, a segment consisting of one object #$i$ makes sense and has a cost $c_{ii}$. On the other hand, a loop is never a part of the shortest path.

And also, why are the vertices denoted till $n+1$ ?
If you need to employ $c_{in}$ and, according to the reasoning above, the second index is the result of subtracting 1, then the last vertex should be $n+1$.

For each partitioning problem you get a direct graph. You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length. Then minimal length would correspond to minimal cost.

#### mathmari

##### Well-known member
MHB Site Helper
Are you wondering why the edge from $i$ to $j$ corresponds to $c_{ij-1}$ as opposed to $c_{ij}$? For one, a segment consisting of one object #$i$ makes sense and has a cost $c_{ii}$. On the other hand, a loop is never a part of the shortest path.

If you need to employ $c_{in}$ and, according to the reasoning above, the second index is the result of subtracting 1, then the last vertex should be $n+1$.

For each partitioning problem you get a direct graph. You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length. Then minimal length would correspond to minimal cost.
For example for n=5, is the graph the following?

#### mathmari

##### Well-known member
MHB Site Helper
You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length.
Could you give me a hint how to do this? I have not really understood the relation between the grouping problem and the shortest path problem..

MHB Math Scholar

#### mathmari

##### Well-known member
MHB Site Helper
Could you give me a hint how to do this? I have not really understood the relation between the grouping problem and the shortest path problem..