ปัญหาเส้นทางที่สั้นที่สุด

ในทฤษฎีกราฟปัญหาเส้นทางที่สั้นที่สุดคือปัญหาของการหาเส้นทางระหว่างจุดยอด สองจุด (หรือโหนด) ในกราฟโดยที่ผลรวมของน้ำหนักของขอบที่ประกอบกันเป็นเส้นทางนั้นมีค่าน้อยที่สุด^{[ 1 ]}

ปัญหาการหาเส้นทางที่สั้นที่สุดระหว่างทางแยกสองแห่งบนแผนที่ถนนสามารถจำลองได้เป็นกรณีพิเศษของปัญหาเส้นทางที่สั้นที่สุดในกราฟ โดยที่จุดยอดจะสอดคล้องกับทางแยก และขอบจะสอดคล้องกับส่วนของถนน โดยแต่ละส่วนจะมีน้ำหนักตามความยาวหรือระยะทางของแต่ละส่วน^{[ 2 ]}

ปัญหาเส้นทางที่สั้นที่สุดสามารถกำหนดได้สำหรับกราฟไม่ว่าจะ เป็นกราฟ แบบไม่มี ทิศทาง แบบ มี ทิศทางหรือแบบผสมคำจำกัดความสำหรับกราฟแบบไม่มีทิศทางระบุว่าขอบทุกเส้นสามารถเดินทางได้ทั้งสองทิศทาง กราฟแบบมีทิศทางกำหนดให้จุดยอดที่อยู่ติดกันต้องเชื่อมต่อกันด้วยขอบที่มีทิศทางที่เหมาะสม^{[ 3 ]}

จุดยอดสองจุดจะอยู่ติดกันเมื่อทั้งสองจุดนั้นอยู่บนเส้นขอบร่วมกันเส้นทางในกราฟแบบไม่มีทิศทางคือลำดับของจุดยอดที่อยู่ติดกับสำหรับเส้นทางดังกล่าวเรียกว่าเส้นทางที่มีความยาวจากไปยัง( เป็นตัวแปร การกำหนดหมายเลขของตัวแปรสัมพันธ์กับตำแหน่งในลำดับและไม่จำเป็นต้องสัมพันธ์กับการกำหนดหมายเลขแบบมาตรฐาน) ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}$${\displaystyle v_{i}}$${\displaystyle v_{i+1}}$${\displaystyle 1\leq i<n}$${\displaystyle P}$${\displaystyle n-1}$${\displaystyle v_{1}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$

ให้เป็นขอบที่เชื่อมทั้งและกำหนดฟังก์ชันน้ำหนักที่เป็นค่าจริงและกราฟแบบไม่มีทิศทาง (แบบง่าย) เส้นทางที่สั้นที่สุดจากไปคือเส้นทาง(โดยที่และ) ที่ทำให้ผลรวม มีค่าน้อยที่สุด ตลอดทุกค่าที่เป็นไปได้ เมื่อแต่ละขอบในกราฟมีน้ำหนักหนึ่งหน่วย หรือนี่เทียบเท่ากับการหาเส้นทางที่มีจำนวนขอบน้อยที่สุด ${\displaystyle E=\{e_{i,j}\}}$${\displaystyle e_{i,j}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle f:E\rightarrow \mathbb {R} }$${\displaystyle G}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$${\displaystyle v_{1}=v}$${\displaystyle v_{n}=v'}$${\displaystyle n}$${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$${\displaystyle f:E\ลูกศรขวา \{1\}}$

บางครั้งปัญหานี้ก็ถูกเรียกว่าปัญหาเส้นทางที่สั้นที่สุดระหว่างจุดคู่เดียวเพื่อแยกแยะออกจากปัญหาประเภทอื่นๆ ดังต่อไปนี้:

• ปัญหาการหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวคือปัญหาที่เราต้องหาเส้นทางที่สั้นที่สุดจากจุดยอดvไปยังจุดยอดอื่นๆ ทั้งหมดในกราฟ
• ปัญหาการหาเส้นทางที่สั้นที่สุดจากจุดยอดทั้งหมดในกราฟทิศทางไปยังจุดยอดปลายทางเดียวvสามารถลดรูปเป็นปัญหาการหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นเดียวได้โดยการกลับทิศทางของส่วนโค้งในกราฟทิศทาง
• ปัญหาการหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดยอดคือปัญหาที่เราต้องหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดยอดvและv'ในกราฟ

การสรุปโดยทั่วไปเหล่านี้มีอัลกอริธึมที่มีประสิทธิภาพมากกว่าวิธีการแบบง่ายๆ ที่ใช้อัลกอริธึมหาเส้นทางที่สั้นที่สุดแบบคู่เดียวกับทุกคู่จุดยอดที่เกี่ยวข้อง

มีอัลกอริธึมหลายตัวที่เป็นที่รู้จักกันดีในการแก้ปัญหานี้และปัญหาในรูปแบบต่างๆ

• อัลกอริทึมของ Dijkstraแก้ปัญหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวโดยใช้ค่าน้ำหนักของขอบที่ไม่เป็นลบเท่านั้น
• อัลกอริทึม Bellman–Fordสามารถแก้ปัญหาแหล่งกำเนิดเดียวได้หากน้ำหนักของขอบอาจเป็นค่าลบ
• อัลกอริทึมการค้นหา A*แก้ปัญหาการหาเส้นทางที่สั้นที่สุดระหว่างคู่จุดเดียว โดยใช้ฮิวริสติกส์เพื่อพยายามเร่งความเร็วในการค้นหา
• อัลกอริทึม Floyd–Warshallแก้ปัญหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุด
• อัลกอริทึมของจอห์นสันสามารถแก้ปัญหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดได้ และอาจเร็วกว่าอัลกอริทึมฟลอยด์-วอร์แชลบนกราฟแบบเบาบาง
• อัลกอริทึม Viterbiแก้ปัญหาเส้นทางสุ่มที่สั้นที่สุดโดยเพิ่มน้ำหนักเชิงความน่าจะเป็นให้กับแต่ละโหนด

อัลกอริทึมเพิ่มเติมและการประเมินที่เกี่ยวข้องสามารถพบได้ในCherkassky, Goldberg & Radzik (1996 )

น้ำหนัก	ความซับซ้อนเชิงเวลา	ผู้เขียน
${\displaystyle \mathbb {R} }$+	${\displaystyle O(V^{2})}$	ไดจ์กสตรา 1959
${\displaystyle \mathbb {R} }$+	${\displaystyle O((E+V)\log {V})}$	จอห์นสัน 1977 ( ฮีปไบนารี )
${\displaystyle \mathbb {R} }$+	${\displaystyle O(E+V\log {V})}$	Fredman & Tarjan 1984 ( ฮีปฟีโบนัชชี )
${\displaystyle \mathbb {N} }$	${\displaystyle O(E)}$	Thorup 1999 (ต้องใช้การคูณแบบใช้เวลาคงที่)
${\displaystyle \mathbb {R} }$+	${\displaystyle O(E{\sqrt {\log V\log \log V}})}$	ต้วนและคณะ 2023

อัลกอริทึม	ความซับซ้อนเชิงเวลา	ผู้เขียน
การค้นหาแบบกว้าง	${\displaystyle O(E+V)}$

อัลกอริทึมที่ใช้การเรียงลำดับเชิงโทโพโลยีสามารถแก้ปัญหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวได้ในเวลาΘ( E + V )ในกราฟทิศทางแบบไม่มีวงจรที่มีน้ำหนักตามอำเภอใจ^{[ 4 ]}

ตารางต่อไปนี้นำมาจากSchrijver (2004)โดยมีการแก้ไขและเพิ่มเติมบางส่วน พื้นหลังสีเขียวแสดงถึงขอบเขตที่ดีที่สุดในเชิงอะซิมโทติกในตารางLคือความยาวสูงสุด (หรือน้ำหนัก) ในบรรดาขอบทั้งหมด โดยสมมติว่าน้ำหนักของขอบเป็นจำนวนเต็ม

น้ำหนัก	อัลกอริทึม	ความซับซ้อนเชิงเวลา	ผู้เขียน
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}EL)}$	ฟอร์ด 1956
${\displaystyle \mathbb {R} }$	อัลกอริทึมเบลล์แมน-ฟอร์ด	${\displaystyle O(VE)}$	ชิมเบล 1955 , เบลล์แมน 1958 , มัวร์ 1959
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}\log {V})}$	แดนท์ซิก 1960
${\displaystyle \mathbb {R} }$	อัลกอริทึมของ Dijkstraพร้อมลิสต์	${\displaystyle O(V^{2})}$	Leyzorek et al. 1957 , Dijkstra 1959 , Minty (ดูPollack & Wiebenson 1960 ), Whiting & Hillier 1960
${\displaystyle \mathbb {R} }$	อัลกอริทึมของ Dijkstraกับฮีปไบนารี	${\displaystyle O((E+V)\log {V})}$	จอห์นสัน 1977
${\displaystyle \mathbb {R} }$	อัลกอริทึมของ Dijkstraกับฮีปฟิโบนาชี่	${\displaystyle O(E+V\log {V})}$	เฟรดแมนและทาร์จัน 1984 , เฟรดแมนและทาร์จัน 1987
${\displaystyle \mathbb {R} }$	อัลกอริทึมควอนตัม ไดจ์กสตรา พร้อมรายการความสัมพันธ์	${\displaystyle O({\sqrt {VE}}\log ^{2}{V})}$	Dürr et al. 2006 [ 5 ]
${\displaystyle \mathbb {R} }$	ระบบลูกผสม ของ Dijkstra - Bellman–Fordพร้อมการลดขอบเขต แบบแบ่งแยกและพิชิต	${\displaystyle O(E\log ^{2/3}{V})}$	Duan et al. 2025 [ 6 ]
${\displaystyle \mathbb {N} }$	อัลกอริทึมของ Dial [ 7 ] ( อัลกอริทึมของ Dijkstraโดยใช้คิวแบบถังที่มี ถัง Lถัง)	${\displaystyle O(E+LV)}$	โทร 1969
		${\displaystyle O(E\log {\log {L}})}$	จอห์นสัน 1981 , คาร์ลสัน แอนด์ โพเบลเต 1983
	อัลกอริทึมของกาโบว์	${\displaystyle O(E\log _{E/V}L)}$	กาโบว 1983 , กาโบว 1985
		${\displaystyle O(E+V{\sqrt {\log {L}}})}$	อาฮูจาและคณะ 1990
${\displaystyle \mathbb {N} }$	ธอร์รัป	${\displaystyle O(E+V\log {\log {V}})}$	ธอร์รัป 2004

น้ำหนัก	อัลกอริทึม	ความซับซ้อนเชิงเวลา	ผู้เขียน
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}EL)}$	ฟอร์ด 1956
${\displaystyle \mathbb {R} }$	อัลกอริทึมเบลล์แมน-ฟอร์ด	${\displaystyle O(VE)}$	ชิมเบล 1955 , เบลล์แมน 1958 , มัวร์ 1959
${\displaystyle \mathbb {R} }$	อัลกอริทึม Johnson-Dijkstraที่ใช้ฮีปไบนารี	${\displaystyle O(VE+V\log V)}$	จอห์นสัน 1977
${\displaystyle \mathbb {R} }$	แบบจำลอง Johnson-Dijkstraที่มีFibonacci heap	${\displaystyle O(VE+V\log V)}$	Fredman & Tarjan 1984 , Fredman & Tarjan 1987ดัดแปลงหลังจากJohnson 1977
${\displaystyle \mathbb {Z} }$	เทคนิคของจอห์นสันที่นำมาใช้กับอัลกอริทึมของไดอัล[ 7 ]	${\displaystyle O(V(E+L))}$	หน้าปัดปี 1969ดัดแปลงจากจอห์นสัน ปี 1977
${\displaystyle \mathbb {Z} }$	วิธีจุดภายในพร้อมตัวแก้ลาปลาเซียน	${\displaystyle O(E^{10/7}\log ^{O(1)}V\log ^{O(1)}L)}$	โคเฮนและคณะ 2017
${\displaystyle \mathbb {Z} }$	วิธีจุดภายในพร้อมตัวแก้ปัญหาการไหล ${\displaystyle \ell _{p}}$	${\displaystyle E^{4/3+o(1)}\log ^{O(1)}L}$	Axiotis, Mądry & Vladu 2020
${\displaystyle \mathbb {Z} }$	วิธีการจุดภายในที่แข็งแกร่งพร้อมการร่างภาพ	${\displaystyle O((E+V^{3/2})\log ^{O(1)}V\log ^{O(1)}L)}$	แวน เดน แบรนด์ และคณะ 2020
${\displaystyle \mathbb {Z} }$	${\displaystyle \ell _{1}}$วิธีการจุดภายในพร้อมโครงสร้างข้อมูลวงจรอัตราส่วนขั้นต่ำแบบไดนามิก	${\displaystyle O(E^{1+o(1)}\log L)}$	เฉินและคณะ 2022
${\displaystyle \mathbb {Z} }$	โดยอิงจากการแยกส่วนเส้นผ่านศูนย์กลางต่ำ	${\displaystyle O(E\log ^{8}V\log L)}$	เบิร์นสไตน์, นานองไก และ วูล์ฟ-นิลเซ่น 2022
${\displaystyle \mathbb {R} }$	เส้นทางที่สั้นที่สุดที่มีข้อจำกัดจำนวนฮอป	${\displaystyle O(EV^{8/9}\log ^{O(1)}V)}$	ฟิเนแมน 2024
${\displaystyle \mathbb {R} }$	สไตเนอร์-ทรี แกดเจ็ต	${\displaystyle O(V^{2+o(1)})}$	Khanna & Song 2026 [ 8 ] harvnb error: no target: CITEREFKhannaSong2026 (help)

ค้นหาวงจรลบหรือคำนวณระยะทางไปยังจุดยอดทั้งหมด

น้ำหนัก	อัลกอริทึม	ความซับซ้อนเชิงเวลา	ผู้เขียน
${\displaystyle \mathbb {Z} }$		${\displaystyle O(E{\sqrt {V}}\log {N})}$	แอนดรูว์ วี. โกลด์เบิร์ก

น้ำหนัก	อัลกอริทึม	ความซับซ้อนเชิงเวลา	ผู้เขียน
${\displaystyle \mathbb {R} _{\geq 0}}$		${\displaystyle O(V)}$	เฮนซิงเกอร์และคณะ 1997

การไหลในเครือข่าย^{[ 9 ]}เป็นแนวคิดพื้นฐานในทฤษฎีกราฟและการวิจัยการดำเนินงาน ซึ่งมักใช้ในการจำลองปัญหาที่เกี่ยวข้องกับการขนส่งสินค้า ของเหลว หรือข้อมูลผ่านเครือข่าย ปัญหาการไหลในเครือข่ายโดยทั่วไปเกี่ยวข้องกับกราฟแบบมีทิศทาง โดยแต่ละขอบแทนท่อ สายไฟ หรือถนน และแต่ละขอบมีความจุ ซึ่งเป็นปริมาณสูงสุดที่สามารถไหลผ่านได้ เป้าหมายคือการค้นหาการไหลที่เป็นไปได้ที่เพิ่มการไหลจากโหนดต้นทางไปยังโหนดปลายทางให้สูงสุด

ปัญหาการหาเส้นทางที่สั้นที่สุดสามารถนำมาใช้แก้ปัญหาการไหลของเครือข่ายบางประเภทได้ โดยเฉพาะอย่างยิ่งเมื่อต้องจัดการกับเครือข่ายที่มีแหล่งกำเนิดเดียวและปลายทางเดียว ในสถานการณ์เหล่านี้ เราสามารถแปลงปัญหาการไหลของเครือข่ายให้เป็นชุดของปัญหาการหาเส้นทางที่สั้นที่สุดได้

^{[ 10 ]}

1. สร้างกราฟค่าตกค้าง:
   • สำหรับแต่ละขอบ (u, v) ในกราฟเดิม ให้สร้างขอบสองขอบในกราฟส่วนที่เหลือ:
     • (u, v) ที่มีความจุ c(u, v)
     • (v, u) ที่มีความจุ 0
   • กราฟส่วนที่เหลือแสดงถึงความจุที่เหลืออยู่ในเครือข่าย
2. ค้นหาเส้นทางที่สั้นที่สุด:
   • ใช้ขั้นตอนวิธีหาเส้นทางที่สั้นที่สุด (เช่น ขั้นตอนวิธีของ Dijkstra, ขั้นตอนวิธีของ Bellman-Ford) เพื่อค้นหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปยังโหนดปลายทางในกราฟส่วนที่เหลือ
3. เพิ่มการไหลเวียน:
   • ค้นหาความจุขั้นต่ำตามเส้นทางที่สั้นที่สุด
   • เพิ่มปริมาณการไหลบริเวณขอบของเส้นทางที่สั้นที่สุดด้วยความจุขั้นต่ำนี้
   • ลดความจุของเส้นทางในทิศทางไปข้างหน้า และเพิ่มความจุของเส้นทางในทิศทางย้อนกลับ
4. อัปเดตกราฟค่าตกค้าง:
   • อัปเดตกราฟส่วนที่เหลือตามการไหลที่เพิ่มขึ้น
5. ทำซ้ำ:
   • ทำซ้ำขั้นตอนที่ 2-4 จนกว่าจะไม่พบเส้นทางเพิ่มเติมจากแหล่งที่มาไปยังปลายทาง

ปัญหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดยอด คือการหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดยอดv , v'ในกราฟ ปัญหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่จุดยอดสำหรับกราฟทิศทางที่ไม่มีน้ำหนัก ถูกนำเสนอโดยShimbel (1953)ซึ่ง สังเกตว่าสามารถแก้ไขได้โดยการคูณเมทริกซ์จำนวนเชิงเส้น ซึ่งใช้เวลาทั้งหมดO ( V ⁴ )

น้ำหนัก	ความซับซ้อนเชิงเวลา	อัลกอริทึม
${\displaystyle \mathbb {R} }$+	${\displaystyle O(V^{3})}$	อัลกอริทึมฟลอยด์-วอร์แชลล์
${\displaystyle \{1,\infty \}}$	${\displaystyle O(V^{\omega }\log V)}$	อัลกอริทึมของ Seidel (เวลาทำงานที่คาดการณ์ไว้โดยใช้อัลกอริทึมการคูณเมทริกซ์แบบเร็ว )
${\displaystyle \mathbb {N} }$	${\displaystyle O(V^{3}/2^{\Omega (\log V)^{1/2}})}$	วิลเลียมส์ 2014
${\displaystyle \mathbb {R} }$+	${\displaystyle O(EV\log \alpha (E,V))}$	เพ็ตตี้และรามาจันดราน 2002
${\displaystyle \mathbb {N} }$	${\displaystyle O(EV)}$	Thorup 1999นำไปใช้กับทุกจุดยอด (ต้องใช้การคูณในเวลาคงที่)

น้ำหนัก	ความซับซ้อนเชิงเวลา	อัลกอริทึม
${\displaystyle \mathbb {R} }$(ไม่มีวงจรลบ)	${\displaystyle O(V^{3})}$	อัลกอริทึมฟลอยด์-วอร์แชลล์
${\displaystyle \mathbb {N} }$	${\displaystyle O(V^{3}/2^{\Omega (\log V)^{1/2}})}$	วิลเลียมส์ 2014
${\displaystyle \mathbb {R} }$(ไม่มีวงจรลบ)	${\displaystyle O(V^{2.5}\log ^{2}{V})}$	การค้นหาควอนตัม[ 11 ] [ 12 ]
${\displaystyle \mathbb {R} }$(ไม่มีวงจรลบ)	${\displaystyle O(EV+V^{2}\log V)}$	จอห์นสัน–ไดจ์กสตรา
${\displaystyle \mathbb {R} }$(ไม่มีวงจรลบ)	${\displaystyle O(EV+V^{2}\log \log V)}$	เพ็ตตี้ 2004
${\displaystyle \mathbb {N} }$	${\displaystyle O(EV+V^{2}\log \log V)}$	ฮาเกอรัป 2000

อัลกอริทึมเส้นทางที่สั้นที่สุดจะถูกนำมาใช้เพื่อค้นหาเส้นทางระหว่างตำแหน่งทางกายภาพโดยอัตโนมัติ เช่น เส้นทางการขับขี่บน เว็บไซต์ แผนที่เช่นMapQuestหรือGoogle Mapsสำหรับแอปพลิเคชันนี้จะมีอัลกอริทึมเฉพาะที่รวดเร็วให้บริการ^{[ 13 ]}

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

ใน บริบทของ การสร้างเครือข่ายหรือการสื่อสารโทรคมนาคมปัญหาเส้นทางที่สั้นที่สุดนี้บางครั้งเรียกว่าปัญหาเส้นทางที่มีความล่าช้าน้อยที่สุด และมักจะเชื่อมโยงกับปัญหาเส้นทางที่กว้างที่สุดตัวอย่างเช่น อัลกอริทึมอาจค้นหาเส้นทางที่กว้างที่สุด (มีความล่าช้าน้อยที่สุด) ที่สั้นที่สุด หรือเส้นทางที่สั้นที่สุด (มีความล่าช้าน้อยที่สุด) ที่กว้างที่สุด^{[ 14 ]}

อีกหนึ่งการประยุกต์ใช้ที่สนุกสนานกว่าคือเกม " หกขั้นของการเชื่อมโยง " ซึ่งพยายามหาเส้นทางที่สั้นที่สุดในกราฟ เช่น การหาดาราภาพยนตร์ที่ปรากฏตัวในภาพยนตร์เรื่องเดียวกัน

แอปพลิเคชันอื่นๆ ที่มักศึกษาในการวิจัยการดำเนินงานได้แก่ การวางผังโรงงานและสิ่งอำนวยความสะดวก หุ่นยนต์การขนส่งและการออกแบบVLSI ^{[ 15 ]}

เครือข่ายถนนสามารถพิจารณาได้ว่าเป็นกราฟที่มีน้ำหนักเป็นบวก โหนดแสดงถึงจุดตัดถนน และขอบแต่ละเส้นของกราฟจะเชื่อมโยงกับส่วนของถนนระหว่างจุดตัดสองจุด น้ำหนักของขอบอาจสอดคล้องกับความยาวของส่วนของถนนที่เกี่ยวข้อง เวลาที่ใช้ในการเดินทางผ่านส่วนนั้น หรือค่าใช้จ่ายในการเดินทางผ่านส่วนนั้น การใช้ขอบแบบมีทิศทางยังทำให้สามารถจำลองถนนทางเดียวได้ด้วย กราฟดังกล่าวมีความพิเศษตรงที่ขอบบางเส้นมีความสำคัญมากกว่าเส้นอื่น ๆ สำหรับการเดินทางระยะไกล (เช่น ทางหลวง) คุณสมบัตินี้ได้รับการกำหนดเป็นทางการโดยใช้แนวคิดของมิติทางหลวง^{[ 16 ]}มีอัลกอริทึมจำนวนมากที่ใช้ประโยชน์จากคุณสมบัตินี้ และด้วยเหตุนี้จึงสามารถคำนวณเส้นทางที่สั้นที่สุดได้เร็วกว่าที่ทำได้ในกราฟทั่วไปมาก

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

อัลกอริทึมที่มีเวลาสอบถามที่เร็วที่สุดเท่าที่ทราบเรียกว่าการติดป้ายฮับ และสามารถคำนวณเส้นทางที่สั้นที่สุดบนเครือข่ายถนนของยุโรปหรือสหรัฐอเมริกาได้ภายในเวลาเพียงเสี้ยววินาที^{[ 17 ]}เทคนิคอื่นๆ ที่เคยใช้มีดังนี้:

• ALT ( การค้นหา A* , จุดสังเกต และอสมการสามเหลี่ยม )
• ธงโค้ง
• ลำดับชั้นการหดตัว
• การกำหนดเส้นทางโหนดส่งผ่าน
• การตัดแต่งกิ่งตามระยะเอื้อม
• การติดฉลาก
• ป้ายกำกับศูนย์กลาง

สำหรับปัญหาเกี่ยวกับเส้นทางที่สั้นที่สุดในเรขาคณิตเชิงคำนวณโปรดดูที่เส้นทางที่สั้นที่สุดในเรขาคณิต ยุคลิด

เส้นทางที่สั้นที่สุดที่ขาดการเชื่อมต่อหลายเส้นทาง^{[ 18 ]}เป็นการแทนเครือข่ายเส้นทางดั้งเดิมภายในกรอบของทฤษฎี Reptation ปัญหาเส้นทางที่กว้างที่สุดจะแสวงหาเส้นทางเพื่อให้ป้ายกำกับขั้นต่ำของขอบใด ๆ มีขนาดใหญ่ที่สุดเท่าที่จะเป็นไปได้

ปัญหาอื่นๆ ที่เกี่ยวข้องอาจแบ่งออกเป็นหมวดหมู่ดังต่อไปนี้

ต่างจากปัญหาเส้นทางที่สั้นที่สุด ซึ่งสามารถแก้ไขได้ในเวลาพหุนามในกราฟที่ไม่มีวงจรลบ ปัญหาเส้นทางที่สั้นที่สุดที่รวมข้อจำกัดเพิ่มเติมเกี่ยวกับเส้นทางที่ต้องการเรียกว่าConstrained Shortest Path Firstและยากต่อการแก้ไข ตัวอย่างหนึ่งคือปัญหาเส้นทางที่สั้นที่สุดแบบมีข้อจำกัด^{[ 19 ]}ซึ่งพยายามลดต้นทุนรวมของเส้นทางในขณะเดียวกันก็รักษาเมตริกอื่นให้อยู่ต่ำกว่าเกณฑ์ที่กำหนด ทำให้ปัญหานี้เป็นNP-complete (เชื่อกันว่าปัญหาดังกล่าวไม่สามารถแก้ไขได้อย่างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดใหญ่ ดูปัญหา P = NP ) ตัวอย่าง NP-complete อีกตัวอย่างหนึ่งต้องการชุดของจุดยอดเฉพาะที่จะรวมอยู่ในเส้นทาง^{[ 20 ]}ซึ่งทำให้ปัญหานี้คล้ายกับปัญหาพนักงานขายเดินทาง (TSP) TSP คือปัญหาของการค้นหาเส้นทางที่สั้นที่สุดที่ผ่านจุดยอดทุกจุดเพียงครั้งเดียวและกลับไปยังจุดเริ่มต้น ปัญหาของการค้นหาเส้นทางที่ยาวที่สุดในกราฟก็เป็น NP-complete เช่นกัน

ปัญหาการเดินทางของ ชาวแคนาดาและปัญหาเส้นทางที่สั้นที่สุดแบบสุ่มเป็นการวางนัยทั่วไปในกรณีที่กราฟไม่เป็นที่รู้จักอย่างสมบูรณ์สำหรับผู้เคลื่อนย้าย เปลี่ยนแปลงไปตามเวลา หรือการกระทำ (การเดินทาง) เป็นแบบความน่าจะเป็น^{[ 21 ] [ 22 ]}

บางครั้ง เส้นเชื่อมในกราฟก็มีบุคลิกเฉพาะตัว: แต่ละเส้นเชื่อมมีผลประโยชน์ส่วนตัวของตนเอง ตัวอย่างเช่น เครือข่ายการสื่อสาร ซึ่งแต่ละเส้นเชื่อมเปรียบเสมือนคอมพิวเตอร์ที่อาจเป็นของบุคคลต่างกัน คอมพิวเตอร์แต่ละเครื่องมีความเร็วในการส่งข้อมูลต่างกัน ดังนั้นแต่ละเส้นเชื่อมในเครือข่ายจึงมีค่าน้ำหนักเท่ากับจำนวนมิลลิวินาทีที่ใช้ในการส่งข้อความ เป้าหมายของเราคือการส่งข้อความระหว่างสองจุดในเครือข่ายในเวลาที่สั้นที่สุดเท่าที่จะเป็นไปได้ หากเรารู้เวลาในการส่งข้อมูลของแต่ละคอมพิวเตอร์ (ค่าน้ำหนักของแต่ละเส้นเชื่อม) เราสามารถใช้อัลกอริธึมหาเส้นทางที่สั้นที่สุดแบบมาตรฐานได้ แต่ถ้าเราไม่รู้เวลาในการส่งข้อมูล เราก็ต้องขอให้แต่ละคอมพิวเตอร์บอกเวลาในการส่งข้อมูลของมัน แต่คอมพิวเตอร์อาจเห็นแก่ตัว: คอมพิวเตอร์อาจบอกเราว่าเวลาในการส่งข้อมูลของมันนานมาก เพื่อที่เราจะไม่รบกวนมันด้วยข้อความของเรา วิธีแก้ปัญหาที่เป็นไปได้คือการใช้กลไก VCG ในรูปแบบที่แตกต่างออกไปซึ่งจะกระตุ้นให้คอมพิวเตอร์เปิดเผยค่าน้ำหนักที่แท้จริงของมัน

ในบางกรณี เป้าหมายหลักไม่ใช่การหาเส้นทางที่สั้นที่สุด แต่เป็นการตรวจจับว่ากราฟนั้นมีวงจรลบหรือไม่ สามารถใช้อัลกอริธึมหาเส้นทางที่สั้นที่สุดบางอย่างเพื่อจุดประสงค์นี้ได้:

• อัลกอริทึม เบลล์แมน-ฟอร์ดสามารถใช้ตรวจจับวัฏจักรลบในเวลาได้${\displaystyle O(|V||E|)}$
• Cherkassky และ Goldberg ^{[ 23 ]}สำรวจอัลกอริธึมอื่นๆ อีกหลายรายการสำหรับการตรวจจับวงจรเชิงลบ

ปัญหาหลายอย่างสามารถกำหนดกรอบได้ในรูปแบบของเส้นทางที่สั้นที่สุดสำหรับแนวคิดการบวกตามเส้นทางและการหาค่าต่ำสุดที่เหมาะสม แนวทางทั่วไปสำหรับสิ่งเหล่านี้คือการพิจารณาการดำเนินการทั้งสองเป็นการดำเนินการของเซมิริงการคูณเซมิริงจะทำตามเส้นทาง และการบวกจะทำระหว่างเส้นทาง กรอบงานทั่วไปนี้เรียกว่าปัญหาเส้นทางพีชคณิต^{[ 24 ] [ 25 ] [ 26 ]}

อัลกอริทึมเส้นทางที่สั้นที่สุดแบบคลาสสิกส่วนใหญ่ (และแบบใหม่) สามารถกำหนดได้โดยการแก้ระบบเชิงเส้นบนโครงสร้างพีชคณิตดังกล่าว^{[ 27 ]}

เมื่อไม่นานมานี้ ได้มีการพัฒนากรอบการทำงานทั่วไปมากขึ้นสำหรับการแก้ปัญหาเหล่านี้ (และปัญหาที่เกี่ยวข้องน้อยกว่าอย่างเห็นได้ชัด) ภายใต้ชื่อ พีชคณิต การประเมินค่า^{[ 28 ]}

ในชีวิตจริง เครือข่ายการขนส่งมักจะเป็นแบบสุ่มและขึ้นอยู่กับเวลา ระยะเวลาในการเดินทางบนเส้นทางถนนขึ้นอยู่กับหลายปัจจัย เช่น ปริมาณการจราจร (เมทริกซ์ต้นทาง-ปลายทาง) งานก่อสร้างถนน สภาพอากาศ อุบัติเหตุ และการเสียของยานพาหนะ แบบจำลองเครือข่ายถนนที่สมจริงยิ่งขึ้นคือเครือข่ายแบบสุ่มที่ขึ้นอยู่กับเวลา (STD) ^{[ 29 ] [ 30 ]}

ไม่มีคำจำกัดความที่ยอมรับกันโดยทั่วไปสำหรับเส้นทางที่เหมาะสมที่สุดภายใต้ความไม่แน่นอน (กล่าวคือ ในเครือข่ายถนนแบบสุ่ม) นี่เป็นหัวข้อที่ถกเถียงกันอย่างมาก แม้ว่าจะมีความก้าวหน้าอย่างมากในช่วงทศวรรษที่ผ่านมาก็ตาม คำจำกัดความที่ใช้กันทั่วไปอย่างหนึ่งคือ เส้นทางที่มีเวลาเดินทางโดยเฉลี่ยต่ำที่สุด ข้อดีหลักของแนวทางนี้คือ สามารถใช้ประโยชน์จากอัลกอริธึมหาเส้นทางที่สั้นที่สุดที่มีประสิทธิภาพสำหรับเครือข่ายแบบกำหนดได้ อย่างไรก็ตาม เส้นทางที่เหมาะสมที่สุดที่ได้อาจไม่น่าเชื่อถือ เนื่องจากแนวทางนี้ไม่สามารถจัดการกับความแปรปรวนของเวลาเดินทางได้

เพื่อแก้ไขปัญหานี้ นักวิจัยบางคนใช้การกระจายระยะเวลาการเดินทางแทนค่าที่คาดหวัง ดังนั้น พวกเขาจึงค้นหาการกระจายความน่าจะเป็นของระยะเวลาการเดินทางทั้งหมดโดยใช้วิธีการเพิ่มประสิทธิภาพที่แตกต่างกัน เช่น การ เขียนโปรแกรมแบบไดนามิกและอัลกอริทึมของ Dijkstra ^{[ 31 ]}วิธีการเหล่านี้ใช้การเพิ่มประสิทธิภาพแบบสุ่มโดยเฉพาะอย่างยิ่งการเขียนโปรแกรมแบบไดนามิกแบบสุ่ม เพื่อค้นหาเส้นทางที่สั้นที่สุดในเครือข่ายที่มีความยาวส่วนโค้งแบบความน่าจะเป็น^{[ 32 ]}คำว่าความน่าเชื่อถือของเวลาเดินทางและความแปรปรวนของเวลาเดินทางถูกใช้เป็นคำตรงข้ามในวรรณกรรมวิจัยด้านการขนส่ง: ยิ่งความแปรปรวนสูง ความน่าเชื่อถือของการคาดการณ์ก็จะยิ่งต่ำลง

เพื่อพิจารณาถึงความแปรปรวน นักวิจัยได้เสนอคำจำกัดความทางเลือกสองแบบสำหรับเส้นทางที่เหมาะสมที่สุดภายใต้ความไม่แน่นอนเส้นทางที่น่าเชื่อถือที่สุดคือเส้นทางที่เพิ่มความน่าจะเป็นที่จะถึงที่หมายตรงเวลาให้มากที่สุด โดยคำนึงถึงงบประมาณเวลาในการเดินทางเส้นทางที่น่าเชื่อถือระดับ αคือเส้นทางที่ลดงบประมาณเวลาในการเดินทางที่จำเป็นเพื่อให้ถึงที่หมายตรงเวลาด้วยความน่าจะเป็นที่กำหนด

• การค้นหาแบบสองทิศทาง – อัลกอริทึมที่ค้นหาเส้นทางที่สั้นที่สุดระหว่างจุดสองจุดบนกราฟแบบมีทิศทาง
• เส้นทางที่สั้นที่สุดในเรขาคณิตยุคลิด  – ปัญหาการคำนวณเส้นทางที่สั้นที่สุดรอบสิ่งกีดขวางทางเรขาคณิต
• เครือข่ายการไหล  – กราฟแบบมีทิศทางซึ่งเส้นเชื่อมมีความจุ
• การหาเส้นทางที่สั้นที่สุด K เส้นทาง  – ปัญหาการคำนวณในทฤษฎีกราฟ
• การคูณเมทริกซ์แบบ Min-plus  – การดำเนินการทางคณิตศาสตร์บนเมทริกซ์
• การค้นหาเส้นทาง  – การวางแผนเส้นทางโดยใช้โปรแกรมคอมพิวเตอร์
• การเชื่อมต่อเส้นทางที่สั้นที่สุด
• ต้นไม้เส้นทางที่สั้นที่สุด  – ประเภทหนึ่งของต้นไม้แผ่ขยายPages displaying short descriptions of redirect targets
• TRILL (การเชื่อมต่อที่โปร่งใสของลิงก์จำนวนมาก)

• Altıntaş, Gökhan (2020). วิธีแก้ปัญหาเส้นทางที่สั้นที่สุดอย่างแม่นยำโดยอาศัยการเปรียบเทียบเชิงกล: ในส่วนที่เกี่ยวข้องกับเขาวงกต Amazon Digital Services LLC. ISBN 9798655831896.
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "ปัญหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวที่มีเอาต์พุตจำกัดแบบไดนามิกอย่างสมบูรณ์" Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms . Atlanta, GA. pp.  212– 221. CiteSeerX  10.1.1.32.9856 .
• Dreyfus, SE (ตุลาคม 1967). การประเมินอัลกอริทึมหาเส้นทางที่สั้นที่สุดบางส่วน(PDF) (รายงาน). โครงการ Rand. กองทัพอากาศสหรัฐอเมริกา. RM-5433-PR. เก็บถาวร(PDF)จากต้นฉบับเมื่อวันที่ 17 พฤศจิกายน 2015.DTIC AD-661265