# Find path to minimum cost from start to finish

• MHB
• mathmari
In summary, the conversation discusses a problem involving finding the minimum cost path on a game board with positive numbers assigned to each square. The proposed solution involves converting the board into a weighted graph and using Dijkstra's algorithm to find the shortest path. There is also a discussion about the directionality of the graph and the possibility of certain moves being restricted.
mathmari
Gold Member
MHB
Hey!

I am looking the following:
The board of a game is an $M \times N$ board with squares, where the starting point is on left - in position $(0, 0)$ - and the finish is in the lower right - in position $(M-1, N-1)$. Each square contains a positive number that describes the cost of moving to pass through this specific square. Design and analyze an algorithm that finds the path to minimum cost from start to finish considering that we can move up, down, right or left. For example, in the table below the minimum cost is 35 and is given by the designed path.

For this problem I have the following idea:

We convert this table into a graph, specifically a weighted graph with weights the cost of each square. In this way the problem will be to find the shortest path of the graph, right? :unsure:

That graph that we get is not directed, is it? :unsure:

Hey mathmari!

Yep. That will work. (Nod)

Suppose we move from square (0,0) to (0,1), what will be the weight that we assign to this path?
And what is the weight if we move from (0,1) to (0,0)?

Klaas van Aarsen said:
Suppose we move from square (0,0) to (0,1), what will be the weight that we assign to this path?

Isn't it equal to $1+3=4$ ? :unsure:

Klaas van Aarsen said:
And what is the weight if we move from (0,1) to (0,0)?

Isn't it $3=1=4$ ? :unsure:

Suppose we are at the point $(i,j)$ then the possible moves are up, left , right, down, i.e to go to $(i-1,j)$, $(i,j-1), (i,j+1), (i+1, j)$, right? :unsure:

So for the pseudocode, do we get the following?

Code:
    Algorithm Minimum_Cost_Path
Input: Numbers M, N, Set S of number of each square (i,j) on board
Output: Minimum Cost Path from (0,0) to (M-1, N-1)
G <- new empty graph
for i <- 0 to M-1 do
for j <- 0 to N-1 do
for i <- 0 to M-1 do
for j <- 0 to N-1 do
G.AddEdge( (i,j), (i-1,j), S( i-1,j ) )
G.AddEdge( (i,j), (i,j-1), S( i,j-1 ) )
G.AddEdge( (i,j), (i,j+1), S( i,j+1 ) )
G.AddEdge( (i,j), (i+1,j), S( i+1,j ) )

Now we have created the graph, right? Is that correct so far? :unsure:

Now we far to call an algorithm that calculates a shortest path. Do we apply Dijkstra because we have only positive weights and we are looking for a path between two specific vertices? :unsure:

mathmari said:
Isn't it equal to $1+3=4$ ?
Isn't it $3=1=4$ ?

Doesn't that mean that if we follow (0,0) -> (0,1) -> (0,0) that we get a weight of (1+3)+(3+1)=8?
That is, aren't we counting the 3 twice when we should only count it once?

What I mean, is that I believe we need a directed graph, which is actually what you implemented in your algorithm.

Suppose we are at the point $(i,j)$ then the possible moves are up, left , right, down, i.e to go to $(i-1,j)$, $(i,j-1), (i,j+1), (i+1, j)$, right?

Now we have created the graph, right? Is that correct so far?

Shouldn't we consider that not every edge is possible since some of the destinations are "off the board"?

Btw, don't forget to keep track of the starting and ending vertices in G.

Now we far to call an algorithm that calculates a shortest path. Do we apply Dijkstra because we have only positive weights and we are looking for a path between two specific vertices?
Yep. (Nod)

I don't know how to apply the programming that well anymore but what if there is a path that goes 1, 4, 1, 1, .. that is the actual lowest cost? Your algorithm wouldn't find that, would it? Your path finds the lowest cost by adding the lowest cost at each step, not necessarily the lowest path on the board.

-Dan

Klaas van Aarsen said:
Doesn't that mean that if we follow (0,0) -> (0,1) -> (0,0) that we get a weight of (1+3)+(3+1)=8?
That is, aren't we counting the 3 twice when we should only count it once?

What I mean, is that I believe we need a directed graph, which is actually what you implemented in your algorithm.

I haven't really understood how it follows that the graph has to be directed. Could you explain that further to me? :unsure:
Klaas van Aarsen said:
Shouldn't we consider that not every edge is possible since some of the destinations are "off the board"?

Ahh sowe have to consider some restrictions if the point is on the edges, right? :unsure:
Klaas van Aarsen said:
Btw, don't forget to keep track of the starting and ending vertices in G.

What do you mean? :unsure:

topsquark said:
I don't know how to apply the programming that well anymore but what if there is a path that goes 1, 4, 1, 1, .. that is the actual lowest cost? Your algorithm wouldn't find that, would it? Your path finds the lowest cost by adding the lowest cost at each step, not necessarily the lowest path on the board.

What do you mean? Do you mean that we consider the best solution in each step and not the best solution in total? :unsure:

mathmari said:
What do you mean? Do you mean that we consider the best solution in each step and not the best solution in total? :unsure:
Exactly.

(I got this new scanner/printer because my old one was too fussy. I still can't scan to a file! Anyway.)

Say we have a route counter-clockwise around the left hand lower corner that goes 1, 4, 1, 1, 1, 1, 1, 2, 3, 2, 1. This has a lower cost than the route given in the original problem. The given algorithm wouldn't find it.

-Dan

mathmari said:
I haven't really understood how it follows that the graph has to be directed. Could you explain that further to me?

Consider the board
$$\to\begin{array}{|c|c|c|}\hline 1 & 2 & 3 \\ \hline\end{array}\to$$

The corresponding graph could be:

right?
Also note that it has special nodes for start and finish that we need for Dijkstra's algorithm.

Ahh sowe have to consider some restrictions if the point is on the edges, right?
Yes. We should for instance only add the edge from $(i,j)$ to $(i-1,j)$ if $i>0$.

topsquark said:
Exactly.

(I got this new scanner/printer because my old one was too fussy. I still can't scan to a file! Anyway.)

Say we have a route counter-clockwise around the left hand lower corner that goes 1, 4, 1, 1, 1, 1, 1, 2, 3, 2, 1. This has a lower cost than the route given in the original problem. The given algorithm wouldn't find it.

-Dan
Note that the algorithm as given is incomplete.
Dijkstra's shortest path algorithm still needs to be added to it.
That algorithm will find the shortest path.

Klaas van Aarsen said:
Consider the board
$$\to\begin{array}{|c|c|c|}\hline 1 & 2 & 3 \\ \hline\end{array}\to$$

The corresponding graph could be:
View attachment 10853
right?
Also note that it has special nodes for start and finish that we need for Dijkstra's algorithm.

Do you mean that if we has an undirected graph we could go back to "start" ? :unsure:
Klaas van Aarsen said:
Yes. We should for instance only add the edge from $(i,j)$ to $(i-1,j)$ if $i>0$.

So do we have the following?

Code:
   Algorithm Minimum_Cost_Path
Input: Numbers M, N, Set S of number of each square (i,j) on board
Output: Minimum Cost Path from (0,0) to (M-1, N-1)
G <- new empty graph
for i <- 0 to M-1 do
for j <- 0 to N-1 do
for i <- 0 to M-1 do
for j <- 0 to N-1 do
if i>0 then
G.AddEdge( (i,j), (i-1,j), S( i-1,j ) )
if j>0 then
G.AddEdge( (i,j), (i,j-1), S( i,j-1 ) )
if j<N-1 then
G.AddEdge( (i,j), (i,j+1), S( i,j+1 ) )
if i<M-1 then
G.AddEdge( (i,j), (i+1,j), S( i+1,j ) )

Then do we just call the algorithm "Dijkstra" ? Or do we have to do also something else? :unsure:

mathmari said:
Do you mean that if we has an undirected graph we could go back to "start" ?

No. (Shake)
The weights as given in the table are for the nodes themselves, and counted when we pass through them.
But for Dijkstra's algorithm we need a graph that assigns weights to the edges instead of the nodes.
In my suggested graph we've solved that problem by assigning the weight of the node we enter to an edge.
It does mean that the reverse edge has a different weight.
And it also means we have to introduce an artificial start node so we can introduce an edge with the weight of the first node.

So do we have the following?

Then do we just call the algorithm "Dijkstra" ? Or do we have to do also something else?
Yes.
And indeed, the only left is to call Dijkstra's algorithm with the graph, the source, and the target. (Nod)

Strictly speaking, we should strip an artificial start node again though (assuming we added one).
Or alternatively, we could choose not to add a start node at all, but instead add the weight of the first node to the result afterwards.

Last edited:
Klaas van Aarsen said:
Strictly speaking, we should strip an artificial start node again though (assuming we added one).
Or alternatively, we could choose not to add a start node at all, but instead add the weight of the first node to the result afterwards.

For the first option:

Code:
   Algorithm Minimum_Cost_Path
Input: Numbers M, N, Set S of number of each square (i,j) on board
Output: Minimum Cost Path from (0,0) to (M-1, N-1)
G <- new empty graph
G.AddVertex(s) // Do we add in that way the artificial starting node?
for i <- 0 to M-1 do
for j <- 0 to N-1 do
G.AddEdge( s, (0,0), 1 ) // Do we add in that way the weight of that artificial starting node?
for i <- 0 to M-1 do
for j <- 0 to N-1 do
if i>0 then
G.AddEdge( (i,j), (i-1,j), S( i-1,j ) )
if j>0 then
G.AddEdge( (i,j), (i,j-1), S( i,j-1 ) )
if j<N-1 then
G.AddEdge( (i,j), (i,j+1), S( i,j+1 ) )
if i<M-1 then
G.AddEdge( (i,j), (i+1,j), S( i+1,j ) )
Dijkstra(G, s) // We give here the artificial starting node as input, or not?
:unsure:

That would work yes.
However, Dijkstra(G, s) does not return a minimum cost path from s to (M-1, N-1).
Instead it returns an array of distances together with an array of "prev" nodes, as explained here on wiki.
Immediately after the algorithm, it also shows what to do if we are only interested in the shortest path to some target node.
That is the path that we want to return from our algorithm, preferably excluding the artificial start node that we added.

So we could do for instance:
Code:
(dist, prev) ← Dijkstra(G, s)

P ← empty sequence
u ← G.vertex( (M-1,N-1) )
while u != s
insert u at the beginning of P
u ← prev[u]
return P
:unsure:

Klaas van Aarsen said:
That would work yes.
However, Dijkstra(G, s) does not return a minimum cost path from s to (M-1, N-1).
Instead it returns an array of distances together with an array of "prev" nodes, as explained here on wiki.
Immediately after the algorithm, it also shows what to do if we are only interested in the shortest path to some target node.
That is the path that we want to return from our algorithm, preferably excluding the artificial start node that we added.

So we could do for instance:
Code:
(dist, prev) ← Dijkstra(G, s)

P ← empty sequence
u ← G.vertex( (M-1,N-1) )
while u != s
insert u at the beginning of P
u ← prev[u]
return P
:unsure:

This is a code to print the path that we get from Dijkstra, right?

So we could use also the following code, right?

Code:
Algorithm print_path(G, s, v, pred)
if s == v then
print(s)
else if pred[v] == -1 then
print(“No path from s to v")
else
print_path(G, s, pred[v], pred)
print(v)
As for the complexity:

From the nested for loops we get $O(MN)$.
From Dijkstra we get $O((|V|+|E|)\log(|V|)$ with $|V|=MN$, right? Is $|E|$ also $MN$ ?
The printing part is again of constant complexity, isn't it?

:unsure:

mathmari said:
This is a code to print the path that we get from Dijkstra, right?

So we could use also the following code, right?

Yes and yes.
However, your code prints the path in reverse order, which does not seem to be consistent with the specification of your algorithm.

As for the complexity:

From the nested for loops we get $O(MN)$.
From Dijkstra we get $O((|V|+|E|)\log(|V|)$ with $|V|=MN$, right? Is $|E|$ also $MN$ ?
The printing part is again of constant complexity, isn't it?
Yes.
Each node has at most 4 edges, so $|E|=O(4MN)$.
The printing part iterates through each of the nodes on the shortest path.
In a worst case scenario that means we have to iterate through $O(MN)$ nodes.

Klaas van Aarsen said:
However, your code prints the path in reverse order, which does not seem to be consistent with the specification of your algorithm.

So to get the correct order with this code, do we add the vectors in an array and print them at the end? :unsure:
Klaas van Aarsen said:
Each node has at most 4 edges, so $|E|=O(4MN)$.
The printing part iterates through each of the nodes on the shortest path.
In a worst case scenario that means we have to iterate through $O(MN)$ nodes.

So is the total complexity as follows?

Let $c$ be the constant complexity of "G.AddVertex" and $d$ the constant complexity of "G.AddEdge".

\begin{align*}T&=c+ \sum_{i=0}^{M-1}\sum_{j=0}^{N-1}c+d+\sum_{i=0}^{M-1}\sum_{j=0}^{N-1}d+T_{\text{Dijkstra}}+T_{\text{print}} \\ & =c+ \sum_{i=0}^{M-1}\sum_{j=0}^{N-1}c+d+\sum_{i=0}^{M-1}\sum_{j=0}^{N-1}d+O((MN+4MN)\log(MN))+O(MN)
\\ &=c+cMN+d+dMN+O((MN)\log(MN))+O(MN)\\ & =O((MN)\log(MN))\end{align*} Is the analysis correct and complete? :unsure:

mathmari said:
So to get the correct order with this code, do we add the vectors in an array and print them at the end?

That would work yes. (Nod)
You did mean nodes instead of vectors didn't you?
So is the total complexity as follows?

Is the analysis correct and complete?
Yep. (Nod)

Klaas van Aarsen said:
That would work yes. (Nod)
You did mean nodes instead of vectors didn't you?

Ah yes!

Do we do that as follows?

Code:
Algorithm print_path(G, s, v, pred)
if s == v then
Add s at the beginning of the set P
else if pred[v] == -1 then
print(“No path from s to v")
else
print_path(G, s, pred[v], pred)
Add s at the beginning of the set P
return P

:unsure:

mathmari said:
Ah yes!

Do we do that as follows?
Code:
Algorithm print_path(G, s, v, pred)
if s == v then
Add s at the beginning of the set P
else if pred[v] == -1 then
print(“No path from s to v")
else
print_path(G, s, pred[v], pred)
Add s at the beginning of the set P
return P
A set has no ordering. Shall we make it a sequence P instead of a set P?

The name print_path is not accurate any more is it? It's generally not printing.

Suppose the shortest path is $s\to n \to t$, then we get pred[t]=n and pred[n]=s.
I believe the sequence $(s, s, s)$ is returned then, isn't it?
That does not look correct. (Shake)

## 1. What is the "Find path to minimum cost from start to finish" problem?

The "Find path to minimum cost from start to finish" problem is a classic optimization problem in computer science. It involves finding the most cost-efficient path from a given starting point to a specified ending point in a graph or network.

## 2. Why is the "Find path to minimum cost from start to finish" problem important?

This problem has a wide range of real-world applications, such as in transportation, logistics, and supply chain management. It allows for efficient resource allocation and can help reduce costs and improve efficiency.

## 3. What are the main approaches for solving the "Find path to minimum cost from start to finish" problem?

The most common approaches for solving this problem include Dijkstra's algorithm, Bellman-Ford algorithm, and A* search algorithm. These algorithms use different strategies to find the optimal path with minimum cost.

## 4. How does Dijkstra's algorithm work for the "Find path to minimum cost from start to finish" problem?

Dijkstra's algorithm is a greedy algorithm that works by maintaining a priority queue of vertices and their tentative costs. It starts from the starting point and explores the network, updating the tentative costs of neighboring vertices as it goes. This process continues until the algorithm reaches the ending point, or all vertices have been explored.

## 5. What are some challenges in solving the "Find path to minimum cost from start to finish" problem?

One major challenge in this problem is dealing with graphs or networks with a large number of vertices and edges, as it can significantly increase the time and resources required to find the optimal path. Additionally, handling negative edge weights and cycles in the graph can also pose challenges for some algorithms.

• Programming and Computer Science
Replies
18
Views
1K
• General Engineering
Replies
7
Views
2K
• Programming and Computer Science
Replies
7
Views
2K
Replies
2
Views
1K
• Math Proof Training and Practice
Replies
23
Views
1K
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• Introductory Physics Homework Help
Replies
1
Views
1K
• Topology and Analysis
Replies
6
Views
1K