خوارزمية فلويد: تستخدم لحل أقصر مسار من المصادر ، ويحسب أقصر مسافة بين جميع العقد والعقد المتبقية.
فكرة هذه الخوارزمية هي: أولاً تهيئة مصفوفة المسافة ، ثم تحديث قيمة نقطة المصفوفة تدريجياً بدءًا من النقطة الأولى. يمثل D [i] [J] المسافة من النقطة الأولى إلى النقطة J. عندما يتم تحديث K ، احكم على أحجام d [i] [k]+d [k] [j] و d [i] [j]. إذا كان الأول صغيرًا ، فقم بتحديث هذه القيمة ، وإلا فلن يتغير.
إعطاء مثال:
خوارزمية تنفيذ Floyd المحددة هي كما يلي [Java] عرض نسخة عادي
حزمة com.plyang ؛ الفئة العامة Floyd {int [] [] Matrix ؛ تشار [] العقد ؛ Final Final int inf = integer.max_value ؛ Public Floyd (char [] notes ، int [] [] matrix) {this.nodes = nodes ؛ this.matrix = matrix ؛ } public void floyd () {int [] [] distant = new int [nodes.length] [nodes.length] ؛ // تهيئة مصفوفة المسافة لـ (int i = 0 ؛ i <nodes.length ؛ i ++) {for (int j = 0 ؛ j <nodes.length ؛ j ++) {distant [i] [j] = matrix [i] [j] ؛ }} // حلقة تحديث قيمة المصفوفة لـ (int k = 0 ؛ k <nodes.length ؛ k ++) {for (int i = 0 ؛ i <nodes.length ؛ i ++) {for (int j = 0 ؛ INF: المسافة [i] [k] + المسافة [k] [j] ؛ if (المسافة [i] [j]> temp) {المسافة [i] [j] = temp ؛ }}}}} // طباعة نتيجة أقصر مسار Floyd.UT.Printf ("Floyd: /n") ؛ لـ (int i = 0 ؛ i <nodes.length ؛ i ++) {for (int j = 0 ؛ j <nodes.length ؛ j ++) system.out.printf ("٪ 12d" ، المسافة [i] [j]) ؛ system.out.printf ("/n") ؛ }}} بعد التنفيذ ، يتم إجراء اختبار لنقاط وأوزان الشكل أعلاه:
حزمة com.plyang ؛ الفئة العامة الرئيسية {public static void main (string [] args) {int inf = integer.max_value ؛ char [] nodes = {'0' ، '1' ، '2' ، '3'} ؛ int matrix [] [] = {/*a*//*b*//*c*//*d*//*/{0 ، 1 ، 2 ، 1} ،/*b*/{inf ، inf ، inf} ،/*c*/{inf ، 3 ، 0 ، 1} ،/*d*/{inf ، 1 ، 1 ، 0} ،} ؛ int [] dist = new int [nodes.length] ؛ Floyd Floyd = New Floyd (العقد ، المصفوفة) ؛ floyd.floyd () ؛ }}ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.