The Difference Between Dijkstra’s Algorithm and A*

Over the last couple weeks, I’ve had an interest in brushing up my C++ skills. Friday, I came across a programming challenge that looked somewhat interesting and I thought I’d give it a shot.

The object was to find the lowest cost route between 10 cities encoded in a map of integers. Each integer represented the cost to get from that any adjacent location to that spot. This is a classic case of a graph navigation algorithm. Unfortunately, I didn’t have time to test my submission before I had to hand mine in. The deadline was Saturday so I did what I could and turned a solution in before I had to leave Saturday evening.

I ended up with the 3rd best solution for the lowest route and the 2nd best solution for time. I’m not going to discuss Dijkstra’s Algorithm here. You can view the Wikipedia definition or look it up elsewhere if you’re interested in implementing it. I’m simply going to discuss the difference between Dijkstra and A* and show what I could have done with more time to get a top score in the competition.

In Dijkstra’s algorithm you search all the verticies in the graph to determine the lowest cost route between each point. A* is a modification of Dijkstra’s algorithm that uses a heuristic to determine which vertices to search. The heuristic is the estimated cost (or distance) from the node you’re searching to the target node. The lower the heuristic, the more likely you’ll search that node’s edges next instead of some node that is further away. This leads you from the source to the target in a much faster manner. A* allows you to trade off the most accurate result for CPU time.

My route cost was quite a bit higher because I chose a heuristic that was too high. After testing a bit further, I found I could come up with a 2nd place route cost by simply lowering the heuristic a bit. This causes more nodes to be searched, and the algorithm run time to climb, but the result is more accurate. Doing away with the heuristic altogether yields a route cost of 2801, which is the same route cost that the 1st place entry received. The execution time goes up to 36 seconds in that case however. The more accurate Euclidian heuristic (linear distance) yields 2819 and costs 10 seconds.

My 2nd issue was implementation details. I think the algorithm is actually coded correctly but I used data structures that needed constructed and destroyed many times during the algorithm search. I planned on coding the algorithm correctly 1st and then optimizing it but didn’t have time to do the latter. The 1st optimization I’d make is to store node pointers instead of nodes and then only construct a node once during the algorithm’s search cycle. I don’t know if this would have yielded the fastest program or not. Either way, it’ll save a lot of cpu cycles.

Anyway, I accomplished my goal of re-familiarizing myself with lots of STL structures, some iostream details and a few C++ quirks that I hadn’t used or remembered for a while. Perhaps I’ll do better with Challenge 13.