Re: [algogeeks] Dp solution for this problem?
I knew this could be done using Min Path finding algo. But what about DP for this problem , guys? On Mon, Oct 31, 2011 at 3:49 AM, SAMM somnath.nit...@gmail.com wrote: This can be done using the Dijkstra's algorithm , Start frm the source frm the Destination (In this example from (2 2)) . You need to consider the index of the array as the the vertices and the weigjht as the the value for the movement from the present vertex to it's connecting neighbour .. On 10/31/11, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
thnx all On Mon, Oct 31, 2011 at 10:13 PM, Vandana Bachani vandana@gmail.comwrote: Hi Mohit, Bellman-Ford algorithm is a dynamic programming algorithm but u need it only if dijkstra's SP wont solve the problem... and Dijkstra's algo works only for +ve weights. So if u r sure that there maybe negative weights then you will need to use bellmann ford which is a DP algo. On Mon, Oct 31, 2011 at 7:40 AM, mohit verma mohit89m...@gmail.comwrote: I knew this could be done using Min Path finding algo. But what about DP for this problem , guys? On Mon, Oct 31, 2011 at 3:49 AM, SAMM somnath.nit...@gmail.com wrote: This can be done using the Dijkstra's algorithm , Start frm the source frm the Destination (In this example from (2 2)) . You need to consider the index of the array as the the vertices and the weigjht as the the value for the movement from the present vertex to it's connecting neighbour .. On 10/31/11, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vandana Bachani Graduate Student, MSCE Computer Science Engineering Department Texas AM University, College Station -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
Min Cost Path: http://www.geeksforgeeks.org/archives/14943 On Mon, Oct 31, 2011 at 12:52 AM, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
This can be done using the Dijkstra's algorithm , Start frm the source frm the Destination (In this example from (2 2)) . You need to consider the index of the array as the the vertices and the weigjht as the the value for the movement from the present vertex to it's connecting neighbour .. On 10/31/11, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
How about this one... 5 9 10 1 3 7 4 4 8 2 1 9 Check the immediate neighbors / 8 (or less) neighbors of your given cell.. Here for 5 the neighbors are 9,7,3 for 9 they are 5,3,7,4,10 for 7 they are 5,9,10,4,1,2,8,3 etc For every cell calculate the sum of it an its neighbors, find the minimum and add it to the table, and your path set. keep on doing it till the cell you are adding to your path set is the n,n th cell. On Mon, Oct 31, 2011 at 12:52 AM, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
if all possible diagonal movements are allowed i guess we must check all the possibilities On Mon, Oct 31, 2011 at 12:52 AM, mohit verma mohit89m...@gmail.com wrote: Given a matrix you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally) e.g. 5 9 10 1 3 7 4 4 8 2 1 9 So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - 5+3+2+1=11 I dont think some DP solution exist for this problem.Can it be? -- Mohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dp solution for this problem?
Consider each element of the matrix as a node of a graph. Connect the nodes
to the adjacent nodes (up, down, left, right or diagonal) using directed
edges having weight equal to the weight of the node it is incident on, eg.
any edge coming into (0,0) with have weight 5. Given the starting point to
find the shortest path, create a source node with an edge from that going
to the start node with the weight equal to the value of that node.
Find shortest path distance from the new source node to required
destination node.
If the matrix always has +ve values then dijkstra's shortest path algorithm
(greedy) will also do, else Bellman Ford should be able to help (DP).
G = (V, E), V = {source, (0,0), (0,1), etc.}, |V| = m*n+1, |E| = ((2) or
(3) or (5))*m*n + 1
-Vandana
On Sun, Oct 30, 2011 at 2:22 PM, mohit verma mohit89m...@gmail.com wrote:
Given a matrix you have to find the shortest path from one point to
another within the matrix. The cost of path is all the matrix entries on
the way. You can move in any direction (up, down, left, right, diagonally)
e.g.
5 9 10 1
3 7 4 4
8 2 1 9
So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost -
5+3+2+1=11
I dont think some DP solution exist for this problem.Can it be?
--
Mohit
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Vandana Bachani
Graduate Student, MSCE
Computer Science Engineering Department
Texas AM University, College Station
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
