The shortest path

This algorithm has its roots in early networking: routers had to decide where to forward packets to, without having any knowledge of what's beyond. They simply had to make the best decision without having perfect information! Edsger Dijkstra, one of the pioneers of computer science, then came up with a graph-routing algorithm that has been named after him: Dijkstra's algorithm.

The algorithm works iteratively and goes over each node to add up their weights, thereby finding the distance (or cost) of reaching this node. It will then continue at the node with the lowest cost, which makes this algorithm a "greedy" algorithm. This continues until the desired node is reached or there are no more nodes to evaluate.

Algorithms that ...

Get The Complete Rust Programming Reference Guide now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.