# Implementation of Dijkstra & A* Pathfinding Algorithms in Go

Follows the implementation of Dijkstra and A* pathfinding algorithms in Go programming language. Obviously.

The best article on the A star algorithm was unexpectedly on Wikipedia. Before reading further, I am assuming you already have some background knowledge on what both Dijkstra and A star pathfinding algorithms do (hint: they find the shortest path), otherwise, make sure to check out both the Wikipedia page and a fine article on the implementation of A star. In essence, Dijkstra by itself is A star algorithm without heuristics, which will become clear pretty soon.

# Implementation of A* and Dijkstra in Go

Again, I am assuming that you are good with the theory. If no, at least go (ahem) and check the pseudocode for the algorithm. The word “algorithm” is in the singular form, as we are going to implement only one function that will do both the work of A star and Dijkstra for us.

Given an undirected graph, with lots of starting and ending vertices, as well as the distance between them. For example, the input`0 2 500` means that there is an edge between the vertex numbers 0 and 2 with a distance of 500 units. We will store them in an `Edge` array.

Also given physical vertex locations within an NxN matrix. We will use this information as our heuristics to guide our A* algorithm. Simply, the heuristic function will return the euclidean distance between vertices in the “physical world”, which will be our estimation.

The`Edge` type has the fields of `to` and `distance` , which we will use to store our edge graph. But first, we initialize the global variables.

`var edgeGraph = make([][]Edge, SIZE)var vertexGraph = make([]int, SIZE)var dist = make([]float64, SIZE)var parent = make([]int, SIZE)var visitCount int`

`edgeGraph[i]` will return the ith edge coming out of the vertex 0. `vertexGraph` will return the physical location of vertex 0. `dist` and `parent` slices should bother you only and only if you are here by chance.

# Finding the Shortest Path with A* and Dijkstra Algorithms

As a quick recall, CTRL (⌘)+ C copies, and the`x` button exits the tab in which you are reading this article. But c’mon.

`findShortestPath` accepts starting and ending vertices, as well as the algorithm of choice (`dijkstra` or `astar`). Of course, you may also write `apple`instead of dijkstra; the algorithm will act in the exact same way.

The `reset` function gives default values to arrays: `dist` gets filled with infinities, and`parent` goes negative.

We then declare our costs and initialize our data structure — priority queue. There is no built-in priority queue implementation in Go, so we will use the simple priority queue library in Go by mtorbin. We then immediately push the start Edge to the queue.

`visitCount` simply keeps track of the visited vertices in order to compare A star to Dijkstra. We `break` the loop whenever we reach the goal node.

Now comes the most important part.

We go through all the outgoing edges of `currentVertex`. You know, we have a thing called f(v), which is equal to g(v) + h(v). We may calculate our gCost, which will be the distance until our current vertex plus the distance from our current vertex to its child node.

`gCost = dist[currentVertex] + edgeGraph[currentVertex][i].distance`

If our gCost is less than the current distance until our child node, we update our `dist[to]` (“to” is the child node, obv).

`dist[to] = gCost`

# The difference between Dijkstra & A* algorithms

If you knew how to implement Dijkstra, then this is the culmination. Otherwise, it’s not. The difference between Dijkstra & A* algorithms is the addition of the heuristic function.

If the algorithm is defined as `astar`we apply our heuristic function, otherwise, hCost remains 0 (in Go, zero is the default value for variables while declaration):

`if algorithm == "astar" { hCost = heuristic(to, finish) }fCost = gCost + hCost`

fCost becomes gCost and hence turns into our usual Dijkstra in case our algorithm is specified as “apple”. The heuristic function simply calculates the euclidean distance between the child and goal nodes. Then we simply push the edge to the queue and update our parent array in order to be able to restore our path in the future.

The full code with the heuristic function, path building, and working test cases you will find in the Github repository below. Pull requests if you find a bug or some other insect.

If the reading was useful you might want to try one of the following:

See the list of my articles and their brief overview