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

ปัญหาวิถียาวสุด  เป็นหนึ่งในปัญหาทางคณิตศาสตร์ในเรื่องทฤษฎีกราฟ ซึ่งมีไว้สำหรับค้นหาวิถีเชิงเดียว (Simple path) ที่มีระยะทางมากที่สุดนับจากปมเริ่มต้นไปยังปมปลายทางบนกราฟถ่วงน้ำหนัก (Weighted graph) ลักษณะของปัญหาวิถียาวสุดจะคล้ายคลึงกันกับปัญหาวิถีสั้นสุด (Shortest path problem) ซึ่งเป็นการหาวิถีเชิงเดียวบนกราฟที่มีระยะทางสั้นที่สุดแทน เราสามารถหาวิถีสั้นสุดบนกราฟใดๆได้ในเวลาที่เป็นฟังก์ชันพหุนาม (Polynomial time) นั่นหมายถึงปัญหาวิถีสั้นสุดที่ลักษณะของปัญหาเป็นแบบปัญหาการตัดสินใจนั้นจัดอยู่ในกลุ่มความซับซ้อนแบบพี แต่ในทางกลับกัน ปัญหาวิถียาวสุดนั้นกลับยังไม่มีขั้นตอนวิธีใดที่ทำงานได้อย่างถูกต้องในเวลาที่เป็นฟังก์ชันพหุนาม กล่าวคือเป็นปัญหาที่อยู่ในกลุ่มเอ็นพี และได้รับการพิสูจน์แล้วว่าปัญหาวิถียาวสุดนั้นเกิดจากการลดรูปมาจากปัญหาวิถีฮัลมินตัน (Hamiltonian path problem) ซึ่งอยู่ในกลุ่มเอ็นพีบริบูรณ์ ทำให้ปัญหานี้อยู่ในกลุ่มเอ็นพีบริบูรณ์เช่นเดียวกัน 
รายละเอียด.
วิถีเชิงเดียวจากปม A ไปยังปม B ของกราฟใดๆหมายถึง เซตของวิถีทุกรูปแบบที่เริ่มต้นจากจุด A และไปสิ้นสุดยังจุด B โดยไม่มีการผ่านปมซ้ำ ในกรณีที่กราฟนั้นเป็นกราฟถ่วงน้ำหนัก กล่าวคือมีตัวเลขกำกับประจำทุกๆเส้นเชื่อมก็จะได้ว่า วิถีเชิงเดียวยาวสุดจากปม A ไปยังปม B ก็คือเซตของวิถีทุกรูปแบบที่มีน้ำหนักรวมของเส้นเชื่อมทุกเส้นบนวิถีมากที่สุด ดังนั้น ปัญหาวิถียาวสุดจึงเป็นปัญหาประเภท Optimization Problem คือแก้ปัญหาโดยการหาผลลัพธ์ที่ดีที่สุดที่เป็นไปได้นั่นเอง
อย่างไรก็ตามปัญหาวิถียาวสุดสามารถปรับให้เปนปัญหาการตัดสินใจได้โดยการกำหนดตัวเลข k ขึ้นมาตัวหนึ่งแล้วถามปัญหาว่า ในกราฟนี้มีวิถียาวสุดที่ยาวไม่น้อยกว่า k หรือไม่ จากการพิสูจน์ว่าปัญหาวิถียาวสุดเป็นปัญหาในกลุ่มเอ็นพีบริบูรณ์ดังนั้นจึงหมายความว่าปัญหานี้สามารถหาคำตอบโดยใช้ฟังก์ชันเชิงไม่กำหนด (Non-deterministic function) หรือสามารถตรวจคำตอบใช่ได้ในเวลาที่เป็นฟังก์ชันพหุนามนั่นเอง โดยการตรวจคำตอบใช่นั้นทำได้โดยการส่งหลักฐาน (Certificate) C เข้าไปในฟังก์ชันโดย C เป็นวิถีหนึ่งในกราฟซึ่งมีวิถียาวสุดยาวกว่าหรือเท่ากับ k ก็จะทำให้ฟังก์ชันตรวจคำตอบทำงานได้ในเวลาที่เป็นฟังก์ชันพหุนาม 
ขั้นตอนวิธี.
สำหรับกราฟอวัฏจักรระบุทิศทาง.
กราฟอวัฏจักรระบุทิศทาง (Directed acyclic graph หรืออักษรย่อว่า DAG) เป็นกราฟระบุทิศทาง ที่ไม่มีวัฏจักรแบบระบุทิศทางใดๆในกราฟ 
ขั้นตอนวิธีสำหรับแก้ปัญหาวิถียาวสุดบนกราฟอวัฏจักรระบุทิศทาง อาจใช้การปรับเปลี่ยนมาจากปัญหาวิถีสั้นสุด โดยสร้างกราฟใหม่ขึ้นมา (G’) โดยให้กราฟใหม่นี้มีปมและเส้นเชื่อมเหมือนกราฟเดิมทุกประการ แต่น้ำหนักของเส้นเชื่อมให้เปลี่ยนเป็นค่าติดลบของค่าเดิม แล้วนำกราฟใหม่นี้มาแก้ปัญหาแบบวิถีสั้นสุด ก็จะได้ว่าวิถีสั้นสุดของกราฟใหม่ ก็จะกลายเป็นวิถียาวสุดของกราฟเดิมนั่นเอง
 int LogestPathDAG(Graph G, Vertex Start, Vertex End){
 construct Graph G’ 
 : G’.V = G.V
 : G’.E = G.E
 : G’.w = -G.w
 return shortestPathDAG(G’, Start, End);
ขั้นตอนวิธีดังกล่าวก็จะมีเวลาในการทำงานเท่ากับ
จึงได้เวลาในการทำงานรวม (กรณีใช้ขั้นตอนวิธีของไดค์สตรา) เป็น O(|G.E| log(|G.V|))
อย่างไรก็ตาม การแก้ปัญหาวิถียาวสุดบนกราฟอวัฎจักรระบุทิศทางนั้น มีอัลกอรีทึมที่สามารถทำงานได้เร็วกว่าขั้นตอนวิธีข้างต้น นั่นคือใช้กำหนดการพลวัต (Dynamic programming) ซึ่งมีขั้นตอนดังนี้
 int LongestPathDAG(Graph G, Vertex Start, Vertex End){
 topologicalSorting(G);
 int distance[|G.V|] arrage by sorted G;
 for each vertex u in topOrder of G.V
 for each edge e in G.E point from u to v
 if (distance(v) < distance(u) + weight(e))
 distance(v) = distance(u) + weight(e);
 return max value element in distance
ประสิทธิภาพในการทำงานขอขั้นตอนวิธีนี้เกิดจาก
รวมเป็นเวลาในการทำงานทั้งหมด O(|G.V| + |G.E|)