ปัญหาวิถีสั้นสุด

thumb|วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1)
ในทฤษฎีกราฟ **ปัญหาวิถีสั้นสุด** ()​ เป็นปัญหาที่ต้องการหา**[[วิถี (ทฤษฎีกราฟ)|วิถี]]สั้นสุด**ระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่าง ๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น ๆ

## นิยาม

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

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

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

## ขั้นตอนวิธี
ขั้นตอนวิธีในการแก้ปัญหาวิถีสั้นสุด จะใช้แนวคิดของการ **การคลายเส้นเชื่อม** (relaxation) นั่นคือขณะเริ่มต้น คำตอบวิถีสั้นสุดจะยังไม่ถูกต้อง เส้นเชื่อม *e* จะเรียกว่า **ตึง** (tense) ถ้าสามารถใช้ *e* แล้วทำให้มีวิถีที่น้ำหนักรวมร้อยกว่าคำตอบที่มีอยู่ ดังนั้นขั้นตอนวิธีแก้ปัญหาวิถีสั้นสุดก็จะทำการคลายเส้นเชื่อมที่ตึง นั่นคือใช้เส้นเชื่อมที่ตึงเพื่อให้ได้คำตอบของวิถีสั้นสุดที่ดียิ่งขึ้นเรื่อย ๆ สุดท้ายเมื่อไม่พบเส้นเชื่อมที่ตึงก็แปลว่าวิถีที่ได้เป็นวิถีสั้นสุดแล้ว

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

สำหรับกราฟไม่ถ่วงน้ำหนัก จากนิยามที่กำหนดให้วิถีสั้นสุดคือมีจำนวนเส้นเชื่อมในวิถีน้อยที่สุด ดังนั้น จึงอาจกล่าวได้ว่าเส้นเชื่อมทุกเส้นมีความสำคัญเท่ากัน กล่าวคือกราฟไม่ถ่วงน้ำหนักจะเทียบเท่ากับกราฟถ่วงน้ำหนักที่เส้นเชื่อมทุกเส้นมีน้ำหนักเท่ากันและไม่เป็นลบ ตัวอย่างเช่น **กราฟถ่วงน้ำหนักหนึ่งหน่วย** (unit-weight graph) เป็นต้น

ขั้นตอนวิธีในการแก้ปัญหาที่ได้รับความนิยมและสำคัญมีดังนี้

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

### ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว
ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวเป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอด *v* ไปจุดยอดอื่น ๆ ทั้งหมดในกราฟ ได้ต้นไม้วิถีสั้นสุดออกมาเป็นผลลัพธ์

#### กราฟถ่วงน้ำหนักหนึ่งหน่วย
* ทำการค้นตามแนวกว้าง ใช้เวลา *O*(*V* + *E*)

#### [[กราฟอวัฏจักรระบุทิศทาง]]สำหรับเส้นเชื่อมน้ำหนักใด ๆ
* ทำการเรียงเชิงทอพอโลยีและกำหนดการพลวัต ใช้เวลา *O*(*V* + *E*)

#### กราฟที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ

#### [[กราฟเชิงระนาบ]]ที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ

#### กราฟสำหรับเส้นเชื่อมน้ำหนักใด ๆ
* ขั้นตอนวิธีของเบลแมน-ฟอร์ด

#### [[กราฟเชิงระนาบ]]สำหรับเส้นเชื่อมน้ำหนักใด ๆ

### ปัญหาวิถีสั้นสุดแบบทุกคู่
#### กราฟสำหรับเส้นเชื่อมน้ำหนักใด ๆ
* ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้เวลา *O*(*V*3) เหมาะสำหรับกราฟหนาแน่นและนำมาใช้งานได้ง่ายมาก
* ขั้นตอนวิธีของจอห์นสัน ใช้เวลา *O*(*V*2log *V* + *VE*) เหมาะสำหรับกราฟไม่หนาแน่นซึ่งเวลาการทำงานจะดีกว่าการใช้ขั้นตอนวิธีของฟลอยด์-วอร์แชลเป็นอย่างมาก

## การนำไปใช้งาน

## ปัญหาที่เกี่ยวข้อง
* ปัญหาวิถีสั้นสุดบนระนาบแบบยุคลิด

## การมองด้วยกำหนดการเชิงเส้น

## เนื้อหาที่เกี่ยวข้อง
* การไหลในเครือข่าย
* ต้นไม้วิถีสั้นสุด
* ปัญหาวิถีสั้นสุดบนระนาบแบบยุคลิด
* การค้นแบบสองทิศทาง ขั้นตอนวิธีหาวิถีสั้นสุดแบบคู่เดียว

## อ้างอิง
### หมายเหตุ

### บรรณานุกรม

*
* 
*
* 
*
* 
* 
* 
* 
* 
*
*
* 
*
*
*
*
* 
* 
*
*
*  Attributes Dijkstra's algorithm to Minty ("private communication") on p.&nbsp;225.
*  Here: vol.A, sect.7.5b, p.&nbsp;103
* 
* 
*
*
*
*

## อ่านเพิ่ม
* 
*  DTIC AD-661265.

หมวดหมู่:ปัญหาฟังก์ชันพหุนาม
หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:ทฤษฎีเครือข่าย
หมวดหมู่:ปัญหาการคำนวณในทฤษฎีกราฟ