อัลกอริทึมฟลอยด์: ใช้เพื่อแก้เส้นทางที่สั้นที่สุดของหลายแหล่งและคำนวณระยะห่างที่สั้นที่สุดระหว่างโหนดทั้งหมดและโหนดที่เหลือ
แนวคิดของอัลกอริทึมนี้คือ: ก่อนเริ่มต้นเมทริกซ์ระยะทางจากนั้นค่อยๆอัปเดตค่าจุดเมทริกซ์เริ่มต้นจากจุดแรก D [i] [j] หมายถึงระยะทางจากจุดที่ฉันถึงจุด J เมื่อการอัปเดต k ตัดสินขนาดของ d [i] [k]+d [k] [j] และ d [i] [j] หากอดีตมีขนาดเล็กให้อัปเดตค่านี้มิฉะนั้นจะไม่เปลี่ยนแปลง
ยกตัวอย่าง:
อัลกอริทึมการใช้งาน Floyd ที่เฉพาะเจาะจงมีดังนี้ [Java] ดูสำเนาธรรมดา
แพ็คเกจ com.blyang; ชั้นเรียนสาธารณะ Floyd {int [] [] เมทริกซ์; ถ่าน [] โหนด; INT INT สุดท้ายส่วนตัว = Integer.max_value; Public Floyd (Char [] โหนด, int [] [] matrix) {this.nodes = โหนด; this.matrix = เมทริกซ์; } โมฆะสาธารณะ Floyd () {int [] [] ระยะทาง = new int [nodes.length] [nodes.length]; // เริ่มต้นเมทริกซ์ระยะทางสำหรับ (int i = 0; i <nodes.length; i ++) {สำหรับ (int j = 0; j <nodes.length; j ++) {ระยะทาง [i] [j] = เมทริกซ์ [i] [j]; }} // ลูปอัปเดตค่าของเมทริกซ์สำหรับ (int k = 0; k <nodes.length; k ++) {สำหรับ (int i = 0; i <nodes.length; i ++) {สำหรับ (int j = 0; j <nodes.length; j ++) {int temp = (ระยะทาง INF: ระยะทาง [i] [k] + ระยะทาง [k] [j]; ถ้า (ระยะทาง [i] [j]> อุณหภูมิ) {ระยะทาง [i] [j] = อุณหภูมิ; }}}}} // พิมพ์ผลลัพธ์ของเส้นทางที่สั้นที่สุดของ Floyd ของ Floyd.out.printf ("Floyd: /n"); สำหรับ (int i = 0; i <nodes.length; i ++) {สำหรับ (int j = 0; j <nodes.length; j ++) system.out.printf ("%12d", ระยะทาง [i] [j]); System.out.printf ("/n"); - หลังจากดำเนินการแล้วจะมีการทดสอบสำหรับคะแนนและน้ำหนักของตัวเลขด้านบน:
แพ็คเกจ com.blyang; คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int inf = integer.max_value; char [] nodes = {'0', '1', '2', '3'}; int matrix [] [] = {/*a*//*b*//*c*//*d*//*a*/{0, 1, 2, 1},/*b*/{inf, 0, inf, inf,/*c*/{inf, 3, 0, 1},/*d*/{ int [] dist = new int [nodes.length]; Floyd Floyd = New Floyd (โหนด, เมทริกซ์); floyd.floyd (); -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น