2.3.5 path finding algorithms

dijkstras algorithm

• finds the shortest path between two nodes in a weighted graph

• breadth first search

• doesn’t work for edges with a negative weight value

how does dijkstras algorithm work

1. set the initial distance from the start values for all noes

2. for each node in the graph

   1. find the node with the shortest distance from the start which has not yet been visited

   2. for each connected node that has not been visited

      1. calculate the distance from the start

      2. if the distance from the start is lower than the recorded distance, set the shortest distance and set the previous node to current node

3. mark the node as visited

what is A* algorithm

• a pathfinding algorithm that finds the shortest path between two nodes on a weighted graph using heuristics

• preforms better than dijkstas’s algorithm as it is a best first search meaning not every vertex is considered

A* algorithm features

• has two cost functions:

  • the actual cost between two nodes, the same cost as is measured in Dijkstra’s algorithm

  • an approximate cost from node x to the final node.

• this is a heuristic, and aims to make the shortest path finding process more efficient

• the approximate cost might be an estimate of the length between x and the final node, calculated using trigonometry

• when calculating the distance between two nodes using the A* algorithm, the approximate cost is added onto the actual cost

• this is used to determine which node is visited next

• this is meant to reduce the total time taken to find the shortest path

heuristic in A*

estimated cost from the current node to the goal, used to help guide the search more efficiently

uses of A* algorithm

• network packet routing

• financial modelling for trading assets and goods

• solving puzzles like word ladders

A* algorithm example

directed vs undirected graph

directed - arcs/edges can only go in 1 direction

undirected - arcs/edges can go in both directions