A practical activity on the shortest path problem with theoretical and algorithmic implications

The shortest path problem and Dijkstra’s algorithm consti- tute foundational topics in many basic courses of Operations Research and Computer Science. Yet, they remain conceptually challenging for many students: experience and literature document recurrent misconcep- tions, persistent difficulties in grasping algorithmic logic and optimality conditions and a limited understanding of the dual perspective. Learn- ers often struggle to connect procedural steps with underlying graph- theoretic structures and to interpret shortest path problems within a broader optimization framework. This paper proposes a structured manual activity designed for university-level courses to support conceptual understanding through direct physical engagement. Using inexpensive and tangible materials, students construct and iteratively update weighted networks, physi- cally enacting the step-by-step execution of Dijkstra’s algorithm. The activity is explicitly designed to make visible the role of tentative dis- tances, the maintenance of feasibility, and the relationship between pri- mal shortest paths and dual node potentials. Grounded in the active learning paradigm, the approach leverages well-known cognition princi- ples according to which coordinated hand-brain activity can strengthen intuition and facilitate abstraction. By externalizing algorithmic pro- cesses into manipulable artifacts, students are encouraged to reason about optimality and dual feasibility in a concrete manner before formalization.