find the smallest route

I have a matrix comprising of 10x10 which is equal to distances of places, if i am to find the smallest route given a matrix similar to this only 10 by 10 so symmetrical with zeros diaganally

0  10 20 30
10 0  19 17
20 19 0  32
30 17 32 0

also with a problem like this is it best to graph it with nodes? if so how do i go about doing it.

[Walter Roberson]

Are you given the starting and ending point?

Answer 1

[Cedric]

You can use a Dijkstra or equivalent shortest path algorithm. The are several MATLAB implementations of Dijkstra, e.g. here on FEX.

[Walter Roberson]

Dijkstra is not suitable for traveling salesman problems (the 'tsp' tag)

[Image Analyst]

Oh, I didn't know what that meant. I thought it was an abbreviation for teaspoon. If it is a traveling salesman problem he should have said so more explicitly since everyone assumed it was a route from a starting point "a" to and ending point "b", not a route between every single node there. I added the full tag "traveling salesman problem".

[Cedric]

Thank you, I didn't see the tag!

[Walter Roberson]

A TSP can still have a starting and ending node given, if the salesman is not required to return to the original location. It complicates finding the best route, though. Hmmm... or does it? If one found the shortest Hamiltonian Circuit and then removed the most costly edge, then would that be guaranteed to be the shortest Hamiltonian Path ?

[Image Analyst]

True, but the traveling salesman is required to visit all the nodes, which is not the case if you were to, say, find the path along the brightest ridgeline in that chunk of image in the matrix. But we'll never know what antfanni wants because she seems to have abandoned this discussion.

[Walter Roberson]

You had written "everyone assumed it was a route from a starting point "a" to and ending point "b"", but I had seen the tsp tag before I opened the question and responded on that basis.

[Image Analyst]

Well that was how I interpreted your words "starting and ending point" - I didn't know you were thinking that every other point was going to be visited, but I guess I assumed wrong.

[Cedric]

We'll go on this argument in front of a beer, I take the first round! Well, Walter is in Canada, 500km away from any other MATLAB user, ImageAnalyst is probably still traveling across China, and I am between Chicago and Detroit, so there is some path optimization to do here .. if you are not planing on going everywhere on the planet, I propose Dijkstra! ;-)

[Image Analyst]

Actually tomorrow I leave for Caracas, Venezuela for 10 days where I'll be setting up 3 imaging systems and teaching 2 color courses. Hopefully I won't get involved in any other "adventures" like my prior trips (bombs, poisonings, presidential visits, riots, etc.) Thank goodness not all of the federal government is shutdown because the airports are still operating. But if I see Djikstra there I'll give him your best. I may not be able to contribute as frequently during that time so I'll have to leave it up to Walter who seems to work 24/7.

[Walter Roberson]

I do not currently work nearly 24/7; I do, though, work at irregular hours.

Answer 2

[Image Analyst]

You can use dynamic programming http://en.wikipedia.org/wiki/Dynamic_programming#Checkerboard or A* http://en.wikipedia.org/wiki/A* or, if you have the Image Processing Toolbox, bwdistgeodesic http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/