Dijkstra's(?) Algorithm help

[Jared Russell]

And once you grasp Dijkstra's algorithm, you'll probably want to learn about A*.

[Sparkyshires]

Okay, I think I get it. Just a couple questions:

• 1. How would this correlate into a map of line segments?
• 2. How would you go about putting something else in there for the time it may take to turn?
• 3. And what exactly is the a*?

[hzheng_449]

1) Traditionally Dijkstra's is thought described in terms of a graph with vertices connected edges. The example with the in the previous post has the centers of each grid as vertices and all adjacent grid centers are connected by edges. (Pretend a chessboard was represented as a graph with each square being an edge)

For a map of line segments, each point at the end of a line segment would be the vertex. And the line segment would be the edge. It also follows that the length of the line segment would be the edge weight.

2) You could make a function that adds a "maneuver" cost to each edge, and the algorithm would work fine. (Ie it takes 2 seconds to turn to get to a line and 9 seconds to travel the line, so I just say the overall time it takes to go down a line is 11 seconds.

3) A* is another path-finding algorithm (There is a link in the previous post) with a much lower computational cost than Dijkstra's method. I recommend you first get a solid understanding of Dijkstra's and some basic graph theory before looking too deeply into A*.

[Ty Tremblay]

Originally Posted by Sparkyshires

Okay, I think I get it. Just a couple questions:

• 1. How would this correlate into a map of line segments?
• 2. How would you go about putting something else in there for the time it may take to turn?
• 3. And what exactly is the a*?

1. I used squares because it was easy to generate the examples with ppt that way. Use intersections of your line segments. Since you're following a magnetic line, I'm assuming you can only turn at intersections, so call those intersections your nodes.

2. Dijkstra's Algorithm explanations use the term "distance" because that's the easiest term to understand when beginning to learn path planning. However, it's important to realize that physical distance is often not the only factor when navigating from point to point. A better term to use is "cost" instead of "distance." This would let you factor in time for turning and even things like energy conservation and a risk factor for getting stuck.

3. hzheng_449 hit the nail on the head. If your algorithm is a bike on training wheels, Dijkstra is without training wheels, and A* is a motorcycle. It's best to learn to ride without training wheels before jumping on a motorcycle.

[Sparkyshires]

Interesting, I've been looking into both, dijkstras more so. Thank's ya'll very much!