- довільна функція, що відображає вершини на дійсні числа. Для кожного ребра визначимо
Нехай - довільний шлях з вершини у вершину . є найкоротшим шляхом з ваговою функцією тоді і тільки тоді, коли він є найкоротшим шляхом з ваговою функцією , тобто рівність рівносильно рівності . Крім того, граф містить цикл з негативним вагою з використанням вагової функції тоді і тільки тоді, коли він містить цикл з негативним вагою з використанням вагової функції .
Зміна ваги. Для даного графа створимо новий граф , де , для деякої нової вершини , а .
- Розширимо вагову функцію таким чином, щоб для всіх вершин виконувалося рівність .
- Далі визначимо для всіх вершин величину і нові ваги для всіх ребер.
Основна процедура. В алгоритмі Джонсона використовується алгоритм Беллмана-Форда і алгоритм Дейкстри, реалізовані у вигляді підпрограм. Ребра зберігаються у вигляді списків суміжних вершин. Алгоритм повертає звичайну матрицю розміром , де , або видає повідомлення про те, що вхідний граф містить цикл з негативною вагою.
Складність. Якщо в алгоритмі Дейкстри неспадними чергу з пріоритетами реалізована у вигляді фібоначчійової купи, то час роботи алгоритму Джонсона дорівнює . При простіший реалізації неубутною черги з пріоритетами час роботи стає рівним , але для розріджених графів ця величина в асимптотичному межі веде себе краще, ніж час роботи алгоритму Флойда-Воршелла.