أقصر مسار
الدرس 12 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
ما هو أقل عدد من الحواف اللازمة للانتقال من start إلى end؟ في الرسم البياني غير الموزون (حيث يكون لكل حافة تكلفة متساوية)، تكون الإجابة هي بالضبط ما يحسبه BFS. نظرًا لأن BFS يزور الرؤوس بمسافات متزايدة من البداية، فإن المرة الأولى التي نصل فيها إلى end تكون عبر أقصر مسار.
تكمن الحيلة في إضافة كل رأس إلى الطابور (enqueue) مع مسافته المقطوعة حتى الآن. ابدأ بـ (start, 0). في كل مرة تكتشف فيها جارًا جديدًا v من رأس على مسافة d، أضف (v, d + 1) إلى الطابور. عندما يكون v == end، أرجع d + 1.
هناك حالتان حديتان. إذا كان start == end، تكون الإجابة 0. إذا انتهى BFS دون الوصول أبدًا إلى end، فهذا يعني أن الاثنين يقعان في مكونات متصلة مختلفة، وتكون الإجابة -1.
التحدي
سهلاكتب دالة shortestPath تستقبل مصفوفة ثنائية الأبعاد من الأعداد الصحيحة adjacency، وعددًا صحيحًا start، وعددًا صحيحًا end، وتعيد أقصر مسافة (عدد الحواف) من start إلى end.
- إذا كان
start == end، فقم بإعادة0. - إذا كان الوصول إلى
endمنstartغير ممكن، فقم بإعادة-1. - خلاف ذلك، قم بإعادة الحد الأدنى لعدد الحواف بينهما.
يجب عليك استخدام فئة Graph (المتوفرة في graph) - لا تستخدم الأدوات المدمجة في اللغة (الخرائط، المجموعات) لتمثيل التجاور. يمكن استخدام أنواع المكتبة القياسية (stdlib) للبيانات المساعدة للخوارزمية (مثل مجموعات العقد التي تمت زيارتها، أو الطوابير).
جرّب بنفسك
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}