Students Struggle with Concepts in Dijkstra's Algorithm

Teachers who are aware of potential student misconceptions teach better than teachers who do not. In this article, we focus on misconceptions in the context of teaching and learning graph algorithms: we seek to discover student misconceptions about Dijkstra's shortest-path algorithm and related concepts. We observed and interviewed fourteen students who worked on a visual simulation task involving the algorithm; we qualitatively analyzed these data to explore the students' mistakes and their underlying reasons. We find, among other things, that students conflate concepts such as spanning tree, fringe, and priority queue and that students may neglect the greedy and dynamic-programming aspects of the algorithm; we also identify usability issues in the visualization tool we employed. These findings suggest that teachers and tool designers need to take great care to help students tease apart the key concepts in graph algorithms.