Sign up
Please tick the below box to proceed
I agree (or if I am under 13 my parent or guardian agrees on my behalf) to the terms and conditions of use and that:
- My test statistics may be published on the site leaderboard against my username
- My teacher(s) can review my test scores
- I can receive feedback on my tests from my teacher(s)
Please tick this box to proceed
Already have an account? Sign in
Preview lessons, content and tests
Computer Science & Programming solved. All in one platform.
1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.2. Searching for something specific? See our text overview of all tests. Scroll right for levels, and lists. 3. Student and Teacher User Guides | Schemes of Work | Real Teacher use Videos |
Join 36000+ teachers and students using TTIO.
Dijkstra's Algorithm
One algorithm for finding the shortest path from a starting node to a target node in a weighted graph is Dijkstra’s algorithm. The algorithm basically creates a TREE of shortest paths from the starting vertex, the source, to all other points in the graph.
Dijkstra’s algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected.
Suggested Video
Additional Information
Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors. (see above)
Applications and uses
Dijkstra’s algorithm is heavily used in computer systems that need to calculate shortest paths. This includes satellite navigation systems that display the shortest or fastest route from a starting point to a chosen destination. Routers in networks often employ Dijkstra’s algorithm to find the shortest path when routing packets within networks.