เมนูนำทาง
ปัญหาวิถีสั้นสุด ขั้นตอนวิธีขั้นตอนวิธีในการแก้ปัญหาวิถีสั้นสุด จะใช้แนวคิดของการการคลายเส้นเชื่อม (relaxation) นั่นคือขณะเริ่มต้น คำตอบวิถีสั้นสุดจะยังไม่ถูกต้อง เส้นเชื่อม e จะเรียกว่า ตึง (tense) ถ้าสามารถใช้ e แล้วทำให้มีวิถีที่น้ำหนักรวมร้อยกว่าคำตอบที่มีอยู่ ดังนั้นขั้นตอนวิธีแก้ปัญหาวิถีสั้นสุดก็จะทำการคลายเส้นเชื่อมที่ตึง นั่นคือใช้เส้นเชื่อมที่ตึงเพื่อให้ได้คำตอบของวิถีสั้นสุดที่ดียิ่งขึ้นเรื่อยๆ สุดท้ายเมื่อไม่พบเส้นเชื่อมที่ตึงก็แปลว่าวิถีที่ได้เป็นวิถีสั้นสุดแล้ว[2]
ปัญหาวิถีสั้นสุดมองแต่เพียงการไปถึงได้ของจุดยอดต่างๆเท่านั้น ดังนั้นสำหรับกราฟไม่ระบุทิศทางจึงสามารถแปลงเป็นกราฟระบุทิศทางได้ โดยการเปลี่ยนเส้นเชื่อมไม่มีทิศทาง เป็นเส้นเชื่อมมีทิศทาง 2 เส้นที่มีทิศทั้งไปและกลับ
สำหรับกราฟไม่ถ่วงน้ำหนัก จากนิยามที่กำหนดให้วิถีสั้นสุดคือมีจำนวนเส้นเชื่อมในวิถีน้อยที่สุด ดังนั้นจึงอาจกล่าวได้ว่าเส้นเชื่อมทุกเส้นมีความสำคัญเท่ากัน กล่าวคือกราฟไม่ถ่วงน้ำหนักจะเทียบเท่ากับกราฟถ่วงน้ำหนักที่เส้นเชื่อมทุกเส้นมีน้ำหนักเท่ากันและไม่เป็นลบ ตัวอย่างเช่นกราฟถ่วงน้ำหนักหนึ่งหน่วย (unit-weight graph) เป็นต้น[2]
ขั้นตอนวิธีในการแก้ปัญหาที่ได้รับความนิยมและสำคัญมีดังนี้
ขั้นตอนวิธีอื่นๆและการนำมาใช้งานในรูปแบบต่างๆอาจหาได้ที่ Cherkassky et al[3]
ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวเป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอด v ไปจุดยอดอื่นๆทั้งหมดในกราฟ ได้ต้นไม้วิถีสั้นสุดออกมาเป็นผลลัพธ์
ขั้นตอนวิธี | ความซับซ้อนทางด้านเวลา | ผู้คิดค้น |
---|---|---|
O(V4) | Shimbel 1955 | |
O(V2EL) | Ford 1956 | |
ขั้นตอนวิธีของเบลแมน-ฟอร์ด | O(VE) | Bellman 1958, Moore 1959 |
O(V2 log V) | Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960 | |
ขั้นตอนวิธีของไดค์สตรา | O(V2) | Leyzorek et al. 1957, Dijkstra 1959 |
... | ... | ... |
ขั้นตอนวิธีของไดค์สตราพร้อมใช้ฮีปฟีโบนัชชี | O(E + V log V) | Fredman & Tarjan 1984, Fredman & Tarjan 1987 |
O(E log log L) | Johnson 1982, Karlsson & Poblete 1983 | |
Gabow's algorithm | O(V logE/V L) | Gabow 1983b, Gabow 1985b |
O(E + V√log L) | Ahuja et al. 1990 |
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
เมนูนำทาง
ปัญหาวิถีสั้นสุด ขั้นตอนวิธีใกล้เคียง
ปัญหา ปัญหาสิ่งแวดล้อมในประเทศไทย ปัญหาวิถีสั้นสุด ปัญหาราชวงศ์ ปัญหาปี ค.ศ. 2000 ปัญหาการแต่งงานที่มีเสถียรภาพ ปัญหาสิ่งแวดล้อมในประเทศอัฟกานิสถาน ปัญหาสกันทอร์ป ปัญหาวันเกิด ปัญหารางวัลมิลเลนเนียมแหล่งที่มา
WikiPedia: ปัญหาวิถีสั้นสุด http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/d... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=1... http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/... http://xlinux.nist.gov/dads/HTML/dagShortPath.html http://portal.acm.org/citation.cfm?id=28874 //www.ams.org/mathscinet-getitem?mr=1392160 http://www.boost.org/libs/graph/doc/graph_theory_r... http://www.computer.org/portal/web/csdl/doi/10.110... //doi.org/10.1007%2FBF01386390 //doi.org/10.1016%2F0025-5610(95)00021-6