Week 18 - Pathfinding Algorithms Flashcards
Path between nodes
A sequence of non-repeating nodes between 2 nodes.
Shortest path between nodes.
A sequence of non-repeating nodes between 2 nodes, that has the smallest total edge weight.
Shortest path problems
Shortest distance to source: find the smallest distance (sum of edge weights) from all nodes to the source node.
Shortest path to source: find the shortest path (least nodes traversed) from all nodes to the source node.
Pathfinding: find the shortest path between 2 nodes.
BFS traversal
BFS traversal finds the shortest path from the source to any node for an unweighted graph.
However if a directed graph is not strongly connected, it may not visit all nodes depending on the source node.
BFS works on undirected and directed graphs.
Traversals on weighted graphs
You cannot use BFS on a weighted graph. Instead need to use an algorithm such as Dijkstra or A*.
Dijkstra’s algorithm
Can be used shortest distances from source, shortest paths from source and pathfinding from source.
It only works if all edges are non-negative.
Dijkstra’s to find shortest distances
2 arrays: visited[] and distanceToSource[]
1. Start at source and set all nodes in visited to unvisited except the source. Set all distanceToSource values to infinity except for the source which is 0.
2. Visit unvisited node v with the smallest distance to source. Then for all neighbours of v, if the path going through v is shorter than the existing distanceToSource for that node, update the distanceToSource. Mark node v as visited.
3. Repeat step 3 until all nodes have been visited.
4. Return distanceToSource.
Shortest distance can be found by going to the lowest value in distanceToSource
Dijkstra’s to find shortest path
3 arrays: visited[], previousNode[] and distanceToSource[]
1. Start at source and set all nodes in visited to unvisited except the source. Set all distanceToSource values to infinity except for the source which is 0. Set all previousNodes entries to null.
2. Visit unvisited node v with the smallest distance to source. Then for all neighbours of v, if the path going through v is shorter than the existing distanceToSource for that node, update the distanceToSource and set previousNode[neighbour] to v. Mark node v as visited.
3. Repeat step 3 until all nodes have been visited.
4. Return distance to source and previousNode.
Shortest path can be found by backtracking through previousNode, starting at the node with the lowest distanceToSource. For each value in previousNode, go to the corresponding node’s value.
Pathfinding via Dijkstra’s algorithm
Used to find shortest path between 2 nodes.
Same as shortest path but when visiting a new node, check if it is the target node.
If it is, return distanceToSource and previousNode, if not, continue to next node.
Complexity of dijkstra’s algorithm
Worst case time complexity: O(n^2)
Dijkstra’s algorithm can be modified to be more efficient and get worst case of O(m+nlogn) where m is number of edges.
A* search algorithm
A pathfinding algorithm to find the shortest path between 2 specified nodes that can be used when you have heuristic information on the distance from some nodes to the source.
Uses heuristic prediction on the distance from current node to specified target to improve the efficiency of the algorithm by guiding it to the target.
If d(v) is distance from source to v and h(v) is heuristic distance from v to target then d(v)+h(v) for nodes is compared to decide which node to visit next.
Bellman-Ford algorithm
A pathfinding algorithm that finds the shortest path from a source node to all other nodes in a graph. It is useful as it can be used even if edge weights are negative.
Bellman-Ford works similarly to Dijkstra’s in that it sets distanceToSource of all nodes except the source to infinity and then changes these values as it moves through the graph. However Bellman-Ford does not use a priority queue and instead iterates through the entire graph n-1 times where v is the number of nodes.
It is less efficient than Dijkstra’s but works in the case of negative edge weights.
Has worst case time complexity of O(n*m) where n is number of nodes and m is number of edges.
