1/11
Vocabulary practice flashcards based on lecture notes on shortest paths and Dijkstra's algorithm.
Distance Between Vertices d(u,v)
The length of the shortest path between vertex u and vertex v in a graph G.

Graph G Example (Section 3.1)
A weighted graph with 4 vertices (v1,v2,v3,v4) used to demonstrate finding the distance d(v1,v4) and path between vertices.
Dijkstra's Algorithm
An algorithm used to find the shortest path from a starting vertex s to a target vertex t in a weighted graph G.
Input for Dijkstra's Algorithm
A weighted graph G and specified vertices s,t×V(G).
Step 1 of Dijkstra's Algorithm
Label vertex s with π(s)=0, label all other vertices v∈V(G)−{s} with π(v)=∞, and set T=V(G).
Step 2 of Dijkstra's Algorithm
Select a vertex u∈T with the minimum label value π(u).
Step 3 of Dijkstra's Algorithm
If u=t, stop the process and output the result message.
Step 4 of Dijkstra's Algorithm
For each edge e=uv where v∈T, update the label of vertex v to π(v)=min{π(v),π(u)+w(e)}.
Step 5 of Dijkstra's Algorithm
Update the unvisited set T=T−{u} and return to Step 2.

Dijkstra's Algorithm Workflow
The complete 5-step algorithmic procedure for iteratively calculating vertex labels π(v) to find the shortest path.

8-Vertex Shortest Path Problem (Section 3.3)
An 8-vertex graph problem (v1 through v8) tracking vertex labels π(vi) across iterations to find the shortest path from v1 to v8.

Shortest Path Summary Table (Section 3.4)
A table layout used to record the origin vertex, destination vertices (v2 to v8), specific shortest path sequences, and total path lengths.