Dijkstra's algorithm
Dijkstra's algorithm computes shortest paths from a source vertex in a weighted graph with nonnegative edge weights.
Grokking Algorithms, Second Edition
Dijkstra's algorithm is a graph shortest-path algorithm that repeatedly selects the lowest-cost unprocessed node and relaxes its outgoing edges, assuming edge weights are nonnegative.
- How it is used
- Finds the lowest-total-cost path through a weighted graph, rather than the path with the fewest edges.
- How deep it goes
- Works through cost and parent updates, explains the nonnegative-weight restriction, and implements the algorithm in Python.
- Examples
- Uses a travel-time route, a sequence of item trades, and Python hash tables for costs, parents, and graph edges.
- What you can do after
- Build it from scratch in Python to find a lowest-cost path when every edge weight is nonnegative.
Read how Grokking Algorithms, Second Edition explains Dijkstra's algorithm →
Acing the CCNA Exam: Volume 1 Fundamentals and Protocols
Dijkstra's algorithm is a shortest-path graph algorithm for calculating minimum-cost paths from a source node.
- How it is used
- Calculates OSPF routes from the shared link-state database.
- How deep it goes
- Explains topology inputs, cumulative costs, and recalculation effects but does not detail the algorithm's internal iteration steps.
- Examples
- Uses OSPF routers calculating a route to 10.1.1.0/24 from shared link costs.
- What you can do after
- Evaluate how OSPF selects routes and why area design changes SPF resource usage.
Read how Acing the CCNA Exam: Volume 1 Fundamentals and Protocols explains Dijkstra's algorithm →
Optimization Algorithms: AI techniques for design, planning, and control problems
A graph algorithm that computes shortest paths from a source node when all edge weights are nonnegative.
- How it is used
- Deploys shortest-path search for routing between a source and destination in weighted graphs and map networks.
- How deep it goes
- Explains priority-ordered expansion, distance relaxation, predecessors, pseudocode, and graph-data adaptations without formal proof.
- Examples
- Uses a home-to-work problem, an S-C-D-A-B graph walkthrough, Toronto map routing, and OpenStreetMap graph irregularities.
- What you can do after
- Apply it via NetworkX or an adapted implementation to compute optimal weighted routes and compare exploration and memory trade-offs.
Advanced Algorithms and Data Structures
Dijkstra's algorithm computes shortest paths from a source in a graph with nonnegative edge weights by repeatedly selecting the unsettled vertex with minimum tentative distance.
- How it is used
- Finds shortest delivery or navigation routes when edge weights represent actual distances or costs.
- How deep it goes
- Develops weighted-path intuition, pseudocode operations, reconstruction, priority-queue trade-offs, and the nonnegative-weight limitation.
- Examples
- Uses irregular city maps, delivery routes, and competing paths whose edge counts and total weights favor different choices.
- What you can do after
- Build it from scratch using a priority queue, tentative distances, predecessor links, and edge relaxation.
Read how Advanced Algorithms and Data Structures explains Dijkstra's algorithm →
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
Dijkstra's algorithm computes shortest paths from a source vertex to reachable vertices in a weighted graph with nonnegative edge weights.
- How it is used
- Uses weighted graphs to find routes from one source to every other reachable vertex, including navigation and network planning.
- How deep it goes
- Explains the five operating steps and Swift data flow, but does not provide a formal proof or asymptotic analysis.
- Examples
- Works through a city graph from Los Angeles to Boston and reconstructs the route through Riverside, Chicago, and Detroit.
- What you can do after
- Build it from scratch by implementing distance relaxation, predecessor tracking, priority-queue exploration, and path reconstruction in Swift.
Related concepts
- priority queueuses · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
- shortest pathaddresses · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
- single-source shortest pathaddresses · The single-source shortest-path problem is to find minimum-cost paths from one source vertex to every other reachable vertex in a weighted graph.
- greedy algorithmuses · A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.
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.