Shortest path
A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A shortest path is a path between vertices whose total edge cost is minimal among the available paths.
- How it is used
- Uses graph search to navigate between vertices or optimize a complete visit cycle.
- How deep it goes
- Develops BFS path reconstruction and exhaustive TSP permutation search, while deferring weighted shortest-path internals.
- Examples
- Uses Boston-to-Miami navigation and a five-city Vermont tour with Swift graph, permutation, and distance-table implementations.
- What you can do after
- Builds BFS route reconstruction and a brute-force traveling-salesman solver in Swift.
Graph Algorithms for Data Science
Network distance is the minimum number of relationships along a path connecting two nodes, particularly when relationships are unweighted.
- How it is used
- Calculates network proximity for link prediction and supports betweenness and closeness centrality analysis.
- How deep it goes
- Defines unweighted traversal, demonstrates Cypher syntax, and addresses leakage and disconnected graphs without covering weighted-path algorithms.
- Examples
- Uses nodes A and E, a Surya-to-Jim Cypher query, social-network friends, and Marvel-character centrality visualizations.
- What you can do after
- Apply it via Cypher to find paths, measure relationship distance, and construct graph features for link prediction.
Read how Graph Algorithms for Data Science explains shortest path →
Grokking Algorithms, Second Edition
A shortest-path problem asks for a path between locations or nodes that minimizes the number of steps or another path cost.
- How it is used
- Uses breadth-first search to find the fewest-step route between nodes in a graph.
- How deep it goes
- Explains graph modeling, layered search, queue ordering, and avoiding repeated checks, without developing weighted-path methods.
- Examples
- Uses a bridge route, web connections, and a social-network search for a nearby mango seller.
- What you can do after
- Apply it via breadth-first search to identify whether a graph contains a path and find its fewest-step path.
Read how Grokking Algorithms, Second Edition explains shortest path →
Advanced Algorithms and Data Structures
A shortest path is a path between graph vertices having minimum total edge distance or cost.
- How it is used
- Models delivery routing as finding a minimum-distance path between a single source and destination in a graph.
- How deep it goes
- Develops graph modeling, grid simplification, BFS distances, and path reconstruction, while deferring detailed weighted-route algorithms.
- Examples
- Uses delivery maps, regular city grids, directed street graphs, BFS distance labels, and an edge-removal exercise.
- What you can do after
- Apply BFS to compute shortest distances and reconstruct a route in an equal-cost grid graph.
Read how Advanced Algorithms and Data Structures explains shortest path →
Modern C
A shortest path is a path between two graph nodes whose total distance is minimal among the available paths.
Learn Haskell by Example
A shortest path is a path between two graph nodes having minimal total length or cost.
- How it is used
- Uses shortest-path search to solve word-ladder chains between user-provided words.
- How deep it goes
- Defines nodes, edges, paths, directions, and costs, then stops before specifying a search algorithm.
- Examples
- Compares two cat-to-dog word chains and visualizes a selection of ladder words as a graph.
- What you can do after
- Builds a word-ladder graph and identifies a shortest chain between two words.
Related concepts
- breadth-first searchaddressed by · Breadth-first search is a graph or tree traversal algorithm that explores nodes in nondecreasing order of their distance from a starting node.
- Dijkstra's algorithmaddressed by · Dijkstra's algorithm computes shortest paths from a source vertex in a weighted graph with nonnegative edge weights.
- depth-first searchcontrasts with · Depth-first search is a graph or tree traversal algorithm that explores one branch as far as possible before backtracking to explore alternatives.
- betweenness centralitymeasured by · Betweenness centrality is a graph metric that measures how frequently a node lies on shortest paths between other nodes.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.