Dijkstra’s algorithm for weighted shortest paths
Dijkstra computes shortest paths from one start vertex in weighted graphs when every edge weight is nonnegative.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
w and δ are additive path costs; V vertices and E edges; with adjacency lists and a binary priority queue, O((|V|+|E|) log |V|).
Variables & units
| Symbol | Meaning | Unit |
|---|---|---|
| Finite directed or undirected graph | nodes and edges | |
| Nonnegative weight of edge (u,v) | cost per edge | |
| Start and destination vertices | nodes | |
| Minimum sum of edge weights along a path from s to v | path cost | |
| Current best-known upper bound on δ(s,v) | path cost |
LaTeX
\delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e),\quad d(v)\gets\min(d(v),d(u)+w(u,v))
Original schematic by Quanta
Free with a Quanta account. Your download stays ready after registration.
Derivation & background
Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Because edge weights are nonnegative, that distance is final when selected. Negative edges invalidate this reasoning, so Dijkstra is unsuitable for them. With adjacency lists and a binary-heap priority queue, the running time is O((|V|+|E|) log |V|); other queue implementations change the bound.
Exam blueprint
Validity range
Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Because edge weights are nonnegative, that distance is final when selected. Negative edges invalidate this reasoning, so Dijkstra is unsuitable for them. With adjacency lists and a binary-heap priority queue, the running time is O((|V|+|E|) log |V|); other queue implementations change the bound.
Derivation steps
Dijkstra keeps the best known distances and improves them through edge relaxation.
- 1Set d(s)=0 and all other distances to ∞.
- 2Choose the unsettled vertex with the smallest tentative distance.
- 3Relax its outgoing edges; with nonnegative weights, its distance is then final.
Rearrangements
Edge relaxation
Update d(v) only when the route through u is shorter; Dijkstra requires nonnegative edge weights.
Task variant
Directed weighted graph edges: s→a(2), s→b(5), a→b(1), a→t(6), b→t(2). Run Dijkstra from s to t.
After s: d(a)=2, d(b)=5.
Through a, d(b) falls to 3.
Through b, d(t)=5.
The path s→a→b→t costs 2+1+2=5; the alternatives cost 8 and 7.
Common mistakes
Treating the first discovered route to a vertex as final.
Finalize a vertex only when removing its smallest tentative value; this requires nonnegative edges.
Exam context
- Compute shortest paths for distances, routing costs, and nonnegative weights in networks.
Formula cluster
Graphs and algorithms
Dijkstra computes shortest paths from one start vertex in weighted graphs when every edge weight is nonnegative.
Worked example
Edges: s→a with weight 2, s→b with 5, a→b with 1, a→t with 6, and b→t with 2. After s, a has value 2 and b initially 5. Relaxing through a lowers b to 3; relaxing through b lowers t to 5. The shortest path s→a→b→t costs 2+1+2=5. Check: s→a→t costs 8, and s→b→t costs 7.
Applications
Compute shortest paths for distances, routing costs, and nonnegative weights in networks.
How do you calculate with Dijkstra’s algorithm for weighted shortest paths?
Here is how to work through a typical Dijkstra’s algorithm for weighted shortest paths (Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v))) task step by step:
- 1
Task
Directed weighted graph edges: s→a(2), s→b(5), a→b(1), a→t(6), b→t(2). Run Dijkstra from s to t.
Solution path
After s: d(a)=2, d(b)=5.
Through a, d(b) falls to 3.
Through b, d(t)=5.
The path s→a→b→t costs 2+1+2=5; the alternatives cost 8 and 7.
Frequently asked questions about Dijkstra’s algorithm for weighted shortest paths
What does Dijkstra’s algorithm for weighted shortest paths describe?+
The relation \delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e),\quad d(v)\gets\min(d(v),d(u)+w(u,v)) describes Dijkstra computes shortest paths from one start vertex in weighted graphs when every edge weight is nonnegative. In the example Edges: s→a with weight 2, s→b with 5, a→b with 1, a→t with 6, and b→t with 2. It applies under the assumptions stated in the background. Validity limit: Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Source: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
How should I work through a calculation?+
First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example Edges: s→a with weight 2, s→b with 5, a→b with 1, a→t with 6, and b→t with 2. After s, a has value 2 and b initially 5. Relaxing through a lowers b to 3; relaxing through b lowers t to 5. The shortest path s→a→b→t costs 2+1+2=5. Check: s→a→t costs 8, and s→b→t costs 7. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Source: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Which assumption must I keep in mind?+
The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Source: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Which units and quantities are involved?+
The stated units are: w and δ are additive path costs; V vertices and E edges; with adjacency lists and a binary priority queue, O((|V|+|E|) log |V|).. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Source: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
When is comparison with graphsuche-bfs-dfs-kuerzeste-wege and big-o-notation useful?+
Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: Initialize d(s)=0 and all other distances to infinity. For each edge (u,v), relaxation checks whether d(u)+w(u,v) improves d(v). A min-priority queue selects the unsettled vertex with the smallest tentative value. Source: MIT OpenCourseWare 6.006, Lecture 13: Dijkstra’s Algorithm.
Quanta exam set
Curated exam set for "Dijkstra’s algorithm for weighted shortest paths":
Question (front)
Which formula describes Dijkstra’s algorithm for weighted shortest paths?
Answer in your set
Question (front)
How do you rearrange Dijkstra’s algorithm for weighted shortest paths for Edge relaxation?
Answer in your set
Question (front)
Which common mistake happens with Dijkstra’s algorithm for weighted shortest paths?
Answer in your set
+ 8 more cards: units, variables, derivation, example, exam task
The formula set contains 11 cards. After importing, review them and start practicing; your ratings determine later review intervals.
Subject references and further reading
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Related formulas
More formulas: Algorithms, number representation and cryptography
Retain Dijkstra’s algorithm for weighted shortest paths for exams
Create a curated FSRS exam set for Kürzester Pfad: min Σw(e); Relaxation: d(v) ← min(d(v), d(u)+w(u,v)): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential