الكاتب | رمادي صغير مبرمج

وطبع هذا المقال بإذن من الرمادي مبرمج صغير (ID: chengxuyuanxiaohui)

في اليوم التالي ----- -----

خارطة الطريق الرمادية الصغيرة هي على النحو التالي:

الخطوة الأولى من الجدول باستخدام خوارزمية ديكسترا، يتم تحديد من قمة A، أقصر مسافة لكل قمة الأخرى:

الخطوة الثانية، إلى الاستمرار في استخدام خوارزمية ديكسترا، تم الحصول عليها من قمة الرأس B، وأقصر مسافة إلى كل من القمم الأخرى.

الخطوة الثالثة، بدءا من قمة الرأس C، وأقصر مسافة لكل قمة.

الخطوة الرابعة، بدءا من قمة الرأس D ......

.......

مثل هذا، وقد اجتاز إلى قمة الرأس G.

تعقيد الوقت لهذه الفكرة هو كم؟

إذا كان هناك ن القمم في الرسم البياني، كومة دون النظر الأمثل، وقت تعقيد ديكسترا هو O (ن ^ 2). لذلك، لكل قمة تحسب مرة أخرى، ومدى تعقيد الوقت الكلي للO (ن ^ 3).

لالكستناء:

A قمة C وحافة قمة الرسم البياني ليست مرتبطة مباشرة إلى المسافة المباشرة بينهما هو لانهائي.

إذا B بأنه "أعلى التتابع"، ثم أقصر طريق من A إلى C هو A-B-C، وأقصر مسافة هو 2 + 3 = 5.

خذ الكستناء آخر:

قمة الرأس A و C قمة الرأس متصلة مباشرة إلى هذا الرقم، والمسافة 6. ومع ذلك، فإن وجود "تجاوز" مسار A-B-C، هو من 3 + 2 = 5 < 6.

ولذلك، بعد تتابع قمة B، وأقصر مسافة من A إلى C قد تكون 5.

الخطوات المفصلة التالية فلويد خوارزمية ونحن نلقي نظرة.

1. لتحقيق فلويد الخوارزمية، تحتاج أولا إلى بناء المرجح مصفوفة الرسم البياني الجوار:

بين مصفوفة الجوار، يمثل كل رقم مسافة مباشرة من قمة الرأس إلى قمة أخرى، لا علاقة التتابع لمسافة أي قمة الرأس.

2. في هذا الوقت، على افتراض أن يسمح فقط قمة الرأس إلى الرأس وكما تتابع، والمسافة بين قمة ما سيصبح من ذلك؟

وكانت المسافة بين B و C أصلا لا نهاية، في هذه الحالة تتابع A، وتقصير المسافة المسافة AB + AC = المسافة

5 + 2 = 7.

بتحديث عنصر المصفوفة المقابلة (يمثل اللون البرتقالي المسافة من قمة ألف لقمة مؤقتة أخرى):

3. بجانب القمم A، B بمثابة قمة التتابع، ثم المسافة بين قمة ما سيصبح من ذلك؟

المسافة بين A و D هي أصلا لا نهاية، B هي حالة التتابع، لتقصير المسافة AB هي المسافة من BD = + 5 + 1 = 6.

المسافة بين A و E أصلا لا نهاية، B هو حالة التتابع، وتقصير المسافة من BE AB = المسافة + 5 + 6 = 11.

بتحديث عنصر المصفوفة المقابلة (يمثل اللون البرتقالي المسافة من قمة B إلى ذروة مؤقتة أخرى):

4. بجانب القمم A، B، C باعتباره ذروة التتابع، ثم المسافة بين قمة ما سيصبح من ذلك؟

والمسافة بين النص الأصلي وF هو لانهائي، في هذه الحالة تتابع C، المسافة AC تقصير المسافة من CF2 = + 2 + 8 = 10.

التحديث (المؤقتة C من البرتقال يمثل قمة الرأس إلى قمة أخرى) المقابلة لعناصر المصفوفة:

لذلك، فإننا نواصل تقديم قمة تتابع جديدة، وتحديث باستمرار مصفوفة المسافة مؤقتة.

وأخيرا، عندما تكون جميع القمم يمكن استخدامها بوصفها ذروة التتابع، ويتم تحديث دينا مصفوفة المسافة على النحو التالي:

في هذه الحالة، كل عنصر من عناصر المصفوفة يتوافق مع أقصر مسافة من قمة الرأس إلى قمة أخرى.

كيف يمكنك أن تقول؟ دعونا ننظر اثنين من عناصر البرمجة الديناميكية:

الحالة الأولية للمشكلة

المعادلة نقل الدولة من مشكلة

للمشكلة لإيجاد المسافة بين كل من القمم من الرسم البياني، الحالة الأولية هي المسافة المباشرة بين القمم، أي الجوار المصفوفة.

مشكلة معادلة انتقال الدولة، ما هو؟

حديثا القمم قدم يفترض أن تتابع هو ن، ثم:

قمة الرأس الجديدة ط ي لقمة من = إماراتي (قمة القديمة أنا لقمة ي هي المسافة، قمة ط إلى قمة الرأس مسافة ن + ن ي القمم المسافة من قمة)

نهائي ثابت الباحث INF = Integer.MAX_VALUE. ساكنة العام باطل فلويد (الباحث المصفوفة) { // مصفوفة تحديث قيمة دورة ل(الباحث ك = 0؛ ك < matrix.length، ك ++) { ل(كثافة العمليات ط = 0؛ ط < matrix.length، وأنا ++) { ل(الباحث ي = 0؛ ي < matrix.length؛ ي ++) { إذا (مصفوفة  == INF || مصفوفة  == INF) { تواصل. } قالب  = Math.min (مصفوفة ، مصفوفة  + مصفوفة )؛ } } } // طباعة النتائج فلويد أقصر الطرق System.out.printf ( "أقصر مسار مصفوفة: \ ن")؛ ل(كثافة العمليات ط = 0؛ ط <  matrix.length، وأنا ++) { ل(الباحث ي = 0؛ ي <  matrix.length؛ ي ++) System.out.printf ( " 3D"، مصفوفة )؛ System.out.printf ( "\ ن")؛ } } ساكنة العام باطلة الرئيسية (سلسلة وسائط) { الباحث مصفوفة = { {0، 5، 2، INF، INF، INF، INF}، {5، 0، INF، 1، 6، INF، INF}، {2، INF، 0، 6، INF و 8 و INF}، {INF، 1، 6، 0، 1، 2، INF}، {INF و 6 و INF، 1، 0، INF، 7}، {INF، INF، 8، 2، INF، 0، 3}، {INF، INF، INF، INF، 7، 3، 0} }؛ فلويد (المصفوفة). }