Use a path cost matrix of the same size as the given matrix. Set all
locations to a maximum cost value.
Use a queue to store locations which still need to be processed.
Start by setting the cost to the destination equal to the cost of that
location and adding that location to the queue.
Then, while the queue is not empty, process queue items in this way:
Dequeue the tail item containing location P
For each location A adjacent to P
If the path cost to A is more than the path cost of P plus
the cost of location A
Set the path cost to A equal to the path cost to P
plus the location cost of A
Insert location A into the queue
Then the path cost of the source represents the cost to move from the
source to the destination. The path is given by moving from the source
to the adjacent location with the lowest path cost.
Don
On Oct 31, 7:40 am, mohit verma <mohit89m...@gmail.com> wrote:
> 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.
