Thuật toán Johnson được Donald B. Johnson tìm ra năm 1977[1]. Thuật toán Johnson là một thuật toán giải quyết bài toán đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số và không có chu trình âm. Nó hoạt động bằng cách sử dụng thuật toán Bellman – Ford để tính toán một phép biến đổi của đồ thị đầu vào loại bỏ tất cả các trọng số âm, cho phép thuật toán Dijkstra được sử dụng trên đồ thị đã biến đổi[2][3].