June 2020
Intermediate to advanced
382 pages
11h 39m
English
Content preview from 40 Algorithms Every Programmer Should Know
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
Understanding the shortest path
A path is a sequence of nodes between a start node and an end node, where no node appears twice on the path. A path represents a route between the chosen start and end vertex. It will be set of vertices, p, connecting the start vertex with the end vertex. No vertex is repeated in p.
The length of a path is calculated by counting the constituent edges. Out of all the options, the path with the smallest length is called the shortest path. Calculation of the shortest path is used extensively in graph theory algorithms but is not always straightforward to calculate. There are different algorithms that can be used to find the shortest path between a start node and an end node. One of the most popular algorithms ...