ขั้นตอนวิธีของจอห์นสันประกอบด้วยขั้นตอนต่อไปนี้

1. สร้างจุดหรือปม ใหม่ขึ้นหนึ่งจุดลงในกราฟ และสร้างเส้นเชื่อมจากจุดใหม่ที่เพิ่มมาไปยังจุดอื่นทุกจุด โดยกำหนดน้ำหนักทั้งหมดเป็น 0
2. ใช้ขั้นตอนวิธีของเบลล์แมน-ฟอร์ดจากจุดใหม่ หาน้ำหนักน้อยที่สุดจากจุดใหม่ไปยังทุกจุดแต่ละจุดก็เก็บค่าไว้ ถ้าตรวจพบวงจร ที่มีน้ำหนักติดลบ ให้หยุดการทำงาน
3. แปลงกราฟดั้งเดิมไม่ให้มีน้ำหนักติดลบ โดยใช้ค่าที่เก็บไว้ในของแต่ละจุดที่คำนวณได้จากขั้นตอนวิธีของเบลล์แมน-ฟอร์ด กล่าวคือ เส้นเชื่อมจากจุด ก ไปยังจุด ข เดิมมีน้ำหนักเป็น น้ำหนักเส้นเชื่อม(ก,ข) เปลี่ยนค่าน้ำหนักใหม่ของเส้นเชื่อมเส้นนั้นเป็น น้ำหนักเส้นเชื่อม(ก,ข) + ค่าที่เก็บไว้ใน ก − ค่าที่ีเก็บไว้ใน ข
4. สุดท้ายใช้ขั้นตอนวิธีของไดค์สตรา เพื่อหาเส้นทางสั้นที่สุดจากจุดใดจุดต้นทางหนึ่ง ไปยังจุดอื่นในกราฟที่แปลงน้ำหนักแล้วได้