Skip to main content
MathidiaMathematics Academy
Discrete mathematics
Lesson 50 of 75
Review

Graph algorithms

Objective. Apply shortest-path and traversal algorithms.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Graph algorithms are systematic procedures for solving structural problems on graphs, such as finding shortest paths or visiting every vertex. Dijkstra's algorithm finds shortest paths from a single source vertex in a weighted graph with non-negative edge weights, repeatedly selecting the unvisited vertex with smallest tentative distance and updating its neighbours' distances. Breadth-first search (BFS) explores a graph level by level using a queue, making it ideal for finding shortest paths in unweighted graphs, while depth-first search (DFS) explores as far as possible along each branch using a stack or recursion before backtracking. For a graph where all edges have weight 1, BFS from a source vertex correctly gives shortest path distances identical to what Dijkstra's algorithm would compute.

Worked example

A graph algorithm performs breadth-first search from vertex A on an unweighted graph. If B is found at distance 2, state what this distance represents.

2
Coordinate grid with the line 2
  1. 1Recall that BFS explores vertices in order of increasing distance from the source.
  2. 2Note that distance here is measured in the minimum number of edges traversed.
  3. 3Since B is found at level 2, the shortest path uses exactly 2 edges.
  4. 4State the interpretation of this distance value.

Answer: The shortest path from A to B uses exactly 2 edges

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students apply Dijkstra's algorithm to a graph containing negative edge weights and trust the result; the algorithm's greedy selection step assumes non-negative weights, and it can give incorrect shortest paths otherwise.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard