Identify this algorithm and win a prize

[wossname]

I have recently undertaken a project that solves Minimum Spanning Trees for N number of points.

That also involved coming up with an algorithm that states the route between any two points (after the tree has been built).

I came up with one out of my head, but then I came to wonder if anyone else before me had designed it first. Then I became convinced this was the case, since all the early programmers were dead klever.

I call my version the Horny Salmon, because its a bit like watching a salmon swimming up a waterfall.

Say the user wants to know how to get from A to M (see picture).



The program starts at M and gives it a score of 13 (the total number of points) then it goes to each of the ones M is connected to in turn giving them a score of 12, and then their neighbours are given 11...10...9 etc until A is found (the countdown never reaches zero).

Then all the salmon has to do is look around and follow the highest scoring path, swimming from point to connected point, directly to its destination.

The route for this example would be A-B-C-D-F-I-J-M.

Has this randy little aquatic stud been invented before? And if so, who by and whats it called?

[DavidHooper]

Sounds like the depth first search algorithm to me. have a search on google cus i can't remember the exact details.

also have a look for breadth first search.

[NotLKH]

I do something similar to trace the longest path in a maze generating program I made once.

I heard about it in Scientific American a While back. {10, 20 years?}

[HarryW]

Sounds similar to Kruskal's algorithm to me, but without checking weights. Or maybe I'm thinking of Dijkstra's algorithm, I always get them confused.

There's Prim's algorithm too but I completely forgot how that works.

[wossname]

Cool

Actually, I am using a version of the Kruskal algorithm to generate the actual tree structure. That was another of my inventions (OK, at least I coded myself after seeing a pseudo-code text explaining the Kruskal algorithm!)

I haven't decide on the prize yet, don't hold your breaths for a speedboat or an RV though!