Bryn Humberstone · YouTube · 4:21
This video demonstrates the first few steps of Dijkstra's algorithm on a weighted network to find the shortest path from 'home' to 'university'. It covers initializing the start vertex, iteratively updating neighbor distances, selecting the minimum uncircled vertex, and resolving multiple distance values at a single vertex by keeping only the minimum. This 120-second clip shows the later stages of a Dijkstra shortest-path worked example on a weighted graph from "home" to "university". Starting with several vertices already settled, the presenter explains why the target label 7 cannot be accepted immediately: the smallest uncircled vertex must still be processed. Vertex E with label 4 is settled first, producing a candidate 9 at university that is crossed out. Vertex B with label 6 is settled next, producing a candidate 8 that is also crossed out. Only then is 7 at university circled as the final shortest distance. The clip ends by following predecessor arrows backward to reconstruct the shortest path as home → → university. This video segment demonstrates the final phase of solving a shortest path problem on a weighted graph, likely using Dijkstra's algorithm. It shows how to backtrack from the destination node ('university') to the source node ('home') to identify the exact sequence of vertices in the optimal path. The presenter highlights the path edges in yellow and writes out the sequence: home - A - D - university. Finally, the total minimum distance is calculated by summing the weights of these edges, resulting in a value of 7.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The video introduces Dijkstra's algorithm as a systematic method for finding the shortest path between two vertices in a network.
A specific problem is presented: finding the shortest path from the 'home' vertex to the 'university' vertex on a weighted graph.
The algorithm begins by initializing the starting vertex 'home' with a distance of 0 and marking it as visited by drawing a circle around it.
Next, the algorithm examines the neighbors of the current circled vertex ('home') that have not yet been visited.
The distances to these neighbors are calculated by adding the edge weight to the current vertex's distance: vertex A gets a distance of 2, and vertex C gets a distance of 3.
The algorithm then identifies the smallest distance among all uncircled vertices, which is 2 at vertex A.
Vertex A is circled to mark it as visited, and an arrow is drawn from 'home' to A to record the path taken.
The process repeats for the newly circled vertex A, updating its unvisited neighbors.
The distance to B is calculated as .
The distance to D is calculated as .
An alternative distance to C is calculated as .
Since vertex C now has two distance values (3 and 4), the algorithm applies a rule to keep only the minimum.
The larger value, 4, is crossed out, leaving 3 as the valid distance for C.
The algorithm scans the remaining uncircled vertices (, , ) and selects the smallest distance, which is 3 at vertex C.
Vertex C is circled, and an arrow is drawn from 'home' to C.
Updating neighbors of C, the path to A is ignored because A is already visited.
The distance to E is calculated as .
With uncircled vertices , , and , the algorithm encounters a tie for the minimum distance.
The presenter chooses vertex D arbitrarily to proceed.
Vertex D is circled, and an arrow is drawn from A to D, continuing the path reconstruction.
The clip opens on a weighted graph with vertices labeled home, A, B, C, D, E, and university. Several distances are already settled: home has 0, A has 2, C has 3, and D has 4. The narrator continues from an already selected vertex and computes new candidates: from A to B gives , and the visible candidate at university is 7. The spoken arithmetic "four plus three is seven" matches the route through D, since D already has label 4 and the edge D–university has weight 3.
The key method point is stated explicitly: the presenter does not circle 7 at university yet because there are still other uncircled vertices to consider. The next vertex chosen is the smallest uncircled label, which is 4 at E. This demonstrates the core rule of the algorithm: settle the smallest tentative distance first, even if the destination already has a candidate value.
To justify that rule, the video highlights the region involving E and university and gives a hypothetical comparison. If the edge from E to university had weight 1 or 2, then the path through E would produce a shorter total than 7. That counterfactual explains why a target label cannot be accepted while a smaller unsettled vertex remains.
The actual edge weight from E to university is 5, so the update from E gives . The number 9 is written at university and then crossed out because . This is a concrete example of label comparison: a newly discovered route is kept only if it improves the current best distance.
After E is handled, the smallest remaining uncircled label is 6 at B, so B is selected next. The presenter draws the predecessor arrow from A to B, reinforcing that each settled label should remember which earlier vertex produced it. The distance from home to B is therefore 6.
From B, the only relevant new update is to university: . The candidate 8 is written at university and then crossed out because . At this stage, every smaller uncircled candidate has been processed, so the old label 7 at university is now the smallest remaining uncircled value.
The presenter circles 7 at university and states the conclusion of the computation: the shortest distance from home to university is 7. This is the final numerical answer of the worked example.
The last step recovers the actual route, not just the distance. By following predecessor arrows backward from university, the path is traced as university ← D ← A ← home. Reversing that chain gives the shortest path home → → university. The yellow highlighting makes the backward reconstruction visually explicit.
To find the actual shortest path after computing the distances, it is smart to work backwards from the destination. Starting at 'university', we trace back along the highlighted edges to see that it came from 'D', which came from 'A', which originated from 'home'.
Depending on the specific requirements of the problem, you must also report the total cost. By summing the weights of the edges along this path (), we determine that the minimum distance is 7.
A systematic method used to find the shortest path between two vertices in a weighted network. It works by iteratively selecting the unvisited vertex with the smallest known distance, updating its neighbors, and marking it as visited.
Begin the algorithm by assigning a distance of 0 to the starting vertex and marking it as visited (e.g., by circling it). All other vertices are typically considered to have an infinite initial distance until updated.
For the current visited vertex, calculate the tentative distance to each unvisited neighbor by adding the edge weight to the current vertex's distance. If this new distance is smaller than any previously recorded distance for that neighbor, update it.
After updating neighbors, identify the unvisited vertex with the smallest recorded distance. Mark this vertex as visited and draw an arrow from its predecessor to reconstruct the shortest path later.
If a vertex receives multiple distance calculations from different paths, only the smallest value represents the true shortest distance found so far. Larger values must be discarded (crossed out) to avoid errors in subsequent steps.
This card captures the main procedural lesson of the clip. Even though university already shows candidate distance 7, the presenter refuses to circle it immediately because another uncircled vertex, E with label 4, is still smaller. The algorithm must settle the smallest uncircled vertex first before the destination label can be trusted as final.
In the worked example, each number at a vertex is the current best known distance from home to that vertex. A blue circle marks that the distance has been accepted as final for that vertex during this run of the algorithm. Uncircled numbers remain tentative candidates that can still be improved or compared.
When a vertex is selected or updated, the presenter draws an arrow from the vertex that supplied the current best label. For example, records how E got label 4, and records how B got label 6. These arrows are not decorative; they are the data used later to reconstruct the shortest path.
From E, whose settled distance is 4, the edge to university has weight 5, so the new candidate is . Since university already has candidate 7, the value 9 is crossed out. This shows the comparison rule: keep the smaller label and discard the larger one.
After B is settled with distance 6, the edge from B to university has weight 2, producing candidate . Again this is worse than the existing 7, so 8 is crossed out. Only after these checks does 7 become safe to finalize.
Once E and B have been processed and no smaller uncircled candidate remains, the label 7 at university is circled. The clip states the result directly: the shortest distance from home to university is 7.
The final distance is not the whole answer. To find the route, start at university and follow predecessor arrows backward: university came from D, D came from A, and A came from home. Reversing that chain yields the shortest path home → → university.
After an algorithm like Dijkstra's computes the shortest distance to every node, the specific path to the target can be found by starting at the target and repeatedly moving to the predecessor node that yielded the minimum distance, until the source is reached.
The total distance or cost of a path in a weighted graph is the sum of the weights of all edges contained in that path. In this example, the path home -> A -> D -> university has a total weight of .
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
The leftmost vertex of the weighted graph is labeled 'home'.
home
The starting vertex for the shortest path problem.
Vertex in a weighted graph
The rightmost vertex of the weighted graph is labeled 'university'.
university
The target vertex for the shortest path problem.
Vertex in a weighted graph
A vertex in the graph is labeled 'A'.
A
An intermediate vertex in the network.
Vertex in a weighted graph
A vertex in the graph is labeled 'B'.
B
An intermediate vertex in the network.
Vertex in a weighted graph
A vertex in the graph is labeled 'C'.
C
An intermediate vertex in the network.
Vertex in a weighted graph
A vertex in the graph is labeled 'D'.
D
An intermediate vertex in the network.
Vertex in a weighted graph
A vertex in the graph is labeled 'E'.
E
An intermediate vertex in the network.
Vertex in a weighted graph
The leftmost vertex is labeled "home" and carries the circled value 0.
home
source vertex of the shortest-path computation
vertex of the displayed weighted graph
The rightmost vertex is labeled "university" and later receives candidate labels 7, 9, and 8 before the final circled 7.
university
target vertex whose shortest distance from home is being found
vertex of the displayed weighted graph
Vertex A is already circled with label 2 at the start of the clip.
The speaker uses A as the current vertex when computing paths to B and D.
A
intermediate vertex with settled shortest distance 2 from home
vertex of the displayed weighted graph
Vertex B first shows candidate label 6, then is circled with 6.
"we can go up to B here, four plus two is six."
B
intermediate vertex whose settled shortest distance becomes 6
vertex of the displayed weighted graph
Vertex C is already circled with label 3 at the start of the clip.
C
intermediate vertex with settled shortest distance 3 from home
vertex of the displayed weighted graph
In this video we're going to be looking at Dijkstra's algorithm, which is a systematic way to determine the shortest path from one vertex to another vertex within a network.
A systematic method used to find the shortest path between two vertices in a weighted network.
The network must have non-negative edge weights.
To start off with, what we're going to do is next to the vertex home, we're going to put a zero because it is zero distance from home, and we're going to circle that vertex.
A blue '0' is written next to the 'home' vertex, and a blue circle is drawn around it.
Assign a distance of 0 to the starting vertex and mark it as visited (circled).
Applies to the starting vertex of the path.
Now at each stage we're going to look at the circled vertex and work out its neighbors that aren't circled yet. So we can go to A, which is two away, and we can go to C, which is three away.
Blue numbers '2' and '3' are written next to vertices A and C respectively.
For the current circled vertex, calculate the total distance to its unvisited neighbors by adding the edge weight to the current vertex's distance. Write these new distances next to the neighbors.
Only applies to neighbors that are not yet circled.
Now we look for the smallest uncircled number that we've written on our graph. In this case it's two, so we're going to circle that and we're going to draw an arrow indicating where that has come from. It's come from home.
The number '2' at vertex A is circled, and a blue arrow is drawn from 'home' to A.
Identify the smallest distance among all uncircled vertices. Circle this vertex and draw an arrow from its predecessor to record the shortest path.
Applies when there are uncircled vertices with assigned distances.
Whenever we have two or more numbers at a vertex, we're going to cross out any number that isn't equal to the minimum. So in this case we've got three and four at C, so we're going to just cross out that four.
The number '4' at vertex C is crossed out with a blue line.
If a vertex receives multiple distance calculations, keep only the smallest value and cross out the larger ones.
Occurs when a vertex is reachable via multiple paths from different circled vertices.
"Now, we don't just conclude that seven must be the shortest distance because we've still got some other vertices to consider. So the smallest uncircled vertex is this other four down here"
The label 4 at E is circled before the label 7 at university is finalized.
The clip demonstrates that a candidate label at the target is not final until it is the smallest uncircled label remaining. The next chosen vertex is the smallest uncircled one, here E with label 4.
The graph is being processed by the displayed shortest-path method.
Vertices with circled labels are treated as already selected.
Uncircled labels are still candidates.
Numeric labels accumulate at vertices and are compared across the graph.
The speaker interprets labels as distances, e.g. "the distance from home to B is six".
The video never states a formal definition with symbols; this item records the operational meaning visible in the worked example.
In this demonstration, a number written at a vertex represents the current best known distance from home to that vertex. A circled number indicates that this distance has been accepted as final for that vertex in the run of the algorithm.
Applies to the specific whiteboard-style demonstration shown in the clip.
"circle that now and indicate where that has come from"
Arrows are drawn from A to B, from C to E, and from D to university.
"Working backwards from university, we've come from D ... that's come from A ... that's come from home."
Whenever a vertex is selected or updated, the presenter draws an arrow from the vertex that supplied the current best label. These arrows are then followed backward to reconstruct the shortest path.
Used when a new best label is assigned or when a selected vertex needs its predecessor recorded.
"And now finally we've got this seven here is the smallest uncircled vertex"
"that tells us that the shortest distance from home to university is seven."
The label 7 at university is circled as the last selected value.
After all smaller uncircled candidates have been processed, the label 7 at university becomes the smallest uncircled vertex and is circled. The presenter concludes that the shortest distance from home to university is 7.
All relevant vertices with smaller tentative labels have already been processed.
"We can also conclude the path to take. Working backwards from university, we've come from D ... following the arrow backwards from D, that's come from A ... and then following from A, that's come from home."
Yellow highlighting traces university ← D ← A ← home in reverse order.
The spoken sentence after "When you're writing this out, it's" is cut off before completion.
Once the destination label is finalized, the actual route is recovered by starting at university and repeatedly moving to the predecessor indicated by the drawn arrow. In this example the backward chain is university ← D ← A ← home, giving the forward path home → → university.
Predecessor arrows must have been recorded during the label updates.
Speaker explains working from right to left to find the path: 'university has come from D, has come from A, has come from home'.
Yellow highlighted edges show the path from home to university. The speaker writes the sequence 'home - A - D - university' below the graph.
After computing the shortest distances to all nodes (typically using an algorithm like Dijkstra's), the actual shortest path can be found by backtracking from the destination node to the source node. At each step, one identifies the predecessor node that yielded the minimum distance.
The shortest distances and predecessors for all nodes must have been previously computed.
Speaker states: 'you should also indicate what the distance was and the minimum distance was seven'.
The number 7 is written next to the final path sequence.
In many shortest path problems, simply identifying the sequence of nodes is not enough; the total cost or distance of that path must also be calculated and reported. This is the sum of the weights of the edges along the shortest path.
The shortest path has been identified.
"Now, we don't just conclude that seven must be the shortest distance because we've still got some other vertices to consider."
In this worked run of Dijkstra's algorithm, seeing a candidate distance 7 at university does not allow immediate termination while a smaller uncircled candidate remains.
The graph contains multiple uncircled vertices.
At least one uncircled vertex has a label smaller than the target's current label.
For the displayed graph state, if an uncircled vertex has a smaller label than the target, then the target label is not yet final.
"if the edge from E to university had just been one or two, then that would actually give us a shorter path."
This is presented as a hypothetical comparison, not as an alteration actually made to the displayed graph.
If the edge weight from E to university were 1 or 2, then the path through E would produce a shorter route to university than the currently visible label 7.
The settled distance to E is 4.
The edge under consideration connects E to university.
For edge weights w(E, university) ∈ {1, 2}, the resulting candidate distance is less than 7.
"that tells us that the shortest distance from home to university is seven."
The final circled label at university is 7.
For the weighted graph shown in the clip, the shortest distance from home to university is 7.
The displayed edge weights are fixed.
The algorithm is applied as demonstrated on this graph.
For the specific graph instance shown, the minimum path length from home to university equals 7.
"Working backwards from university, we've come from D ... that's come from A ... that's come from home."
Yellow highlight marks the edges home-A, A-D, and D-university.
The shortest route identified by the worked example is home → → university.
The predecessor arrows recorded during the algorithm are correct for the displayed run.
For the specific graph instance shown, the reconstructed minimizing path is home → → university.
So we can go to A, which is two away, and we can go to C, which is three away.
Numbers 2 and 3 appear next to A and C.
Calculate distance to A from home.
Edge weight from home to A is 2.
Calculate distance to C from home.
Edge weight from home to C is 3.
Distances to A and C are updated to 2 and 3 respectively.
So we've got B is a neighbor, two plus four is six. D is a neighbor, two plus two is four. And C is a neighbor, two plus two is four.
Numbers 6, 4, and 4 appear next to B, D, and C.
Calculate distance to B from A.
Edge weight from A to B is 4.
Calculate distance to D from A.
Edge weight from A to D is 2.
Calculate alternative distance to C from A.
Edge weight from A to C is 2.
Distances to B, D, and an alternative to C are calculated.
From this just circled vertex, we could get to A but we've already worked out the shortest distance there is two. So we can get to E though, three plus one is four.
Number 4 appears next to E.
Calculate distance to E from C.
Edge weight from C to E is 1.
Distance to E is updated to 4.
"All right, from that one, we can go up to B here, four plus two is six. We can go to the university, four plus three is seven, and we can't go anywhere else."
Candidate labels 6 at B and 7 at university appear after processing from A.
The opening words are fragmentary, but the arithmetic and resulting labels are clear.
Vertex A is already circled with label 2 at the start of the clip.
Observed diagram state.
From A, the presenter computes a candidate label 6 for B.
Audio arithmetic plus visible edge weight 4 on A-B.
Using the visible edge weight 3 from A to university, the arithmetic gives 5, but the clip instead shows and says 7 from the path through D.
Diagram shows edge A-university with weight 3, while audio says "four plus three is seven" and the written candidate at university is 7.
The displayed candidate 7 at university matches the path through D, whose settled label is 4 and whose edge to university has weight 3.
Visible labels and edge weights on D-university.
Processing from A yields a candidate 6 at B, and the visible candidate 7 at university corresponds to the route through D rather than directly from A.
"the smallest uncircled vertex is this other four down here"
"looking at the E, we've got four there, and that is nine to the university"
E is circled with 4, then 9 is written at university and crossed out against 7.
Among uncircled vertices, E has the smallest label.
Audio explicitly identifies "this other four down here" as the smallest uncircled vertex.
The label 4 at E comes from C with an edge of weight 1.
Visible circled label 3 at C, edge weight 1 on C-E, and arrow .
From E, the presenter computes a candidate 9 for university.
Audio says "that is nine to the university" and the diagram shows 9 written at university.
The new candidate 9 is worse than the existing candidate 7, so 9 is crossed out.
Audio: "we're going to cross out nine because that's not the smallest."
E must be settled before the target because its outgoing edge could have improved the target label; in this graph it produces 9, which is discarded in favor of 7.
"it looks like at B, we've got some sixes here"
"from B, we can get to the university, six plus two is eight"
"we've got a seven and an eight here, so cross out the eight"
B is circled with 6, 8 is written at university and crossed out, then 7 is circled.
The phrase "some sixes here" is audible but the exact reason for the plural is not fully explained in the clip.
After E is handled, the smallest remaining uncircled label is 6 at B, so B is selected.
Audio identifies B as the next smallest uncircled vertex and the diagram circles 6 at B.
The selected label 6 at B is consistent with the earlier update from A.
Visible labels and edge weight 4 on A-B.
From B, the presenter computes a candidate 8 for university.
Audio says "six plus two is eight" and 8 is written at university.
The candidate 8 is worse than the existing candidate 7, so 8 is crossed out.
Audio: "cross out the eight because that is larger than seven."
With no smaller uncircled candidate left, the label 7 at university is circled as final.
Audio: "now finally we've got this seven here is the smallest uncircled vertex" and the diagram circles 7.
Processing B cannot improve the target because it gives 8, so the previously seen 7 becomes the final shortest distance.
"Working backwards from university, we've come from D ... following the arrow backwards from D, that's come from A ... and then following from A, that's come from home."
Yellow highlight appears successively on D-university, A-D, and home-A.
The last spoken sentence is truncated after "When you're writing this out, it's".
Start at the destination and follow its predecessor arrow back to D.
Audio and yellow highlight on edge D-university.
Follow D's predecessor arrow back to A.
Audio and yellow highlight on edge A-D.
Follow A's predecessor arrow back to the source.
Audio and yellow highlight on edge home-A.
Reverse the backward chain to state the path in forward order.
Derived from the observed predecessor sequence.
The predecessor pointers identify the shortest path as home → → university.
Speaker narrates the process of tracing the path backwards and summing the distance.
Visual highlighting of the path and writing of the sequence 'home - A - D - university (7)'.
Start at the destination node 'university'.
Goal is to find the path to 'university'.
Trace backwards along the highlighted yellow edges to find the predecessor node 'D'.
Visual inspection of the graph shows the edge D -> university is part of the shortest path tree.
Continue tracing backwards from 'D' to its predecessor 'A'.
Visual inspection shows the edge A -> D is part of the shortest path tree.
Trace backwards from 'A' to the starting node 'home'.
Visual inspection shows the edge home -> A is part of the shortest path tree.
Write the full path sequence: home - A - D - university.
Combining the traced steps gives the complete shortest path.
Calculate the total distance by summing the weights of the edges along the path (home->A is 2, A->D is 2, D->university is 3).
Definition of path length in a weighted graph.
The shortest path is home - A - D - university, and its minimum distance is 7.
A weighted graph with vertices home, university, A, B, C, D, E.
In this case we want to find the shortest path from home to university.
Find the shortest path from the 'home' vertex to the 'university' vertex in the given weighted network.
Weighted undirected graph with vertices: home, university, A, B, C, D, E.
Edge weights: home-A=2, home-C=3, , , , , B-university=2, , D-university=3, E-university=5.
Determine the sequence of vertices and total weight of the shortest path.
Start the algorithm at the source vertex.
Base case for Dijkstra's algorithm.
Calculate initial distances from the source.
Add edge weights to d(home).
Choose the closest unvisited vertex.
.
Recalculate distances through 'A'.
, , . Keep minimum for C.
Choose the next closest unvisited vertex.
, 6.
Recalculate distances through 'C'.
.
Choose the next closest unvisited vertex. Tie between D and E broken arbitrarily.
4 <= 4, 6.
The algorithm is still running at the end of the clip. The shortest path found so far leads to D with distance 4.
Visual tracking of circled vertices and arrows confirms the path construction.
A weighted graph with vertices home, A, B, C, D, E, university is worked step by step.
The speaker narrates label updates, crossings-out, selection of the smallest uncircled vertex, and final path reconstruction.
The very first words are fragmentary, and the final sentence is cut off after "When you're writing this out, it's".
Find the shortest distance and route from home to university in the displayed weighted graph using the demonstrated version of Dijkstra's algorithm.
Initial visible settled labels: home = 0, , , .
Visible edge weights include home-A = 2, home-C = 3, , , , , A-university = 3, , B-university = 2, D-university = 3, E-university = 5.
E begins with uncircled label 4.
University begins with candidate label 7 before the clip's later updates.
Determine the final shortest distance from home to university.；Determine the corresponding shortest path.
From A, compute a candidate label 6 for B.
Audio: "four plus two is six" with visible labels and edge weight.
A candidate label 7 is already present at university from the route through D.
Visible label 7 and audio "four plus three is seven"; the arithmetic matches D→university rather than A→university.
Do not finish at university yet; choose the smallest uncircled vertex, E with label 4.
Audio explicitly says the smallest uncircled vertex is "this other four down here".
From E, compute a candidate 9 for university.
Audio: "that is nine to the university" and visible edge weight 5 on E-university.
Compare 9 with the existing 7 and cross out 9.
Audio: "we're going to cross out nine because that's not the smallest."
Next choose the smallest uncircled vertex, B with label 6.
Audio identifies B as the next smallest uncircled vertex and the diagram circles 6.
From B, compute a candidate 8 for university.
Audio: "six plus two is eight" and visible edge weight 2 on B-university.
Compare 8 with 7 and cross out 8.
Audio: "cross out the eight because that is larger than seven."
Circle 7 at university as the final shortest distance.
Audio: "that tells us that the shortest distance from home to university is seven."
Follow predecessor arrows backward from university to recover the route.
Audio and yellow backward highlighting from university to D to A to home.
Shortest distance = 7; shortest path = home → → university.
The answer is verified inside the clip by comparing all later candidate labels at university (9 from E and 8 from B) against 7 and by tracing the recorded predecessor arrows backward from university to home.
A weighted graph with nodes home, A, B, C, D, E, university.
Speaker explains how to find the shortest path from home to university.
Given a weighted graph representing locations and travel times, find the shortest path from 'home' to 'university' and its total distance.
A graph with vertices: home, A, B, C, D, E, university.
Edge weights representing distances/times.
Pre-computed shortest distances to each node (indicated by blue circles).
Identify the sequence of nodes forming the shortest path and calculate its total weight.
Observe the highlighted yellow path on the graph.
The visual aid indicates the optimal route.
Trace the path backwards from 'university' to 'home': university <- <- home.
Following the directed edges of the shortest path tree.
Write the forward path: home - A - D - university.
Reversing the backward trace to get the logical order.
Sum the weights of the edges: (home, A)=2, (A, D)=2, (D, university)=3.
Calculation of total path cost.
Path: home - A - D - university; Minimum distance: 7.
The sum of the edge weights matches the final distance value written by the speaker.
Static weighted graph with 7 vertices and 10 edges.
Vertices: home, university, A, B, C, D, E
Edges with numerical weights
Blue annotations (numbers, circles, arrows, cross-outs) are added sequentially over time.
The underlying graph structure and edge weights remain constant.
The visual changes represent the step-by-step execution of Dijkstra's algorithm on the fixed network.
The graph shows circled labels 0 at home, 2 at A, 3 at C, and 4 at D; E has uncircled 4; university has uncircled 7; B has uncircled 6.
weighted graph
vertices home, A, B, C, D, E, university
circled labels 0, 2, 3, 4
uncircled labels 6, 4, 7
blue predecessor arrows
Candidate labels 6 at B and 7 at university are visible from updates associated with A and D.
Edge weights remain fixed.
Already circled labels 0, 2, 3, and 4 do not change.
The clip begins mid-run, after several vertices have already been settled and after candidate labels have been propagated to B and university.
The uncircled 4 at E is circled in blue.
A blue arrow is drawn from C to E.
vertex E
label 4 at E
vertex C
edge C-E
E changes from uncircled to circled.
A predecessor arrow is added.
The label value 4 at E does not change.
Other settled labels remain unchanged.
Because 4 at E is the smallest uncircled label, E is settled before the target label 7 can be accepted.
A red rectangular outline encloses E, the edge E-university, and university.
vertex E
edge E-university
vertex university
red rectangle
The region involving E and university is highlighted in red.
No numerical label is changed by the red box itself.
The edge weight remains 5.
The highlight supports the spoken counterfactual explanation that a smaller edge from E to university could have beaten the current target label 7.
A 9 is written at university below the existing 7.
The 9 is then crossed out.
vertex university
labels 7 and 9
edge E-university
A new candidate label 9 appears at university.
The 9 is crossed out while 7 remains.
The existing label 7 stays visible.
The edge weight E-university remains 5.
The update from E gives , which is worse than the current best 7, so it is discarded.
The label 6 at B is circled.
A blue arrow from A to B is drawn.
vertex B
label 6 at B
vertex A
edge A-B
B changes from uncircled to circled.
A predecessor arrow is added.
The value 6 at B is unchanged.
Previously settled labels remain fixed.
After E is handled, B has the smallest remaining uncircled label and is therefore settled next.
An 8 is written at university near the existing 7.
The 8 is crossed out.
vertex university
labels 7 and 8
edge B-university
A new candidate label 8 appears at university.
The 8 is crossed out while 7 remains.
The label 7 remains the best candidate.
The edge weight B-university remains 2.
The update from B gives , which is larger than 7, so the target label is not improved.
The label 7 at university is circled in blue.
vertex university
label 7
The uncircled 7 at university becomes circled.
No new candidate replaces 7.
All smaller uncircled vertices have already been processed.
The destination label 7 is now accepted as the shortest distance from home to university.
Yellow highlighting appears on D-university, then A-D, then home-A.
The speaker narrates the backward route from university to D to A to home.
edges D-university, A-D, home-A
vertices university, D, A, home
yellow highlight
Edges are highlighted one by one in reverse order from the destination toward the source.
The underlying graph and labels do not change during the highlighting.
The highlighted edges correspond to the recorded predecessor arrows.
The animation visually reconstructs the shortest path by following predecessor pointers backward, yielding home → → university.
Edges home->A, A->D, and D->university are highlighted in thick yellow.
Graph edges
Specific edges are colored yellow to distinguish them from the rest of the graph.
The underlying graph structure remains unchanged.
The yellow highlight visually represents the sequence of edges that constitute the shortest path found by the algorithm.
Handwritten text appears sequentially at the bottom of the screen: 'university', then '- D - university', then '- A - D - university', then 'home - A - D - university', and finally '(7)'.
Text labels
Text is added incrementally to build the final path string.
The graph diagram above remains static.
This animation demonstrates the process of reconstructing the path by tracing backwards from the destination and then writing it out in the correct forward order, concluding with the total distance.
Whenever we have two or more numbers at a vertex, we're going to cross out any number that isn't equal to the minimum.
Students might leave multiple distance values at a single vertex, leading to confusion in later steps.
Only the minimum distance value should be kept; all larger values must be explicitly crossed out.
"Now, we don't just conclude that seven must be the shortest distance because we've still got some other vertices to consider."
"The reason why we couldn't just circle that seven straight away is if the edge from E to university had just been one or two, then that would actually give us a shorter path."
Once a number appears at the destination, one might think it is already the shortest distance and stop immediately.
The clip explicitly shows that 7 at university is not circled right away because a smaller uncircled vertex E with label 4 still has to be processed; only after all smaller candidates are handled can the target label be finalized.
Hypothetical discussion of the edge from E to university being 1 or 2.
Later candidates 9 and 8 are written at university and compared against 7.
One might assume that a single route to the destination determines the answer without checking other unsettled branches.
The worked example checks alternate routes through E and B, producing 9 and 8, and rejects both because they are larger than 7.
Sequential explanation of initialization followed by updating neighbors.
The initialization step must be completed before neighbor updates can begin.
Sequential explanation of updating neighbors followed by selecting the minimum.
Neighbors must be updated with new distances before the algorithm can select the next vertex to visit.
Explanation of crossing out larger numbers immediately after calculating multiple distances to C.
The rule for crossing out larger numbers is applied as a direct consequence of the neighbor update step when multiple paths reach the same vertex.
The speaker first insists on processing the smallest uncircled vertex and only later circles 7 at university.
E and B are settled before university.
The final distance 7 depends on first applying the rule that the smallest uncircled vertex must be processed before the target can be declared finished.
Predecessor arrows are drawn during the run.
The final path is obtained by "following the arrow backwards".
Path reconstruction depends on the earlier recording of predecessor arrows; without those arrows, the backward route could not be recovered.
All algorithm actions are driven by comparing numeric vertex labels.
The speaker repeatedly refers to labels as distances.
The rule for choosing the next vertex presupposes understanding that each numeric label represents a current distance estimate from the source.
The whole clip is a single worked graph example.
The narration applies the selection and update rules concretely.
The worked example instantiates the general method of selecting the smallest uncircled vertex and updating neighboring candidates.
The hypothetical edge weight 1 or 2 from E to university is used to explain why 7 cannot be circled immediately.
The hypothetical shorter route through E contrasts with the mistaken idea that the first target label can be accepted immediately.
Speaker transitions from describing the path to stating the minimum distance.
Once the path is identified via backtracking, the minimum distance is calculated by summing the weights of the edges along that specific path.
Explanation of putting a zero at the start vertex.
Explanation of circling the smallest uncircled number.
Rule for handling two or more numbers at a vertex.
"we don't just conclude that seven must be the shortest distance"
"if the edge from E to university had just been one or two"
Numbers are attached to vertices and compared throughout.
"the distance from home to B is six"
"that is nine to the university"
"six plus two is eight"
"the shortest distance from home to university is seven"
"Working backwards from university, we've come from D ... A ... home."
Yellow highlighting traces the route backward.
"the smallest uncircled vertex is this other four down here"
E is circled before university is finalized.
Explanation of working right to left to find the path.
Statement about indicating the minimum distance.
Covered · Introduction to Dijkstra's algorithm.
Covered · Problem statement: find shortest path from home to university.
Covered · Step 1: Initialize starting vertex.
Covered · Step 2: Update neighbors of the starting vertex.
Covered · Step 3: Select and circle the minimum uncircled vertex (A).
Covered · Step 4: Update neighbors of vertex A.
Covered · Step 5: Cross out the larger distance at vertex C.
Covered · Step 6: Select and circle the minimum uncircled vertex (C).
Covered · Step 7: Update neighbors of vertex C.
Covered · Step 8: Select and circle the minimum uncircled vertex (D).
Covered · Opening graph state and updates from A producing candidate labels at B and university.
Covered · Explanation that 7 is not final yet; E with label 4 is selected as the smallest uncircled vertex.
Covered · Red-box visual emphasis and hypothetical explanation about a shorter edge from E to university.
Covered · Computation of candidate 9 from E and crossing it out against 7.
Covered · Selection of B with label 6 and recording of predecessor arrow .
Covered · Computation of candidate 8 from B and crossing it out against 7.
Covered · Final circling of 7 at university and statement of the shortest distance.
Covered · Backward traversal of predecessor arrows to recover the path home → → university.
Covered · The entire clip covers the final steps of a shortest path problem: backtracking to find the route and summing the weights for the total distance.
Reviewed subject paths
The final shortest distance from home to university is 7. This value is determined after all smaller uncircled candidates (specifically vertices E with label 4 and B with label 6) have been processed.
Conditions: The algorithm has processed all vertices with tentative labels smaller than 7.; The label 7 at university is the smallest remaining uncircled label.; The graph edge weights are fixed as shown in the example.
The algorithm does not finalize the destination label 7 at university immediately because there are still other uncircled vertices with smaller tentative distances that must be processed first. Specifically, vertex E has an uncircled label of 4, which is smaller than 7.
Conditions: The graph is being processed by Dijkstra's algorithm.; Vertices with circled labels are treated as already selected/settled.; Uncircled labels are still tentative candidates.; There exists at least one uncircled vertex with a label smaller than the target's current label.
To update the neighbors, you calculate the total distance from the source to each unvisited neighbor by adding the edge weight to the current circled vertex's distance. You then write these new distances next to the neighbors.
Conditions: There is a current circled (settled) vertex.; The vertex has neighbors that are not yet circled.; Edge weights are known and non-negative.
When a vertex receives multiple distance calculations from different paths, you keep only the smallest value and cross out the larger ones. This ensures that the vertex's label always represents the shortest known distance from the source.
Conditions: A vertex is reachable via multiple paths from different circled vertices.; New distance calculations are performed for an already labeled vertex.
The initialization step involves assigning a distance of 0 to the starting vertex (home) and marking it as visited by drawing a circle around it. All other vertices are initially considered to have an infinite or undefined distance until they are updated by neighbor calculations.
Conditions: The algorithm is starting.; The source vertex is identified as 'home'.
The numeric labels at the vertices represent the current best known distance from the source vertex (home) to that specific vertex. A blue circle around a label indicates that this distance has been accepted as final for that vertex in the current run of the algorithm.
Conditions: The demonstration uses a visual whiteboard-style representation.; The source vertex is 'home'.; The algorithm is Dijkstra's shortest path algorithm.
The rule is to select the uncircled vertex with the smallest tentative distance label. This vertex is then circled to mark it as settled, and a predecessor arrow is drawn from the vertex that supplied this smallest distance.
Conditions: There are uncircled vertices with assigned distance labels.; The algorithm is in the selection phase after updating neighbors.
To reconstruct the shortest path, you follow the predecessor arrows backward from the destination vertex to the source vertex. During the algorithm's execution, whenever a vertex is selected or updated, an arrow is drawn from the vertex that supplied the current best label.
Conditions: Predecessor arrows must have been recorded during the label updates.; The destination label has been finalized (circled).; The graph is directed or treated as such for the purpose of following the recorded arrows.
Continue with related videos in the same subject.
YouTube7:02
YouTube5:33
YouTube7:38