Lecture about graphs
April 18, 2025
I gave this lecture to finalists of the Luxembourgish olympiad in informatics.
After a quick introduction to graphs, we talk about how graphs are stored in memory, as adjacency matrices, edge lists or neighbourhood lists.
We then go over to graph traversal with BFS (breadth first search) and DFS (depth first search) and how to determine connectedness of graphs.
The bulk of the lesson is spent on algorithms for shortest paths, notably Floyd-Warshall and Dijkstra. Finally we use them to solve the problem ‘Péage’ from LIO 2020.
You can find the slides here: Graphs