Skip to content

Algorithms, networks and linear programming

Introduced
Watch lesson
Vocabulary
English Meaning
Dijkstra's algorithm/ˈdeɪkstrəz ˈælɡərɪθəm/A shortest-path algorithm that makes the smallest temporary distance permanent, then updates neighbours; edge weights must be non-negative.
algorithms/ˈælɡərɪθəmz/A finite sequence of precise steps for solving a problem or carrying out a task.
networks/ˈnetwɜːks/A set of connected devices or nodes that can exchange information.
edges/ˈedʒɪz/Connections between vertices in a graph, or boundary segments of a geometric shape.
spanning treeA tree that joins every vertex of a network, with no cycles.
vertices/ˈvɜːtɪsiːz/The nodes of a graph; in geometry, the corner points where edges meet.
minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/A connected cycle-free network joining every vertex with the smallest possible total edge weight.
objective function/ɒbˈdʒektɪv ˈfʌŋkʃn/The quantity expressed as a function of decision variables that is to be maximised or minimised.
constraints/kənˈstreɪnts/A condition or limit that a valid solution must satisfy.
feasible regionThe set of points that satisfy all the constraints of a linear programming problem.
Next →

Handout

Log in or create account

IGCSE, A-Level & AP