วิถีเชิงเดียวจากปม A ไปยังปม B ของกราฟใดๆหมายถึง เซตของวิถีทุกรูปแบบที่เริ่มต้นจากจุด A และไปสิ้นสุดยังจุด B โดยไม่มีการผ่านปมซ้ำ ในกรณีที่กราฟนั้นเป็นกราฟถ่วงน้ำหนัก กล่าวคือมีตัวเลขกำกับประจำทุกๆเส้นเชื่อมก็จะได้ว่า วิถีเชิงเดียวยาวสุดจากปม A ไปยังปม B ก็คือเซตของวิถีทุกรูปแบบที่มีน้ำหนักรวมของเส้นเชื่อมทุกเส้นบนวิถีมากที่สุด ดังนั้น ปัญหาวิถียาวสุดจึงเป็นปัญหาประเภท Optimization Problem คือแก้ปัญหาโดยการหาผลลัพธ์ที่ดีที่สุดที่เป็นไปได้นั่นเอง อย่างไรก็ตามปัญหาวิถียาวสุดสามารถปรับให้เปนปัญหาการตัดสินใจได้โดยการกำหนดตัวเลข k ขึ้นมาตัวหนึ่งแล้วถามปัญหาว่า ในกราฟนี้มีวิถียาวสุดที่ยาวไม่น้อยกว่า k หรือไม่ จากการพิสูจน์ว่าปัญหาวิถียาวสุดเป็นปัญหาในกลุ่มเอ็นพีบริบูรณ์ดังนั้นจึงหมายความว่าปัญหานี้สามารถหาคำตอบโดยใช้ฟังก์ชันเชิงไม่กำหนด (Non-deterministic function) หรือสามารถตรวจคำตอบใช่ได้ในเวลาที่เป็นฟังก์ชันพหุนามนั่นเอง โดยการตรวจคำตอบใช่นั้นทำได้โดยการส่งหลักฐาน (Certificate) C เข้าไปในฟังก์ชันโดย C เป็นวิถีหนึ่งในกราฟซึ่งมีวิถียาวสุดยาวกว่าหรือเท่ากับ k ก็จะทำให้ฟังก์ชันตรวจคำตอบทำงานได้ในเวลาที่เป็นฟังก์ชันพหุนาม
ขั้นตอนวิธี
ข้อมูลนำเข้า กราฟ G, ปมเริ่มต้น a "เป็นสมาชิกของ" G.V, ปมปลายทาง b "เป็นสมาชิกของ" G.V
ข้อมูลส่งออก ระยะทางของวิถีที่ยาวที่สุดจากปม a ไปยังปม b บนกราฟ G
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 }
Ioannidou, Kyriaki, Longest path problem on Interval Graphs(PDF)
Takahara, Yoshihiro, Longest path problem on Ptolemaic Graphs
Uehara, Ryuhei, Longest path problem on Small Graph Classes
Longest path problem on Cocomparability Graphs
แหล่งข้อมูลอื่น
NP-Completeness
Source of the algorithm
"Find the Longest Path", by Daniel J. Barrett
Efficient Algorithms for the Longest Path Problem by Ryuhei UEHARA (JAIST), Yushi UNO (Osaka Prefecture University)[ลิงก์เสีย]
On the relation between the travelling-salesman and the longest path problems by William W. Hardgrave and George L. Nemhauser
ธันวาคม 17, 2021
ญหาว, ยาวส, บทความน, องการการจ, ดหน, ดหมวดหม, ใส, งก, ภายใน, หร, อเก, บกวาดเน, อหา, ให, ณภาพด, ณสามารถปร, บปร, งแก, ไขบทความน, ได, และนำป, ายออก, จารณาใช, ายข, อความอ, นเพ, อช, ดข, อบกพร, อง, งกฤษ, longest, path, problem, เป, นหน, งในป, ญหาทางคณ, ตศาสตร, ในเร,. bthkhwamnitxngkarkarcdhna cdhmwdhmu islingkphayin hruxekbkwadenuxha ihmikhunphaphdikhun khunsamarthprbprungaekikhbthkhwamniid aelanapayxxk phicarnaichpaykhxkhwamxunephuxchichdkhxbkphrxngpyhawithiyawsud xngkvs Longest path problem epnhnunginpyhathangkhnitsastrineruxngthvsdikraf sungmiiwsahrbkhnhawithiechingediyw Simple path thimirayathangmakthisudnbcakpmerimtnipyngpmplaythangbnkrafthwngnahnk Weighted graph lksnakhxngpyhawithiyawsudcakhlaykhlungknkbpyhawithisnsud Shortest path problem sungepnkarhawithiechingediywbnkrafthimirayathangsnthisudaethn erasamarthhawithisnsudbnkrafididinewlathiepnfngkchnphhunam Polynomial time nnhmaythungpyhawithisnsudthilksnakhxngpyhaepnaebbpyhakartdsinicnncdxyuinklumkhwamsbsxnaebbphi aetinthangklbkn pyhawithiyawsudnnklbyngimmikhntxnwithiidthithanganidxyangthuktxnginewlathiepnfngkchnphhunam klawkhuxepnpyhathixyuinklumexnphi aelaidrbkarphisucnaelwwapyhawithiyawsudnnekidcakkarldrupmacakpyhawithihlmintn Hamiltonian path problem sungxyuinklumexnphibriburn 1 thaihpyhanixyuinklumexnphibriburnechnediywkn enuxha 1 raylaexiyd 2 khntxnwithi 2 1 sahrbkrafxwtckrrabuthisthang 2 2 sahrbkrafxun 3 khntxnwithixunthiekiywkhxng 4 pyhathiekiywkhxng 5 xangxing 6 aehlngkhxmulxunraylaexiyd aekikhwithiechingediywcakpm A ipyngpm B khxngkrafidhmaythung estkhxngwithithukrupaebbthierimtncakcud A aelaipsinsudyngcud B odyimmikarphanpmsa inkrnithikrafnnepnkrafthwngnahnk klawkhuxmitwelkhkakbpracathukesnechuxmkcaidwa withiechingediywyawsudcakpm A ipyngpm B kkhuxestkhxngwithithukrupaebbthiminahnkrwmkhxngesnechuxmthukesnbnwithimakthisud dngnn pyhawithiyawsudcungepnpyhapraephth Optimization Problem khuxaekpyhaodykarhaphllphththidithisudthiepnipidnnexng xyangirktampyhawithiyawsudsamarthprbihepnpyhakartdsinicidodykarkahndtwelkh k khunmatwhnungaelwthampyhawa inkrafnimiwithiyawsudthiyawimnxykwa k hruxim cakkarphisucnwapyhawithiyawsudepnpyhainklumexnphibriburndngnncunghmaykhwamwapyhanisamarthhakhatxbodyichfngkchnechingimkahnd Non deterministic function hruxsamarthtrwckhatxbichidinewlathiepnfngkchnphhunamnnexng odykartrwckhatxbichnnthaidodykarsnghlkthan Certificate C ekhaipinfngkchnody C epnwithihnunginkrafsungmiwithiyawsudyawkwahruxethakb k kcathaihfngkchntrwckhatxbthanganidinewlathiepnfngkchnphhunamkhntxnwithi aekikhkhxmulnaekha kraf G pmerimtn a epnsmachikkhxng G V pmplaythang b epnsmachikkhxng G V khxmulsngxxk rayathangkhxngwithithiyawthisudcakpm a ipyngpm b bnkraf G sahrbkrafthisamathnamaichepnkhxmulnaekha nnsamarthepnkrafidkid odyhakepnkrafthwngnahnkthwip General Weighted Graph inpccubnyngimmiikhrkhnphbkhntxnwithithiichewlathiepnfngkchnphhunamid aetwasahrbkaraekpyhawithiyawsudthingaynn krafthirbmacaepnkrafxwtckrrabuthisthang dngthicaaesdngtxipnisahrbkrafxwtckrrabuthisthang aekikh withiyawsudbnkrafxwtckrrabuthisthangaebbthwngnahnk cakpm A ipyngpm G aethndwyluksrsiaedng krafxwtckrrabuthisthang Directed acyclic graph hruxxksryxwa DAG epnkrafrabuthisthang thiimmiwtckraebbrabuthisthangidinkraf khntxnwithisahrbaekpyhawithiyawsudbnkrafxwtckrrabuthisthang xacichkarprbepliynmacakpyhawithisnsud odysrangkrafihmkhunma G odyihkrafihmnimipmaelaesnechuxmehmuxnkrafedimthukprakar aetnahnkkhxngesnechuxmihepliynepnkhatidlbkhxngkhaedim aelwnakrafihmnimaaekpyhaaebbwithisnsud kcaidwawithisnsudkhxngkrafihm kcaklayepnwithiyawsudkhxngkrafedimnnexng 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 khntxnwithidngklawkcamiewlainkarthanganethakb ewlainkarsrangkrafihm epn O G E ewlainkaraekpyhawithisnsud khunkbkhntxnwithithiich echn khntxnwithikhxngidkhstra caichewlainkarthanganepn O G E log G V cungidewlainkarthanganrwm krniichkhntxnwithikhxngidkhstra epn O G E log G V xyangirktam karaekpyhawithiyawsudbnkrafxwdckrrabuthisthangnn mixlkxrithumthisamarththanganiderwkwakhntxnwithikhangtn nnkhuxichkahndkarphlwt Dynamic programming 2 sungmikhntxndngniint 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 lt distance u weight e distance v distance u weight e return max value element in distance prasiththiphaphinkarthangankhxkhntxnwithiniekidcak ewlainkareriyngladbaebbthxphxlxyi 3 epn O G V G E ewlainkartrwcsxbaelaepliynkhainxaery distance epn O G E ewlainkarhakhamaksudinxaery distance epn O G V rwmepnewlainkarthanganthnghmd O G V G E sahrbkrafxun aekikh khntxnwithisahrb Interval Graphs 4 khntxnwithisahrb Ptolemaic Graphs 5 khntxnwithisahrb Small Graph Classes 6 khntxnwithisahrb Cocomparability Graphs 7 khntxnwithixunthiekiywkhxng aekikhkareriyngladbaebbthxphxolyi Topological sorting khntxnwithikhxngidkhstra Dijkstra algorithm pyhathiekiywkhxng aekikhpyhawithisnsud Shortest path problem pyhawithihlmintn Hamiltonian path problem pyhakaredinthangkhxngphnkngankhay Travelling salesman problem xangxing aekikh A proof that longest path is NP complete Dynamic programming PDF Topological sorting khlngkhxmuleka ekbcak aehlngedim emux 2011 08 19 subkhnemux 2011 09 29 Ioannidou Kyriaki Longest path problem on Interval Graphs PDF Takahara Yoshihiro Longest path problem on Ptolemaic Graphs Uehara Ryuhei Longest path problem on Small Graph Classes Longest path problem on Cocomparability Graphsaehlngkhxmulxun aekikhNP Completeness Source of the algorithm Find the Longest Path by Daniel J Barrett Efficient Algorithms for the Longest Path Problem by Ryuhei UEHARA JAIST Yushi UNO Osaka Prefecture University lingkesiy On the relation between the travelling salesman and the longest path problems by William W Hardgrave and George L Nemhauser ekhathungcak https th wikipedia org w index php title pyhawithiyawsud amp oldid 9651038, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
