Bài toán đường đi ngắn nhất trong dạy học lí thuyết đồ thị ở trường phổ thông: Một nghiên cứu tri thức luận lịch sử

Tóm tắt

This paper explores the historical development and educational implications of graph theory, emphasizing its origin from Euler’s solution to the “Seven Bridges of Königsberg” problem in 1736. It categorizes shortest-path algorithms based on problem types, input graph characteristics, and basic techniques, highlighting classical algorithms and Dijkstra's improvements. The paper also compares the classical Dijkstra’s approach using set operations with its modern adaptation utilizing labeling techniques, emphasizing their respective benefits and challenges in teaching. Through proposed teaching scenarios, the study aims to enhance students' conceptual understanding of shortest-path algorithms, emphasizing both computational efficiency and pedagogical clarity. The findings suggest modifications to teaching methods for improved student comprehension and algorithmic implementation.