v คือ จำนวนปมe คือ จำนวนเส้นเชื่อมถ้า ขั้นตอนวิธีของไดค์สตรา ใช้ binary heap จะทำให้ Johnson ใช้เวลา O ( v e l o g v ) {\displaystyle O(velogv)} ซึ่งเมื่อใช้กับ กราฟที่มีเส้นเชื่อมน้อยๆ จะเร็วกว่าใช้ ขั้นตอนวิธีของฟลอยด์-วอร์แชล ที่ใช้ O(v3)