تشخيص أولويات أقصر المسارات وأوزانها

افهم الأسباب المحتملة

• تترك تحديثات الأولوية الكسولة الإدخالات القديمة عمدا. وتكون خريطة المسافات الحالية هي المعتمدة، وليس كل عنصر مخزن في الطابور.
• برهان الامتداد غير السالب في Dijkstra، وشرط إمكان الوصول من المصدر في Bellman-Ford، والتمثيل الكامل للرؤوس متطلبات مستقلة. ولا تتحقق منها عملية كومة ناجحة.

ثبّت رسما صغيرا ذا مجال عددي معلن

سجّل الحواف الموجهة، وجميع الرؤوس بما فيها المعزولة، والمصدر، وكلف الطرق المتوقعة. تحقّق من وجود كل طرف حافة، ومن انتماء الأوزان إلى المجال العددي المحدود المقبول. استخدم أعدادا صحيحة دقيقة في هذا الدليل لكي لا يخفي التقريب أو NaN التشخيص. يلزم طريق غير مباشر أرخص لإعادة إنتاج الإدخالات القديمة. ميّز عدم إمكان الوصول من المسافة صفر. يشير KeyError لجار مفقود إلى مدخل معيب، وليس إلى سبب لتغيير نظرية أقصر المسارات أو إسقاط الحافة بصمت. ولا تحتاج إلى قاعدة بيانات رسوم خارجية.

قارن الأولوية المخزنة بالمسافة المعتمدة

في تنفيذ Dijkstra الكسول، يدرج التحسن إدخالا جديدا دون إزالة القديم. وعند السحب تخط إدخالا تختلف كلفته المخزنة عن خريطة المسافات. يجعل البرنامج هذا الحدث العادي ظاهرا، ولا يكتب قيمة قديمة فوق الخريطة أبدا. وإذا أضفت خروجا مبكرا عند هدف، فاحفظ شرط الأوزان غير السالبة وفحص الصلاحية قبل اعتبار النتيجة المسحوبة مستقرة. ويحتاج كسر تعادل الصفوف أيضا إلى تسميات رؤوس قابلة للمقارنة أو عداد منفصل. هذه التفاصيل جزء من التنفيذ، وليست تنظيفا تجميليا اختياريا.

import heapq
from math import inf

graph = {"A": [("B", 9), ("C", 2)], "B": [], "C": [("B", 3)]}
distance = {vertex: inf for vertex in graph}
distance["A"] = 0
heap, trace = [(0, "A")], []
while heap:
    cost, vertex = heapq.heappop(heap)
    status = "current" if cost == distance[vertex] else "stale"
    trace.append((vertex, cost, status))
    if status == "stale":
        continue
    for neighbor, weight in graph[vertex]:
        if cost + weight < distance[neighbor]:
            distance[neighbor] = cost + weight
            heapq.heappush(heap, (distance[neighbor], neighbor))
print(trace)
print(distance["B"])

[('A', 0, 'current'), ('C', 2, 'current'), ('B', 5, 'current'), ('B', 9, 'stale')]
5

عامل الأوزان السالبة بوصفها سؤالا لاختيار الخوارزمية

إذا قُبلت حافة سالبة، فلن تصلح إضافة فحص الإدخال القديم برهان استقرار Dijkstra. اختر خوارزمية تناسب الرسم، مثل Bellman-Ford لمسارات مصدر عامة مع حواف سالبة وكشف الدورات القابلة للوصول. قد تمنع دورة سالبة واصلة وجود حد أدنى محدود للوجهات المتأثرة. ولا يمكن لدورة سالبة غير واصلة أن تظهر على طريق من المصدر، وينبغي ألا تفسد نتيجته. اربط كشف الدورة بشرط مسافة محدودة من المصدر. ولا تستبدل اللانهاية بالصفر لتبسيط الحساب، لأن ذلك يخترع طرقا إلى مكونات منفصلة.

قارن المسافات وأي طريق مستعاد كلّا على حدة

على رسوم صغيرة غير سالبة، قارن التنفيذ المصحح بمرجع Floyd-Warshall مستقل وبـ Bellman-Ford. أضف حوافا صفرية، وبدائل متساوية الكلفة، ورأسا معزولا، وتحسنا من الكلفة 9 إلى 5. اختبر رفض الحافة السالبة مستقلا عن حالتي الدورة السالبة الواصلة وغير الواصلة. وإذا أتاحت الواجهة استعادة الطريق بالسابقات، فتحقّق من وجود الحواف المستعادة ومن مساواة مجموع أوزانها للمسافة المعلنة؛ ولا يلزم أن تتفرد الطرق متساوية المسافة. لا تثبت مسافة تبدو معقولة وحدها صحة سلسلة السابقات. أبق جميع العينات بيانات محلية محدودة، بدلا من تشغيل حمل على خدمة رسوم.

امنع تكرار المشكلة

• أبق افتراضات الأوزان وملكية الرسم بجوار الواجهة. اعتمد خريطة المسافات مرجعا حاليا، واحتفظ برسم تراجع يكشف الإدخالات القديمة، وأبلغ عن الحد الفعلي لحجم الكومة الكسولة بدلا من ادعاء كومة مفهرسة.