Path Algorithms

In programming it is often necessary to find the shortest path between two points on a graph. Mapping software like Google or Apple maps makes use of shortest path algorithms. They are also used in networks including the internet package routing.

Find the shortest path involves finding the smallest total "cost" of each path.

Note: you are not expected to be able to program the algorithm. However, you should be able to trace the algorithm and work out the path.

Both Path Algorithms are breadth first.

Dijkstra’s shortest path

Edsger Dijkstra in 1956 came up with this breadth first path algorithm to find the shortest route between two Dutch towns. Dijkstra's path algorithm uses a weighting for each path.

One way to implement this would be using an array (but you could use many different data structures).

1. Start each cost as infinity (or a very large value) to show that it hasn't been calculated. A should start at 0. It has no cost as it's the starting point.
2. A visited node is one where all outgoing nodes have been visited. Repeat the following steps until all nodes have been visited:
   1. Choose the node with the lowest running total cost for the path so far and set this as the current node.
   2. For each directly attached nodes, work out the total path so far. Update the table if this is lower than the current value in Distance from the start.
3. Trace the shortest path back from the goal to the start.

Note: this algorithm will not work for negative weight values.

The A* Algorithm

A* is known as a best first algorithm improves upon Dijkstra’s shortest path by using heuristics to estimate distances. This speeds up the process because not every vertex is considered.

What is a heuristic?

A heuristic is a problem-solving strategy not guaranteed to find the most accurate solution, but is designed to find a satisfactory solution in a faster time than the most accurate solution. This is like a best guess or educated guess.

The heuristic is unworkable if it severely over or under estimates the path cost. It needs to be based on something reasonable. This is called an admissible heuristic.

For example in GPS you could use longitude and latitude to calculate a straight line distance. In a video game one could use the X and Y coordinates for each node.

The algorithm to apply to those coordinates could be the Manhattan approach (grid) or Euclidean approach (any angle). The latter will be more accurate but will take more processing power.

Heuristic values are normally calculated as you work through the graph.

A* and Djikstra - What's the difference?

• Dijkstra's algorithm visits all nodes.
• A* is more efficient as it uses heuristic values and continues until all nodes adjacent to the goal node have been visited (the ones with edges that lead to the goal). This might leave some nodes unvisited.

You could say that A* is looking forward by using a heuristic (an educated guess). Where as Djiksta only looks up to the current node.

Uses of the A* algorithm

This algorithm is used in video games to move characters, in network packet routing, social networking and financial modelling.