I'm sure this has been done to death but I couldn't find anything specific. I have a node structure that is basically a linked list. Nodes hold a list of linked nodes like a tree, except any node can link to any other node (as opposed to a strict hierarchy). That means there can be multiple paths from one node to another given node, kind of like a flow chart. Each node also has a "resistance." You can think of it as a cost to travel through that node. I want the best algorithm that returns the path of least resistance between two given nodes. What's the appropriate solution here?

Yes, A*.

Yeah A* is fine for weighted nodes, another algorithm is Dijkstra's path finding algorithm:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Ah, yes, I think Dijkstra's will do it. The issue I was having with A* is coming up with a meaningful value for H in the this situation, but the other one doesn't need it. Thanks!

Quote: Original post by Pete Michaud
I have a node structure that is basically a linked list. Nodes hold a list of linked nodes like a tree, except any node can link to any other node (as opposed to a strict hierarchy).

That means there can be multiple paths from one node to another given node, kind of like a flow chart.

This is a graph.

Quote: Each node also has a "resistance." You can think of it as a cost to travel through that node.

This is a weighted graph. (See the above link.)

Quote: I want the best algorithm that returns the path of least resistance between two given nodes.

One of the various graph traversal algorithms.

:)

If your nodes correspond to physical locations in space or in a plane, a good h() for A* is to simply take the straight-line distance between the two nodes.