- Dijkstra’s shortest path algorithm (1956) is a method for finding the shortest path from one node to all the connected remaining nodes
- This differs from A*, which focuses on getting from a specific node to another node through heuristic methods for optimisation - they work in a similar way
- When the number of nodes approaches a high number, this work can be intensive but the algorithm is optimised for speed
Applications
- Digital mapping in Google Maps
- Social networking applications
- To suggest friends based on their distance to you (from network interactions, physical, etc)
- Telephone network
- IP routing to find shortest path
- Robotic pathing
- Drones, etc. can automate paths for package delivery, return to home function, etc.
- Agenda-based application
- Skyscanner, etc. gives shortest path recommendations to fly from points a to b, etc. using time and distance metrics
How to
Determining the Path
- Start from the goal node, in this case G
- Push the previous node to the start of a stack
- Repeat step 2 until start node is reached
- Output the stack by popping until empty
Stack: G F E B A
Output: A B E F G