[henry]

This is the question
But the question have something worry
I don't understand the diagram given
how the line go?
This is the Question....
Who have solve this question before or other
can you explain it in more detail
thank you

Attached File(s)

•  OOP__static_.doc (32K)
  Number of downloads: 126

[born2c0de]

The Question is rather simple.
Create a matrix class and find out the shortest path (shortest sum of the weights) from the (1,1) to (last row,last column)
Allow the User to input data for the matrix first and the calculate the shortest path.

This is a good problem so I wont break the solution to you.
I'll give you a hint though.
For example(using the illustrations from the DOC File): In a 5x5 Matrix, no matter which direction you go...you will always take 4 steps downwards and 5 steps to the right.
A Diagonal Step for this example can be represented as 1 step to the right + 1 step downwards.

All the Best.
If you have any problems while coding...You can ask freely.

[henry]

I still not get it
Can you explain how the road is going on at the diagram?
How it is done?
In detail please
Thank you

[Amadeus]

Henry, I hate to ask, but have you gone through the assignment? Is there a particular concept which you do not understand? Is it matrices in general that you would like some help with, or the concept of determining the least weight?

The best course of action may be to populate a matrix with the values given in the file, and then take a few sample traversals to add up the values. You can then experiment with checking all the values that are eleigible from the current value from which you sit...then move onto taking end values into consideration, etc...

Remeber that the matrix wraps (last row can move up into the first row), and that you can move up a row as well as down a row (born2code may have given the impression that moves must always be down and to the right...you can go up as well, but always to the right).

[henry]

any hint
What to use?
Give me a bit only..
Thank
Smile........
I don't want answer but hint ok

[born2c0de]

Amadeus, on 24 Jan, 2006 - 09:57 AM, said:

(born2code may have given the impression that moves must always be down and to the right)

Oops....Thanks for pointing that out Amadeus.
I must have missed it.

[1lacca]

First of all, the assignment has a bug: it starts with specifying a matrix of size NxN and then it talks about sizes of 5x6 and so on

Anyway, you could go along and implementDijkstra's algorythm if no negative values shall be present in the matrix- as this is the fastest way to solve this problem.
However note that it takes a graph given by its adjacency mtrix, and that is different from the matrix you are given! So you must convert it first. If the given matriy is NxM the converted will be (N*M)x(N*M) - quite large, but sparse, so you might look for an edge-list implementation, but I'm not sure if it worth the effort. Another hint: this way you should have start hte algorythm as many times as the number of rows, as the path can start anywhere in the first column, but if you add a new edge to the graph that is connected with all of the cells of the first column, you can finish with one run ( although the converted matrix will be (N*M+1)x(N*M+1).
Conversion should be easy, each cell in the old matrix gives value to 3 cells in the converted one.

[1lacca]

And yes, I have given you a link on purpose written in Java, so that it can be used as pseudo code, but it doesn't destroy the challenge