Question about Dynamic programming-Shortest Path Problem

In summary, the problem involves grouping n things into clusters with adjacent things while minimizing the total cost of the clusters. To write it as a shortest path problem, we can construct a directed graph with vertices 1 to n+1 and edges from i to j with weight c_ij-1. The last vertex is n+1 to account for using c_in. This bijection between partitions and paths from 1 to n+1 allows us to find the minimal cost by finding the shortest path.
  • #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}$??
 
Mathematics news on Phys.org
  • #2
mathmari said:
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.
 
  • #3
I like Serena said:
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 by a moderator:
  • #4
What is meant by writing the problem as a shortest path problem?
 
Last edited by a moderator:
  • #5
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..
 
  • #6
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.
 
  • #7
mathmari said:
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$.
 
  • #8
Evgeny.Makarov said:
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 by a moderator:
  • #9
mathmari said:
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.

mathmari said:
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.
 
  • #10
Evgeny.Makarov said:
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?

View attachment 1793
 

Attachments

  • dir_gr.png
    dir_gr.png
    12.9 KB · Views: 72
  • #11
Evgeny.Makarov said:
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:
 
  • #12
mathmari said:
For example for n=5, is the graph the following?
Yes.
 
  • #13
mathmari said:
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!
 

FAQ: Question about Dynamic programming-Shortest Path Problem

What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them down into smaller subproblems and finding the optimal solution for each subproblem. The solutions to the subproblems are then combined to find the overall optimal solution.

What is the Shortest Path Problem?

The Shortest Path Problem is a classic optimization problem in computer science, where the goal is to find the shortest path between two nodes in a graph. It is commonly used in navigation systems and routing algorithms.

How is Dynamic Programming used to solve the Shortest Path Problem?

In Dynamic Programming, the shortest path problem is solved by breaking it down into smaller subproblems and recursively finding the shortest path for each subproblem. This approach significantly reduces the time complexity of finding the shortest path in a graph.

What are the advantages of using Dynamic Programming for the Shortest Path Problem?

Dynamic Programming offers several advantages for solving the Shortest Path Problem, including improved time complexity, the ability to handle complex and large graphs, and the ability to find the shortest path between multiple pairs of nodes in a single run.

Are there any limitations to using Dynamic Programming for the Shortest Path Problem?

While Dynamic Programming is a powerful approach to solving the Shortest Path Problem, it may not be suitable for all types of graphs and may require a significant amount of memory for storing subproblem solutions. Additionally, it may not be the most efficient solution for certain types of graphs, such as those with negative weight edges.

Similar threads

Replies
1
Views
1K
Replies
19
Views
2K
Replies
5
Views
3K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Back
Top