Johnson ( graph G ) { //สร้างกราฟ K ใหม่เพิ่มปมพิเศษ q และเพิ่มเส้นเชื่อมจากปม q ไปปมอื่นทุกปมให้น้ำหนักเป็น 0 create graph K : K.V = G.V add {q} //V คือ จุดปม : K.E = G.E add {(q,i) | i in G.V} //E คือ เส้นเชื่อม : K.W = G.W , K.W(q,i) = 0 | i in G.V //W คือ ระยะระหว่างปมสองปม BellmanFord(K,q) //ถ้ามีวงจรติดลบจะหยุด for each edge (i,j)in G.E G.W(i,j) += h[i]-h[j] for each vertex i in G.V { d=dijkstra(G,i) //d คือ array ของทุกจุดในกราฟแต่ละจุดเก็บระยะสั้นสุดจากจุด i for each vertex j in G.V L(i,j)=d[j]-(h[i]-h[j]) //L คือ ระยะทางสั้นสุด } return L }
นตอนว, ของจอห, นส, บทความน, อาจต, องการตรวจสอบต, นฉบ, ในด, านไวยากรณ, ปแบบการเข, ยน, การเร, ยบเร, ยง, ณภาพ, หร, อการสะกด, ณสามารถช, วยพ, ฒนาบทความได, เป, นข, นตอนว, ทำการปร, บกราฟไม, ให, ำหน, กต, ดลบเพ, อให, สามารถใช, นตอนว, ของไดค, สตราได, ในการหาเส, นทางส, น. bthkhwamnixactxngkartrwcsxbtnchbb indaniwyakrn rupaebbkarekhiyn kareriyberiyng khunphaph hruxkarsakd khunsamarthchwyphthnabthkhwamidkhntxnwithikhxngcxhnsn epnkhntxnwithithithakarprbkrafimihminahnktidlbephuxihsamarthichkhntxnwithikhxngidkhstraidinkarhaesnthangsnthisudrahwangthukkhucudhruxpm sungepnkhntxnwithithiehmaainkarichkbkrafrabuthisthangthimiesnechuxmnxyephraathaesnechuxmeyxacachakwa khntxnwithikhxngflxyd wxraechl aettxngimmiwngrxbthinahnktidlbxyudwy phukhidkhnwithikarnikhux odnld bi cxhnsn Donald B Johnson sungephyaephrepnkhrngaerkemux kh s 1977 enuxha 1 karxthibaykhntxnwithi 2 twxyang 3 rhsethiym 4 khwamthuktxng 5 prasiththiphaphechingewla 6 ephimetim 7 xangxingkarxthibaykhntxnwithi aekikhkhntxnwithikhxngcxhnsnprakxbdwykhntxntxipni srangcudhruxpm ihmkhunhnungcudlnginkraf aelasrangesnechuxmcakcudihmthiephimmaipyngcudxunthukcud odykahndnahnkthnghmdepn 0 ichkhntxnwithikhxngebllaemn fxrdcakcudihm hanahnknxythisudcakcudihmipyngthukcudaetlacudkekbkhaiw thatrwcphbwngcr thiminahnktidlb ihhyudkarthangan aeplngkrafdngedimimihminahnktidlb odyichkhathiekbiwinkhxngaetlacudthikhanwnidcakkhntxnwithikhxngebllaemn fxrd klawkhux esnechuxmcakcud k ipyngcud kh edimminahnkepn nahnkesnechuxm k kh epliynkhanahnkihmkhxngesnechuxmesnnnepn nahnkesnechuxm k kh khathiekbiwin k khathiiekbiwin kh sudthayichkhntxnwithikhxngidkhstra ephuxhaesnthangsnthisudcakcudidcudtnthanghnung ipyngcudxuninkrafthiaeplngnahnkaelwidtwxyang aekikh erimcaktxnaerkidkhxmulkhxngkrafesnechuxmthiminahnktidlb caknnthakarephimcudihm q thimiesnechuxmnahnkepn 0 chiipyngthukcudthimikxnintxnaerk aelwcungichkhntxnwithikhxngebllaemn fxrdodyich q epncuderimtn caidkha h v thithisnthisudcak q ipyngcud v caknnthakarepliynnahnkkhxngesnechuxmaetlaesn w u v ihepnbwkthukesnepn w u v h u h v hlngcakidkrafthithakaraeplngnahnkaelwksamarthichkhntxnwithikhxngidkhstrahawithisnsudidrhsethiym aekikhJohnson graph G srangkraf K ihmephimpmphiess q aelaephimesnechuxmcakpm q ippmxunthukpmihnahnkepn 0 create graph K K V G V add q V khux cudpm K E G E add q i i in G V E khux esnechuxm K W G W K W q i 0 i in G V W khux rayarahwangpmsxngpm BellmanFord K q thamiwngcrtidlbcahyud for each edge i j in G E G W i j h i h j for each vertex i in G V d dijkstra G i d khux array khxngthukcudinkrafaetlacudekbrayasnsudcakcud i for each vertex j in G V L i j d j h i h j L khux rayathangsnsud return L khwamthuktxng aekikhemuxphicarnawithicakpm k thung kh aemaetlawithicaphanpmtangknaetkhwamyawthiephimkhuncaethaknesmx khwamyawihm k c ch kh khwamyawedim k c ch kh kharayathangthiekbiwkhxng k kharayathangthiekbiwkhxng kh khwamyawihm k ch kh khwamyawedim k ch kh kharayathangthiekbiwkhxng k kharayathangthiekbiwkhxng kh dd dngnnwithisnsudcaepnwithiedim khwamyawkhxngwngcrinkrafkimepliyn khwamyawihm k c ch k khwamyawedim k c ch k kharayathangthiekbiwkhxng k kharayathangthiekbiwkhxng k dd prasiththiphaphechingewla aekikhv khux canwnpm e khux canwnesnechuxm tha khntxnwithikhxngidkhstra ich binary heap cathaih Johnson ichewla O v e l o g v displaystyle O velogv sungemuxichkb krafthimiesnechuxmnxy caerwkwaich khntxnwithikhxngflxyd wxraechl thiich O v3 ephimetim aekikhULearn karxxkaebbxlkxrithum smchay prasiththicutrakul widioxprakxbkhaxthibay khntxnwithikhxngidkhstra epnkhntxnwithithiichinkarharayathangesnthangsnsudkhxngkhupmid sahrbkrafthimikhwamyawkhxngesnechuxmimepnlb khntxnwithikhxngeblaemn fxrd epnkhntxnthiichinkarkhanwnhawithithisnsudaebbaehlngtnthangediywinkrafthimikarthwngnahnkkhxngesnechuxmepnbwk hruxnahnkkhxngesnechuxmepnlb khntxnwithikhxngflxyd wxraechl epnkhntxnwithikarwiekhraahkrafephuxthicaharayathangkhxngesnthangsnsudinkrafthiminahnkkhxngesnechuxmepnbwk hrux nahnkkhxngesnechuxmepnlb aetimsamarthhaidthamiwngcrlbxangxing aekikhBlack Paul E Johnson s Algorithm Dictionary of Algorithms and Data National Institute of Standards and Technology Suurballe J W 1974 Disjoint paths in a network Networks 14 125 145 doi 10 1002 net 3230040204 karxxkaebbaelawiekhraahxlkxrithum smchay prasiththicutrakulekhathungcak https th wikipedia org w index php title khntxnwithikhxngcxhnsn amp oldid 5882289, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
