ในการหาเส้นทางที่สั้นที่สุดมีอัลกอริทึมหลายแบบที่แตกต่างกันที่ใช้หาเส้นทางที่สั้นที่สุดระหว่าง 2 จุดยอดในกราฟมีน้ำหนัก เราจะแสดงขั้นตอนที่ค้นพบ
โดย E. Dijkstra ในปี 1959 ในรูปกราฟมีน้ำหนัก ไม่มีทิศทาง ซึ่งน้ำหนักทั้งหมดเป็นค่าบวกง่ายที่จะปรับเข้ากับปัญหาระยะทางที่สั้นที่สุดในกรา

วิธีแก้ปัญหา
     แม้ว่าเส้นทางที่สั้นที่สุดจะหาได้ง่ายโดยการสำรวจ เราก็ได้พัฒนาความคิดที่มีประโยชน์ของอัลกอริทึมของ
Dijskstra เราจะแก้ปัญหานี้โดยการหาความยาวของเส้นทางที่สั้นที่สุดจาก a ต่อไปเรื่อยๆ จนถึง z

     เส้นทางเดียวเท่านั้นที่เริ่มที่ a ทั้ง a ไป b และa ไป d ดังนั้นความยาวของ a ไป b และa ไป d คือ 4 และ 2
ตามลำดับ จะเห็นได้ว่าจุด d เป็นจุดที่ใกล้กับ a ที่สุด

     เราสามารถหาจุดถัดไปที่ใกล้ที่สุดได้โดยมองเส้นทางทั้งหมด แล้วผ่านไปทาง a และ d เท่านั้น แล้วเส้นทาง
ที่สั้นที่สุดจาก a ไปยัง b มีความยาวมีความยาว 4 และเส้นทางที่สั้นที่สุดไป e คือ aไป d ไป e มีความยาว 5
เพราะฉะนั้น จุดที่สั้นที่สุดถัดไปคือ a

     การหาจุดที่ใกล้กับ a มากที่สุดเป็นจุดที่ 3 เราต้องทดสอบเส้นทางที่ผ่าน a , d หรือ b เท่านั้น มีเส้นทางหนึ่ง
ความยาว 7 ไปยัง c (จาก a ไป bไป c) และเส้นทางอีกความยาว 6 ไปยัง z (จาก a ไป d ไป e ไป z ) z จึงเป็น
จุดถัดไปที่ใกล้ที่สุดไปยัง a และมีเส้นทางที่สั้นที่สุดไปยัง z เท่ากับ 6

จาก ตัวอย่างที่1 เป็นการยกตัวอย่างวิธีการใช้ในอัลกอริทึมของ Dijkstra สังเกตว่าระยะสั้นที่สุดจาก a ไปยัง z หาได้จากการไล่จนพบ แต่อย่างไรก็ตาม
การไล่หาจะไม่สามารถทำได้ถ้ากราฟมีจำนวนจุดมาก

      ตอนนี้เราจะพิจารณาปัญหาทั่วๆไป ของการหาความยาวระยะทางสั้นที่สุดระหว่าง a และ z ในแบบกราฟมีน้ำหนักทั่วๆไปที่เชื่อมกันอย่างไม่เป็นทิศทาง
อัลกอริทึมของ Dijkstra จะดำเนินการโดยหาความยาวเส้นทางที่สั้นสุดจาก a ไปยังจุดแรกก่อน และต่อมาคือความยาวจาก a ไปยังจุดที่สอง และหาไปเรื่อยๆ
จนกว่าจะเจอเส้นทางที่สั้นสุดจาก a ไปยัง z อัลกอริทึมจะอาศัยชุดของการวนซ้ำ ชุดของจุดที่แตกต่างกันจะถูกสร้างโดยการเพิ่มทีละจุดเข้าไปในการวนซ้ำ
แต่ละรอบ

Dijkstra's Algorithm

{ G has vertices a = v0 , v1 , v2 , ... , vn  = Z and weight w = ( vi , vj ) = ฅ if { vi , vj } is not an edge in G }

For i = 1 to n
       L(vi) := ฅ
       L(a) := 0
       S := f
       While Z f S
              Begin
                     u := a vertex not in S with L(u) minimal
                     S = S ศ { u }
                     For all vwrtices v is not in S
                            If L(u) + w(u,v) < L(v) Then
                                   L(v) = L(u) + w(u,v)
                            End

การทำงาน
- เริ่มต้น ที่จุด a ให้เป็นศูนย์ จุดอื่นๆให้เป็น ฅ

- Loop ที่ 1 พบว่ามีน้ำหนักจาก a ไปยังจุด b และ d ให้นำค่าน้ำหนักไปเขียนลงในตาราง จุดอื่นๆที่ไม่มี
น้ำหนักให้คงไว้เป็น ฅ แล้วเลือกจุดที่มีน้ำหนักน้อยที่สุดซึ่งคือจุด d เพื่อออกไปทำงานยัง Loop ต่อไป

- Loop ที่ 2 จุดใดที่มีค่าน้ำหนักแต่ไม่มีการเลือกใน Loop ก่อนหน้านี้ให้นำมาเขียนไว้ดังเดิมนั่นคือน้ำหนัก 4 ที่
จุด b จากนั้นมองหาจุดที่มีน้ำหนักจากจุดที่เลือกมานั่นคือ d ไปยังจุดอื่นๆ แล้วนำค่าน้ำหนักไปรวมกับค่าน้ำหนัก
ของ Loop ก่อนหน้านี้ที่ได้เลือกมา กล่าวคือ พบว่ามีน้ำหนักจากจุด d ไปยังจุด e ค่าน้ำหนักเท่ากับ 3 ให้นำ 3 ไป
บวกกับค่าน้ำหนักที่เลือกมาก่อนหน้านี้ คือ 2 ได้เป็น 5 จึงนำไปใส่ในตาราง จุดอื่นๆที่ไม่มีค่าน้ำหนักให้คงไว้เป็น ฅ
แต่หากจุดใดมีการเลือกไปแล้วจะไม่ต้องใส่เป็น ฅ อีกเลย นั่นคือจุด d ที่ได้เลือกไปแล้วจะไม่ต้องใส่ ฅ อีก จากนั้น
เลือกจุดที่มีน้ำหนักน้อยที่สุดซึ่งคือจุด b เพื่อออกไปทำงานยัง Loop ต่อไป

- Loop ที่ 3 จะมองในลักษณะเดียวกับ Loop ก่อนหน้านี้ มีน้ำหนักจาก b ไปยัง c กับ e มีน้ำหนักเท่ากับ 3 ที่จุด
c จะต้องลงนำหนักเป็น 3+4 = 7 น้ำหนัก 4 ที่นำมาบวก มาจากการนำน้ำหนักที่ถูกเลือกมาจาก Loop ก่อนหน้านี้
ที่จุด e ก็ทำเช่นเดียวกันหากแต่ว่าเมื่อรวมน้ำหนักแล้วได้เท่ากับ 7 แต่ใน Loop ก่อนหน้านี้มีน้ำหนักเพียง 5 ในกรณี
นี้จะใช้น้ำหนักที่น้อยเป็นหลัก ที่ Loop นี้เราจะเลือก e ซึ่งมีน้ำหนักน้อยที่สุด

- Loop ที่ 4 ทำงานลักษณะเดียวกันกับ Loop ที่ผ่านมา ที่ Loop นี้จะเลือก z เพราะมีน้ำหนักน้อยที่สุด ทำให้เรา
สามารถหา ระยะทางที่สั้นที่สุดระหว่าง a ถึง z เท่ากับ 6