Welcome to our community

Be a part of something great, join today!

Question about Dynamic programming-Shortest Path Problem

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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
Mar 5, 2012
8,777
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
Apr 14, 2013
4,047
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
Apr 14, 2013
4,047
What is meant by writing the problem as a shortest path problem?
 
Last edited:

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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? :confused: Could you give me an example because I'm really confused..
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,777
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
Jan 30, 2012
2,492
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
Apr 14, 2013
4,047
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
Jan 30, 2012
2,492
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
Apr 14, 2013
4,047
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?

dir_gr.png
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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.. :confused:
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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.. :confused:
I got it now...your answers were helpful!!