ວິທີການຊອກຫາ "ເສັ້ນທາງ" ຂອງທຸກຄູ່ເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດດ້ວຍ Floyd-Warshall Algorithm ໃນ C#

ແນະນຳ ໃນ , ພວກເຮົາໄດ້ເຫັນວິທີການແກ້ໄຂບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດຄູ່ທັງຫມົດໂດຍໃຊ້ . ພວກເຮົາຍັງໄດ້ຄົ້ນຫາຫຼາຍວິທີເພື່ອປັບປຸງປະສິດທິພາບຂອງສູດການຄິດໄລ່ໂດຍໃຊ້ຂະໜານ ແລະ vectorization. ບົດຂຽນທີ່ຜ່ານມາ Floyd-Warshall algorithm ຢ່າງໃດກໍຕາມ, ຖ້າທ່ານຄິດກ່ຽວກັບຜົນໄດ້ຮັບຂອງ Floyd-Warshall algorithm, ທ່ານຈະຮູ້ທັນທີທັນໃດທີ່ຫນ້າສົນໃຈ - ພວກເຮົາຮູ້ໄລຍະຫ່າງ (ຄ່າຂອງເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ) ລະຫວ່າງ vertexes ໃນກາຟແຕ່ພວກເຮົາບໍ່ຮູ້ວ່າ "ເສັ້ນທາງ" ຫມາຍຄວາມວ່າ, ພວກເຮົາບໍ່ຮູ້ວ່າສິ່ງທີ່ vertexes ປະກອບສ່ວນໃຫ້ແຕ່ລະເສັ້ນທາງສັ້ນທີ່ສຸດ, ແລະພວກເຮົາບໍ່ສາມາດສ້າງ "ເສັ້ນທາງ" ເຫຼົ່ານີ້ຄືນໃຫມ່ຈາກຜົນໄດ້ຮັບທີ່ພວກເຮົາມີ. ໃນບົດຂຽນນີ້, ຂ້າພະເຈົ້າຂໍເຊີນທ່ານເຂົ້າຮ່ວມກັບຂ້າພະເຈົ້າແລະຂະຫຍາຍລະບົບສູດການຄິດໄລ່ Floyd-Warshall. ເວລານີ້, ພວກເຮົາຈະເຮັດໃຫ້ແນ່ໃຈວ່າພວກເຮົາສາມາດຄິດໄລ່ໄລຍະທາງແລະສ້າງ "ເສັ້ນທາງ". ທິດສະດີທີ່ຮູ້ຈັກເລັກນ້ອຍ… ກ່ອນທີ່ຈະເຂົ້າໄປໃນລະຫັດແລະມາດຕະຖານ, ໃຫ້ພວກເຮົາທົບທວນຄືນທິດສະດີຂອງວິທີການເຮັດວຽກຂອງ Floyd-Warshall. ນີ້ແມ່ນຄໍາອະທິບາຍຂໍ້ຄວາມຂອງ algorithm: ພວກເຮົາເລີ່ມຕົ້ນໂດຍການເປັນຕົວແທນຂອງກາຟ ( ) ຂອງຂະຫນາດ ເປັນ matrix ( ) ຂອງຂະຫນາດ ທີ່ທຸກໆເຊນ ມີນ້ໍາຫນັກຂອງຂອບຈາກຈຸດສູງສຸດ ຫາ vertex (ເບິ່ງຮູບ 1). ໃນກໍລະນີທີ່ບໍ່ມີຂອບເຂດລະຫວ່າງ vertexes, ເຊລໄດ້ຖືກຕັ້ງຄ່າເປັນ ພິເສດ (ສະແດງໃຫ້ເຫັນເປັນຕາຕະລາງສີດໍາໃນຮູບພາບ 1). G N W N x N W[i,j] i j NO_EDGE ຈາກນີ້ໄປ, ພວກເຮົາເວົ້າວ່າ – ມີໄລຍະຫ່າງລະຫວ່າງຈຸດສູງສຸດ ແລະ . W[i,j] i j ຕໍ່ໄປ, ພວກເຮົາເອົາ vertex ແລະ iterate ຜ່ານທຸກຄູ່ຂອງ vertexes ກວດເບິ່ງວ່າໄລຍະທາງ ແມ່ນນ້ອຍກວ່າໄລຍະຫ່າງລະຫວ່າງ ກັບ . k W[i,j] i ⭢ k ⭢ j i j ຄ່າທີ່ນ້ອຍທີ່ສຸດຈະຖືກເກັບໄວ້ໃນ ແລະຂັ້ນຕອນ #3 ແມ່ນຊ້ໍາກັນສໍາລັບ ຕໍ່ໄປຈົນກ່ວາຈຸດສູງສຸດທັງຫມົດຂອງ ຖືກນໍາໃຊ້ເປັນ . W[i,j] k G k ນີ້ແມ່ນລະຫັດ pseudo: algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm ເມື່ອເຮັດແລ້ວ, ທຸກໆຕາລາງ ຂອງ matrix ຈະມີໄລຍະຫ່າງຂອງເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດລະຫວ່າງຈຸດ ແລະ ຫຼືຄ່າ , ຖ້າບໍ່ມີເສັ້ນທາງລະຫວ່າງພວກມັນ. W[i,j] W i j NO_EDGE ດັ່ງທີ່ຂ້າພະເຈົ້າໄດ້ກ່າວໃນຕອນຕົ້ນ - ມີພຽງແຕ່ຂໍ້ມູນນີ້ເຮັດໃຫ້ມັນເປັນໄປບໍ່ໄດ້ທີ່ຈະສ້າງເສັ້ນທາງລະຫວ່າງຈຸດສູງສຸດເຫຼົ່ານີ້. ດັ່ງນັ້ນ… ພວກເຮົາຄວນເຮັດແນວໃດເພື່ອໃຫ້ສາມາດສ້າງເສັ້ນທາງເຫຼົ່ານີ້ຄືນໃຫມ່? ດີ… ມັນອາດຈະຟັງໄດ້ຊັດເຈນ ແຕ່… ພວກເຮົາຕ້ອງເກັບກຳຂໍ້ມູນຕື່ມອີກ! … ເລັກນ້ອຍຂອງທິດສະດີດຽວກັນແຕ່ຈາກມຸມທີ່ແຕກຕ່າງກັນ ໂດຍເນື້ອແທ້ແລ້ວຂອງ Floyd-Warshall algorithm ແມ່ນຊ່ອງຫວ່າງຂອງໄລຍະທາງທີ່ຮູ້ຈັກ ທີ່ມີໄລຍະຫ່າງຂອງເສັ້ນທາງທີ່ອາດຈະເປັນໄປໄດ້ໃຫມ່ຈາກ ຫາ ຜ່ານຈຸດກາງ . W[i,j] i j k ຂ້າພະເຈົ້າດຶງຄວາມສົນໃຈຫຼາຍກັບລາຍລະອຽດນີ້ເພາະວ່າມັນເປັນກຸນແຈຂອງວິທີທີ່ພວກເຮົາສາມາດຮັກສາຂໍ້ມູນເສັ້ນທາງ. ໃຫ້ພວກເຮົາເອົາເສັ້ນສະແດງກ່ອນຫນ້າຂອງ 5 vertexes (ເບິ່ງຮູບ 2) ແລະປະຕິບັດວິທີການ Floyd-Warshall ກ່ຽວກັບມັນ. ໃນເບື້ອງຕົ້ນ, ພວກເຮົາຮູ້ກ່ຽວກັບຂອບກາຟທັງຫມົດ, ເຊິ່ງເຮັດໃຫ້ພວກເຮົາມີເສັ້ນທາງດັ່ງຕໍ່ໄປນີ້: , , , ແລະ . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 ຂ້ອຍໃຊ້ຮູບແບບ "ຈາກ" ⭢ "ເຖິງ" : "ໄລຍະຫ່າງ" ຈາກ ເພື່ອຂຽນເສັ້ນທາງ. ຂໍ້ຄວາມທີ່ຜ່ານມາ - ບັນທຶກຂອງຜູ້ຂຽນ ພວກເຮົາຍັງຮູ້ວ່າບໍ່ມີຂອບທີ່ນໍາໄປສູ່ຈຸດສູງສຸດ , ດັ່ງນັ້ນການປະຕິບັດສູດການຄິດໄລ່ສໍາລັບ ບໍ່ມີຄວາມຫມາຍ. ມັນຍັງເຫັນໄດ້ຊັດເຈນ, ມີຂອບດຽວ ( ) ທີ່ນໍາໄປສູ່ຈາກຈຸດສູງສຸດ ຫາຈຸດສູງສຸດ , ເຊິ່ງເຮັດໃຫ້ການປະຕິບັດທັງຫມົດຂອງ ( ແມ່ນ "ຈາກ" ທີ່ນີ້) ຂ້ອນຂ້າງບໍ່ມີຄວາມ ໝາຍ ແລະຍ້ອນວ່າຈຸດສູງສຸດ ມີຂອບດ້ວຍ ແລະ , ມັນຍັງບໍ່ມີຄວາມຫມາຍທີ່ຈະປະຕິບັດ algorithms ສໍາລັບ ໃດໆທີ່ບໍ່ແມ່ນ ຫຼື ( ແມ່ນ "to" ທີ່ນີ້). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j ນັ້ນແມ່ນເຫດຜົນທີ່ວ່າຂັ້ນຕອນທໍາອິດຂອງພວກເຮົາແມ່ນເພື່ອປະຕິບັດ algorithm ສໍາລັບ , ແລະ . k = 1 i = 0 j = 2,4 ຂັ້ນຕອນ ເສັ້ນທາງ ຄໍາເຫັນ 1 0 ⭢ 1 ⭢ 2 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 3 (ບໍ່ມີຫຍັງເລີຍ) 2 0 ⭢ 1 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະຫ່າງ = 8 (ແມ່ນ 10). ພວກເຮົາໄດ້ພົບເຫັນສອງເສັ້ນທາງ: ເສັ້ນທາງໃຫມ່ ( ) ແລະທາງລັດ ( ). ທັງສອງຜ່ານຈຸດສູງສຸດ . ຖ້າພວກເຮົາບໍ່ເກັບຮັກສາຂໍ້ມູນນີ້ (ຄວາມຈິງທີ່ພວກເຮົາໄດ້ໄປຫາ ແລະ ເຖິງ ) ບາງບ່ອນໃນປັດຈຸບັນ, ມັນຈະສູນເສຍຕະຫຼອດໄປ (ແລະນັ້ນແມ່ນຂ້ອນຂ້າງກົງກັນຂ້າມກັບສິ່ງທີ່ພວກເຮົາຕ້ອງການ). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 ດັ່ງນັ້ນພວກເຮົາຄວນເຮັດແນວໃດ? ພວກເຮົາຈະປັບປຸງ matrix ກັບຄ່າໃຫມ່ (ເບິ່ງຮູບພາບ 3a) ແລະຍັງເກັບຄ່າຂອງ (ຊຶ່ງເປັນ ) ໃນເຊລ ແລະ ຂອງ matrix ໃຫມ່ຂະຫນາດດຽວກັນ ເປັນ matrix ແຕ່ເລີ່ມຕົ້ນດ້ວຍຄ່າ (ເບິ່ງຮູບ 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE ໃນປັດຈຸບັນ, ບໍ່ໄດ້ສຸມໃສ່ສິ່ງທີ່ແນ່ນອນ matrix ແມ່ນ. ໃຫ້ເຮົາສືບຕໍ່ໄປ ແລະປະຕິບັດ algorithm ສໍາລັບ ຕໍ່ໄປ. R k = 2 ໃນທີ່ນີ້, ພວກເຮົາຈະເຮັດການວິເຄາະດຽວກັນ (ເພື່ອເຂົ້າໃຈວ່າການລວມກັນແມ່ນຫຍັງທີ່ມີຄວາມຫມາຍທີ່ຈະປະຕິບັດ) ດັ່ງທີ່ພວກເຮົາໄດ້ເຮັດສໍາລັບ ແຕ່ເວລານີ້, ພວກເຮົາຈະໃຊ້ matrix ແທນກຣາຟ . ເບິ່ງ matrix , ໂດຍສະເພາະໃນຖັນ #2 ແລະແຖວ #2 (ຮູບ 4). k = 1, W G W ໃນທີ່ນີ້ທ່ານສາມາດເຫັນໄດ້, ມີສອງເສັ້ນທາງໄປສູ່ຈຸດສູງສຸດ ຈາກຈຸດສູງສຸດ ແລະຈາກຈຸດສູງສຸດ (ຖັນ # 2), ແລະສອງເສັ້ນທາງຈາກຈຸດສູງສຸດ ຫາຈຸດສູງສຸດ ແລະເຖິງຈຸດສູງສຸດ (ແຖວທີ 2). ຮູ້ວ່າ, ມັນເຮັດໃຫ້ຄວາມຮູ້ສຶກທີ່ຈະປະຕິບັດ algorithm ພຽງແຕ່ສໍາລັບການປະສົມຂອງ , ແລະ . 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 ຂັ້ນຕອນ ເສັ້ນທາງ ຄໍາເຫັນ 1 0 ⭢ 2 ⭢ 3 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 4 (ບໍ່ມີຫຍັງເລີຍ) 2 0 ⭢ 2 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 6 (ເທົ່າກັບ 8) 3 1 ⭢ 2 ⭢ 3 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 2 (ບໍ່ມີຫຍັງເລີຍ) 4 1 ⭢ 2 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 4 (ເທົ່າກັບ 6) ດັ່ງທີ່ພວກເຮົາໄດ້ເຮັດໃນເມື່ອກ່ອນ, ພວກເຮົາກໍາລັງປັບປຸງຈຸລັງ , , , ດ້ວຍໄລຍະຫ່າງໃຫມ່ແລະເຊລ , , ແລະ ດ້ວຍ (ເບິ່ງຮູບທີ 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 ມີພຽງແຕ່ ໄວ້ເພື່ອປະມວນຜົນ (ເນື່ອງຈາກວ່າບໍ່ມີຂອບທີ່ນໍາຈາກ vertex ກັບ vertex ອື່ນໆໃນກາຟ). k = 3 4 ອີກເທື່ອຫນຶ່ງ, ໃຫ້ພວກເຮົາເບິ່ງຢູ່ໃນ matrix (ຮູບ 6). W ອີງຕາມ matrix , ມີສາມເສັ້ນທາງໄປຫາຈຸດສູງສຸດ ຈາກ vertexes , ແລະ (ຖັນ #3), ແລະມີເສັ້ນທາງດຽວຈາກຈຸດສູງສຸດ ຫາຈຸດ (ແຖວ #3). ດັ່ງນັ້ນ, ພວກເຮົາມີເສັ້ນທາງການປຸງແຕ່ງດັ່ງຕໍ່ໄປນີ້: W 3 0 1 2 3 4 ຂັ້ນຕອນ ເສັ້ນທາງ ຄໍາເຫັນ 1 0 ⭢ 3 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 5 (ເທົ່າກັບ 6) 2 1 ⭢ 3 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 3 (ເທົ່າກັບ 4) 3 2 ⭢ 3 ⭢ 4 ພົບເສັ້ນທາງ. ໄລຍະທາງ = 2 (ເທົ່າກັບ 3) ນີ້ແມ່ນການ iteration ສຸດທ້າຍຂອງ algorithm. ທັງໝົດທີ່ເຫຼືອແມ່ນການປັບປຸງເຊລ , , ດ້ວຍໄລຍະຫ່າງໃໝ່ ແລະກຳນົດເຊລ , , ເຖິງ . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 ນີ້ແມ່ນສິ່ງທີ່ພວກເຮົາມີຢູ່ໃນຕອນທ້າຍຂອງ algorithm (ຮູບ 7). ດັ່ງທີ່ພວກເຮົາຮູ້ຈາກ , matrix ປະຈຸບັນມີຄູ່ຂອງເສັ້ນທາງສັ້ນທີ່ສຸດໃນກຣາບ ແຕ່ສິ່ງທີ່ເກັບໄວ້ໃນ matrix ແມ່ນຫຍັງ? ການຕອບທີ່ຜ່ານມາ W G R ກັບບ້ານ ທຸກໆຄັ້ງທີ່ພວກເຮົາພົບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ, ພວກເຮົາປັບປຸງຕາລາງທີ່ສອດຄ້ອງກັນຂອງ matrix ດ້ວຍຄ່າປະຈຸບັນຂອງ . ໃນຂະນະທີ່ທໍາອິດ, ການປະຕິບັດນີ້ອາດຈະເບິ່ງຄືວ່າມີຄວາມລຶກລັບ, ມັນມີຄວາມຫມາຍທີ່ງ່າຍດາຍຫຼາຍ - ພວກເຮົາເກັບຮັກສາ vertex, ຈາກທີ່ພວກເຮົາໄດ້ໄປເຖິງຈຸດຫມາຍປາຍທາງ: (ນີ້ພວກເຮົາໄປເຖິງ ໂດຍກົງຈາກ ). R k i ⭢ k ⭢ j j k ປັດຈຸບັນນີ້ແມ່ນສໍາຄັນ. ເນື່ອງຈາກວ່າການຮູ້ຈຸດສູງສຸດທີ່ພວກເຮົາມາຈາກເຮັດໃຫ້ພວກເຮົາສາມາດສ້າງເສັ້ນທາງຄືນໃຫມ່ໄດ້ໂດຍການຍ້າຍກັບຄືນໄປບ່ອນ (ເຊັ່ນ: lobster) ຈາກ vertex ("ເຖິງ") ກັບ vertex ("ຈາກ"). j i ນີ້ແມ່ນຄໍາອະທິບາຍຂໍ້ຄວາມຂອງ algorithm ເພື່ອສ້າງເສັ້ນທາງຈາກ ຫາ : i j ກະກຽມອະເຣ Dynamic ຫວ່າງເປົ່າ. X ເລີ່ມໂດຍການອ່ານຄ່າ ຈາກເຊລ . z R[i,j] ຖ້າ ແມ່ນ , ເສັ້ນທາງຈາກ ຫາ ແມ່ນພົບແລະພວກເຮົາຄວນຈະດໍາເນີນຂັ້ນຕອນ #7. z NO_EDGE i j Prepend ກັບ dynamic array . z X ອ່ານຄ່າຂອງເຊລ ເປັນ . R[i,z] z ເຮັດຊ້ໍາຂັ້ນຕອນ #3, #4, ແລະ #5 ຈົນກ່ວາເງື່ອນໄຂທາງອອກໃນ #3 ບັນລຸໄດ້. Prepend ກັບ X. i ຕື່ມ ກັບ . j X ໃນປັດຈຸບັນ dynamic array ມີເສັ້ນທາງຈາກ ຫາ . X i j ກະລຸນາຮັບຊາບ, ສູດການຄິດໄລ່ຂ້າງເທິງນີ້ໃຊ້ໄດ້ກັບເສັ້ນທາງທີ່ມີຢູ່ແລ້ວເທົ່ານັ້ນ. ມັນຍັງບໍ່ສົມບູນແບບຈາກທັດສະນະຂອງການປະຕິບັດແລະແນ່ນອນວ່າສາມາດເພີ່ມປະສິດທິພາບໄດ້. ຢ່າງໃດກໍ່ຕາມ, ໃນຂອບເຂດຂອງຂໍ້ຄວາມນີ້, ມັນໄດ້ຖືກອະທິບາຍໂດຍສະເພາະໃນລັກສະນະທີ່ເຮັດໃຫ້ມັນງ່າຍຕໍ່ການເຂົ້າໃຈແລະເຮັດຊ້ໍາໃນແຜ່ນເຈ້ຍ. - ບັນທຶກຂອງຜູ້ຂຽນ ໃນລະຫັດ pseudo, ມັນເບິ່ງຄືວ່າງ່າຍດາຍກວ່າ: algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm ໃຫ້ລອງມັນຢູ່ໃນເສັ້ນກຣາບ ຂອງພວກເຮົາ ແລະສ້າງເສັ້ນທາງຈາກຈຸດສູງສຸດ ຫາຈຸດສູງສຸດ (ເບິ່ງຮູບທີ 8). G 0 4 ນີ້ແມ່ນຄຳອະທິບາຍທີ່ເປັນຕົວໜັງສືຂອງຮູບຂ້າງເທິງ: ພວກເຮົາເລີ່ມຕົ້ນໂດຍການອ່ານຄ່າຈາກ , ເຊິ່ງຜົນໄດ້ຮັບໃນ . ອີງຕາມສູດການຄິດໄລ່, ນີ້ຫມາຍຄວາມວ່າເສັ້ນທາງໄປສູ່ຈຸດສູງສຸດ ຈາກຈຸດສູງສຸດ (ສະແດງເປັນສີຟ້າ). R[0,4] 3 4 3 ເນື່ອງຈາກວ່າຄ່າຂອງ ບໍ່ແມ່ນ , ພວກເຮົາດໍາເນີນການຕໍ່ໄປແລະອ່ານຄ່າຂອງ ເຊິ່ງຜົນໄດ້ຮັບໃນ (ສະແດງຢູ່ໃນສີຂຽວ). R[0,4] NO_EDGE R[0,3] 2 ອີກເທື່ອຫນຶ່ງ, ເນື່ອງຈາກວ່າຄ່າຂອງ ບໍ່ແມ່ນ , ພວກເຮົາດໍາເນີນການຕໍ່ໄປແລະອ່ານຄ່າຂອງ ເຊິ່ງຜົນໄດ້ຮັບໃນ (ສະແດງຢູ່ໃນ RED). R[0,3] NO_EDGE R[0,2] 1 ໃນທີ່ສຸດ, ພວກເຮົາອ່ານຄ່າຂອງ , ເຊິ່ງສົ່ງຜົນໃຫ້ຄ່າ , ຊຶ່ງຫມາຍຄວາມວ່າ, ບໍ່ມີຈຸດສູງສຸດຍົກເວັ້ນ ແລະ ທີ່ປະກອບສ່ວນເຂົ້າໃນເສັ້ນທາງ. ດັ່ງນັ້ນ, ເສັ້ນທາງທີ່ໄດ້ຮັບຜົນແມ່ນ: ເຊິ່ງຖ້າທ່ານເບິ່ງເສັ້ນສະແດງຕົວຈິງແມ່ນກົງກັບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດຈາກຈຸດສູງສຸດ ຫາຈຸດສູງສຸດ . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 ຜູ້ອ່ານທີ່ຄິດຈະຖາມວ່າ: ພວກເຮົາສາມາດແນ່ໃຈວ່າຂໍ້ມູນທັງຫມົດທີ່ພວກເຮົາອ່ານຈາກ matrix ເປັນເສັ້ນທາງດຽວກັນ? R - ຜູ້ອ່ານທີ່ຄິດ ມັນເປັນຄໍາຖາມທີ່ດີຫຼາຍ. ພວກເຮົາແນ່ໃຈວ່າຍ້ອນວ່າພວກເຮົາປັບປຸງ matrix ດ້ວຍຄ່າໃຫມ່ເມື່ອພວກເຮົາປັບປຸງຄ່າເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດໃນ matrix . ດັ່ງນັ້ນໃນທີ່ສຸດ, ທຸກໆແຖວຂອງ matrix ມີຂໍ້ມູນທີ່ກ່ຽວຂ້ອງກັບເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ. ບໍ່ມີຫຼາຍ, ບໍ່ຫນ້ອຍ. R W R ໃນປັດຈຸບັນ, ພວກເຮົາເຮັດກັບທິດສະດີ, ມັນແມ່ນເວລາປະຕິບັດ. ການປະຕິບັດໃນ C# ໃນ , ນອກເຫນືອຈາກການຈັດຕັ້ງປະຕິບັດຕົ້ນສະບັບຂອງ Floyd-Warshall algorithm, ພວກເຮົາຍັງໄດ້ປະສົມປະສານການເພີ່ມປະສິດທິພາບຕ່າງໆ: ການສະຫນັບສະຫນູນເສັ້ນສະແດງ, ຂະຫນານ, ແລະ vectorization, ແລະໃນທີ່ສຸດ, ພວກເຮົາຍັງໄດ້ລວມເອົາພວກມັນທັງຫມົດ. ບົດຂຽນທີ່ຜ່ານມາ ບໍ່ມີເຫດຜົນທີ່ຈະເຮັດຊ້ໍາສິ່ງທັງຫມົດນີ້ໃນມື້ນີ້. ຢ່າງໃດກໍຕາມ, ຂ້າພະເຈົ້າຢາກຈະສະແດງໃຫ້ທ່ານເຫັນວິທີການປະສົມປະສານການທ່ອງຈໍາເສັ້ນທາງເຂົ້າໄປໃນຕົ້ນສະບັບແລະ vectorized (ໂດຍສະຫນັບສະຫນູນສໍາລັບກາຟ sparse) ສະບັບຂອງ algorithm. ການປະສົມປະສານເຂົ້າໃນລະບົບສູດການຄິດໄລ່ຕົ້ນສະບັບ ມັນອາດຈະເປັນການຍາກທີ່ຈະເຊື່ອແຕ່ເພື່ອປະສົມປະສານການຈື່ເສັ້ນທາງເຂົ້າໄປໃນສະບັບຕົ້ນສະບັບຂອງ algorithms, ທັງຫມົດທີ່ພວກເຮົາຕ້ອງເຮັດຄື: ຂະຫຍາຍລາຍເຊັນຟັງຊັນເພື່ອລວມເອົາ matrix ເປັນພາລາມິເຕີແຍກຕ່າງຫາກ – . R int[] routes ບັນທຶກ k ໄປຫາ ທຸກຄັ້ງທີ່ເສັ້ນທາງສັ້ນທີ່ສຸດມີການປ່ຽນແປງ (ເສັ້ນ: 2 ແລະ 14). routes ນັ້ນແມ່ນມັນ. ພຽງແຕ່ຫນຶ່ງແລະເຄິ່ງຫນຶ່ງຂອງລະຫັດ: public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } ການປະສົມປະສານເຂົ້າໄປໃນ Vectorized Algorithm ການລວມເຂົ້າກັນເປັນ vectorized (ໂດຍສະຫນັບສະຫນູນກຣາຟ sparse) ສະບັບໃຊ້ຄວາມພະຍາຍາມຫຼາຍເລັກນ້ອຍເພື່ອໃຫ້ສໍາເລັດ, ຢ່າງໃດກໍຕາມ, ຂັ້ນຕອນແນວຄວາມຄິດແມ່ນຄືກັນ: ຂະຫຍາຍລາຍເຊັນຟັງຊັນເພື່ອລວມເອົາ matrix ເປັນພາລາມິເຕີແຍກຕ່າງຫາກ – . R int[] routes ໃນແຕ່ລະ iteration, ເລີ່ມຕົ້ນ vector ໃຫມ່ຂອງຄ່າ (ເສັ້ນ: 6). k ບັນທຶກ ຄ່າ vector ໄປຫາ ທຸກຄັ້ງທີ່ເສັ້ນທາງສັ້ນທີ່ສຸດຖືກປ່ຽນ (ເສັ້ນ: 31-32). k routes ປັບປຸງສ່ວນທີ່ບໍ່ແມ່ນ vectorized ຂອງ algorithm ໃນລັກສະນະດຽວກັນທີ່ພວກເຮົາໄດ້ປັບປຸງ algorithm ຕົ້ນສະບັບ (ເສັ້ນ: 41). public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k (k); for (var i = 0; i (matrix[i * sz + k]); var j = 0; for (; j .Count; j += Vector .Count) { var ij_vec = new Vector (matrix, i * sz + j); var ikj_vec = new Vector (matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector (-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector (routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } ການເຕືອນເລັກນ້ອຍ – ການດໍາເນີນງານ ສົ່ງຄືນ vector ໃຫມ່ທີ່ຄ່າເທົ່າກັບນ້ອຍກວ່າຂອງສອງຄ່າທີ່ສອດຄ້ອງກັນຂອງ vectors input, ie, ຖ້າຄ່າຂອງ vector ເທົ່າກັບ , ຫຼັງຈາກນັ້ນການດໍາເນີນງານເລືອກຄ່າຈາກ , ຖ້າບໍ່ດັ່ງນັ້ນ, ມັນເລືອກຄ່າຈາກ . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - ບັນທຶກຂອງຜູ້ຂຽນ Benchmarking ການເກັບກໍາຂໍ້ມູນເສັ້ນທາງເບິ່ງຄືວ່າສົມເຫດສົມຜົນພຽງພໍເນື່ອງຈາກວ່າ ... ດີເປັນຫຍັງບໍ່? ໂດຍສະເພາະແມ່ນໃນເວລາທີ່ມັນເປັນສະນັ້ນງ່າຍທີ່ຈະເຊື່ອມໂຍງເຂົ້າກັບວິທີການທີ່ມີຢູ່ແລ້ວ. ຢ່າງໃດກໍຕາມ, ໃຫ້ເບິ່ງວິທີການປະຕິບັດການລວມມັນໂດຍຄ່າເລີ່ມຕົ້ນ. ນີ້ແມ່ນສອງຊຸດຂອງມາດຕະຖານ: ມີ ແລະບໍ່ມີ (ທັງສອງປະຕິບັດສະບັບຕົ້ນສະບັບ ແລະ vectorized ຂອງ algorithm). ມາດຕະຖານທັງໝົດຖືກປະຕິບັດໂດຍ v0.13.1 (.NET 6.0.4 x64) ໃນເຄື່ອງທີ່ຕິດຕັ້ງດ້ວຍໂປເຊດເຊີ Intel Core i5-6200U CPU 2.30GHz (Skylake) ແລະແລ່ນ Windows 10. BenchmarkDotNet ການທົດລອງທັງຫມົດແມ່ນໄດ້ຮັບການປະຕິບັດກ່ຽວກັບການກໍານົດໄວ້ລ່ວງຫນ້າຂອງກາຟທີ່ນໍາໃຊ້ໃນ : 300, 600, 1200, 2400, ແລະ 4800 vertexes. ການຕອບທີ່ຜ່ານມາ ລະຫັດແຫຼ່ງແລະກາຟທົດລອງແມ່ນມີຢູ່ໃນ repository ໃນ GitHub. ກຣາຟທົດລອງສາມາດພົບໄດ້ຢູ່ໃນໄດເລກະທໍລີ . ໄຟລ໌ Data/Sparse-Graphs.zip ດັດຊະນີທັງໝົດໃນໂພສນີ້ຖືກປະຕິບັດຢູ່ໃນ APSP02.cs . ຂ້າງລຸ່ມນີ້ແມ່ນຜົນໄດ້ຮັບ benchmark ທີ່ວິທີການ ແລະ ກົງກັນກັບສະບັບຕົ້ນສະບັບຂອງ algorithm ແລະ ແລະ method ກົງກັບ vectorized (ສະຫນັບສະຫນູນສໍາລັບ sparse graphs) ສະບັບຂອງ algorithm. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes ວິທີການ ຂະໜາດ ສະເລ່ຍ (ms) ຄວາມຜິດພາດ (ms) StdDev (ms) ພື້ນຖານ 300 40.233 0.0572 0.0477 BaselineWithRoutes 300 40.349 0.1284 0.1201 ການເພີ່ມປະສິດທິພາບ SpartialVector 300 4.472 0.0168 0.0140 SpartialVector Optimisations WithRoutes 300 4.517 0.0218 0.0193 ພື້ນຖານ 600 324.637 5.6161 4.6897 BaselineWithRoutes 600 321.173 1.4339 1.2711 ການເພີ່ມປະສິດທິພາບ SpartialVector 600 32.133 0.2151 0.1679 SpartialVector Optimisations WithRoutes 600 34.646 0.1286 0.1073 ພື້ນຖານ 1200 2,656.024 6.9640 5.8153 BaselineWithRoutes 1200 2,657.883 8.8814 7.4164 ການເພີ່ມປະສິດທິພາບ SpartialVector 1200 361.435 2.5877 2.2940 SpartialVector Optimisations WithRoutes 1200 381.625 3.6975 3.2777 ພື້ນຖານ 2400 21,059.519 38.2291 33.8891 BaselineWithRoutes 2400 20,954.852 56.4719 50.0609 ການເພີ່ມປະສິດທິພາບ SpartialVector 2400 3,029.488 ໑໒.໑໕໒໘ 11.3677 SpartialVector Optimisations WithRoutes 2400 3,079.006 8.6125 7.1918 ພື້ນຖານ 4800 164,869.803 547.6675 427.5828 BaselineWithRoutes 4800 184,305. 980 210.9535 164.6986 ການເພີ່ມປະສິດທິພາບ SpartialVector 4800 21,882.379 200.2820 177.5448 SpartialVector Optimisations WithRoutes 4800 21,004.612 79.8752 70.8073 ຜົນໄດ້ຮັບ Benchmark ບໍ່ງ່າຍດາຍທີ່ຈະຕີຄວາມຫມາຍ. ຖ້າທ່ານເບິ່ງໃກ້ຊິດ, ທ່ານຈະພົບເຫັນການປະສົມປະສານໃນເວລາທີ່ການເກັບກໍາເສັ້ນທາງຕົວຈິງເຮັດໃຫ້ algorithm ແລ່ນໄວຂຶ້ນຫຼືບໍ່ມີຜົນກະທົບທີ່ສໍາຄັນໃດໆ. ນີ້ເບິ່ງຄືວ່າສັບສົນຫຼາຍ (ແລະຖ້າມັນເປັນ - ຂ້ອຍຂໍແນະນໍາໃຫ້ເຈົ້າຟັງ ນີ້ກັບ ແລະ ເພື່ອເຂົ້າໃຈດີຂຶ້ນວ່າສິ່ງທີ່ຫຍຸ້ງຍາກສາມາດສົ່ງຜົນກະທົບຕໍ່ການວັດແທກ). ການປະຕິບັດທີ່ດີທີ່ສຸດຂອງຂ້ອຍແມ່ນວ່າພຶດຕິກໍາ "ສັບສົນ" ແມ່ນເກີດມາຈາກການປະຕິບັດ cache ຂອງ CPU ທີ່ຍິ່ງໃຫຍ່ (ເພາະວ່າກາຟບໍ່ໃຫຍ່ພໍທີ່ຈະ saturate cache). ບາງສ່ວນ, ທິດສະດີນີ້ແມ່ນອີງໃສ່ຕົວຢ່າງ " " ບ່ອນທີ່ພວກເຮົາສາມາດເຫັນການເຊື່ອມໂຊມທີ່ສໍາຄັນໃນກາຟທີ່ໃຫຍ່ທີ່ສຸດ. ຢ່າງໃດກໍຕາມ, ຂ້າພະເຈົ້າບໍ່ໄດ້ກວດສອບມັນ. ລາຍການ Denis Bakhvalov Andrey Akinshin ກ້າຫານ ໂດຍທົ່ວໄປ, benchmark ສະແດງໃຫ້ເຫັນວ່າຖ້າພວກເຮົາບໍ່ໄດ້ເວົ້າກ່ຽວກັບສະຖານະການທີ່ມີປະສິດທິພາບສູງແລະກາຟຂະຫນາດໃຫຍ່, ມັນເຫມາະສົມທີ່ຈະປະສົມປະສານການຈໍາແນກເສັ້ນທາງເຂົ້າໄປໃນທັງສອງ algorithms ໂດຍຄ່າເລີ່ມຕົ້ນ (ແຕ່ຈື່ໄວ້ວ່າມັນຈະບໍລິໂພກຄວາມຈໍາສອງເທົ່າເພາະວ່າພວກເຮົາຕ້ອງການ. ຈັດສັນສອງ matrices ແລະ ແທນທີ່ຈະເປັນຫນຶ່ງ). W R ສິ່ງດຽວທີ່ເຫລືອແມ່ນການປະຕິບັດວິທີການສ້າງເສັ້ນທາງຄືນໃຫມ່. ການປະຕິບັດວິທີການສ້າງເສັ້ນທາງຄືນໃຫມ່ ການປະຕິບັດວິທີການສ້າງເສັ້ນທາງໃຫມ່ໃນ C# ແມ່ນກົງໄປກົງມາແລະເກືອບທັງຫມົດສະທ້ອນໃຫ້ເຫັນເຖິງລະຫັດ pseudo-code ທີ່ສະແດງໃຫ້ເຫັນກ່ອນຫນ້ານີ້ (ພວກເຮົາໃຊ້ ເພື່ອເປັນຕົວແທນຂອງອາເຣແບບເຄື່ອນໄຫວ): LinkedList public static IEnumerable RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList (); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; } ສູດການຄິດໄລ່ຂ້າງເທິງນີ້ບໍ່ສົມບູນແບບ ແລະແນ່ນອນສາມາດປັບປຸງໄດ້. ການປັບປຸງທີ່ງ່າຍດາຍທີ່ສຸດທີ່ພວກເຮົາສາມາດເຮັດໄດ້ແມ່ນການຈັດສັນ array ຂອງຂະຫນາດ ແລະຕື່ມຂໍ້ມູນໃສ່ໃນລໍາດັບປີ້ນກັບກັນ: sz public static IEnumerable RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment (x, y, sz - y); } ໃນຂະນະທີ່ "ການເພີ່ມປະສິດທິພາບ" ນີ້ຫຼຸດລົງຈໍານວນການຈັດສັນຫນຶ່ງ, ມັນບໍ່ຈໍາເປັນຕ້ອງເຮັດໃຫ້ສູດການຄິດໄລ່ "ໄວ" ຫຼື "ຈັດສັນຫນ່ວຍຄວາມຈໍາຫນ້ອຍ" ກ່ວາອັນທີ່ຜ່ານມາ. ຈຸດນີ້ແມ່ນຖ້າພວກເຮົາຈໍາເປັນຕ້ອງມີເສັ້ນທາງທີ່ສັ່ງຈາກ ຫາ , ພວກເຮົາສະເຫມີຈະຕ້ອງ "ກັບຄືນ" ຂໍ້ມູນທີ່ພວກເຮົາດຶງມາຈາກ matrix , ແລະບໍ່ມີທາງທີ່ຈະຫນີມັນ. i j R ແຕ່ຖ້າພວກເຮົາສາມາດນໍາສະເຫນີຂໍ້ມູນຕາມລໍາດັບ, ພວກເຮົາສາມາດໃຊ້ LINQ ແລະຫຼີກເວັ້ນການຈັດສັນທີ່ບໍ່ຈໍາເປັນ: public static IEnumerable RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; } ມັນສາມາດມີຫຼາຍຕົວແປຂອງວິທີການລະຫັດນີ້ສາມາດ "ປ່ຽນ" ຫຼື "ປັບປຸງ." ເວລາທີ່ສໍາຄັນຢູ່ທີ່ນີ້ແມ່ນເພື່ອຈື່ - "ການປ່ຽນແປງ" ໃດກໍ່ຕາມມີການຫຼຸດລົງໃນແງ່ຂອງຫນ່ວຍຄວາມຈໍາຫຼືວົງຈອນ CPU. ຮູ້ສຶກວ່າບໍ່ເສຍຄ່າເພື່ອທົດລອງ! ຄວາມເປັນໄປໄດ້ເກືອບບໍ່ຈຳກັດ! ທ່ານສາມາດຊອກຫາການຈັດຕັ້ງປະຕິບັດລະບົບເສັ້ນທາງທັງໝົດໃນ GitHub ໃນໄຟລ໌ Routes.cs . ສະຫຼຸບ ໃນບົດຂຽນນີ້, ພວກເຮົາໄດ້ເຈາະເລິກເຂົ້າໄປໃນທິດສະດີທີ່ຢູ່ເບື້ອງຫຼັງຂອງ Floyd-Warshall algorithm ແລະໄດ້ຂະຫຍາຍມັນດ້ວຍຄວາມເປັນໄປໄດ້ຂອງການຈື່ຈໍາເສັ້ນທາງທີ່ສັ້ນທີ່ສຸດ "ເສັ້ນທາງ." ຫຼັງຈາກນັ້ນ, ພວກເຮົາໄດ້ປັບປຸງການປະຕິບັດ C # (ຕົ້ນສະບັບແລະ vectorized) ຈາກ . ໃນທີ່ສຸດ, ພວກເຮົາໄດ້ປະຕິບັດສອງສາມສະບັບຂອງສູດການຄິດໄລ່ເພື່ອສ້າງ "ເສັ້ນທາງ". ຂໍ້ຄວາມທີ່ຜ່ານມາ ພວກເຮົາໄດ້ເຮັດຊ້ໍາອີກຫຼາຍ, ແຕ່ໃນເວລາດຽວກັນ, ຂ້ອຍຫວັງວ່າເຈົ້າຈະພົບເຫັນສິ່ງໃຫມ່ແລະຫນ້າສົນໃຈໃນອັນນີ້. ນີ້ບໍ່ແມ່ນຈຸດຈົບຂອງບັນຫາເສັ້ນທາງສັ້ນທີ່ສຸດຄູ່ທັງໝົດ. ນີ້ແມ່ນພຽງແຕ່ການເລີ່ມຕົ້ນ. ຂ້າພະເຈົ້າຫວັງວ່າທ່ານຈະມີຄວາມສຸກການອ່ານ, ແລະພົບທ່ານໃນຄັ້ງຕໍ່ໄປ!