ديكسترا للأوزان غير السالبة: تحسين المسافة وتجاوز سجل كومة قديم

المسافة مجموع أوزان لا عدد حواف

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

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

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

[1]

رسم مؤلف بست عقد

العقد هي S وA وB وC وT وG. من S توجد حافة إلى A بوزن 8 وإلى B بوزن 2. ومن B إلى A وزن 1 وإلى C وزن 5. ومن A إلى C وزن 1 وإلى T وزن 7. ومن C إلى T وزن 2، بينما لا تخرج حواف من T أوG في هذا المثال.

نبدأ من S بمسافة صفر. المسافات النهائية التي سنراجعها هي B عند 2، وA عند 3، وC عند 4، وT عند 6. أما G فهي مصرح بها لكن لا يصل إليها هذا المصدر. لا نضع مسافة صفر لعقدة غابت من نتائج الوصول؛ الصفر قيمة البداية هنا، والغياب يعني أن الحساب لم يجد طريقًا وفق الحواف التي أعطيناها.

يعرض الرسم الرئيسي الاتجاهات والأوزان وطريقًا شاهدًا إلى T، ثم تبين الصورة الداخلية السجلات القديمة مقارنةً بالمسافات الحالية. البيانات من تأليف المقال، وليست نتيجة خدمة نقل أو محرك خرائط. سنعيد جمع أوزان الشاهد وفحص كل انتقال في الرسم حتى لا يكون رقم ستة منفصلًا عن طريق يحققه.

أول عرض إلى A بثمانية ليس تثبيتًا

بعد فحص حواف S نعرف طريقًا إلى A بوزن 8 وطريقًا إلى B بوزن 2، ونضيف سجلين إلى الكومة. معرفة طريق بقيمة معينة لا تثبت أنه الأقل؛ قد يظهر طريق آخر عبر عقدة لم نوسعها بعد. لذلك لا نعامل أول إدخال في قاموس distance مثل اكتشاف نهائي لا يجوز تحسينه في مسألة الأوزان المختلفة.

يخرج سجل B بقيمة 2 قبل A بقيمة 8 لأن الكومة تختار الأقل. عبر B نصل إلى A بمرشح 2 زائد 1، أي 3، وهو أقل من العرض السابق 8. نحدث المسافة والسابق لـA ونضيف سجلًا جديدًا بقيمة 3، بينما يبقى السجل القديم ذي الثمانية في الكومة في صياغتنا.

لو ثبتنا A على الثمانية عند أول عرض ومنعنا التحسين، لفقدنا الطريق الأرخص الذي عرفناه من B. هذا فرق مهم من مرور يعتمد حوافًا ذات خطوة واحدة ويستعمل اكتشافًا أولًا بحسب طبقات الطابور. لا ننقل سياسة اكتشاف من عقد إلى آخر دون مراجعة ما يضمن أن العرض الأول أدنى كلفة.

تحسين C إلى أربعة ثم T إلى ستة

عند توسيع B نعرض أيضًا C بقيمة 2 زائد 5، أي 7. لكن سجل A الجديد بقيمة 3 يخرج قبل C ذات السبعة، وعبره نحصل على C بمرشح 3 زائد 1، أي 4. نحدثها ونضيف سجلًا جديدًا لها، ثم نعرض T من A بقيمة 3 زائد 7، أي 10.

يخرج سجل C بقيمة 4، فنحسن T إلى 4 زائد 2، أي 6. نضيف سجلًا جديدًا لـT، ثم يخرج بقيمته الحالية قبل السجلات القديمة السبعة والثمانية والعشرة. لا يوجد له جيران في الرسم، فتكتمل أعمال الوصول الفعلية، مع بقاء عناصر في الكومة نحتاج فحص حداثتها عند إخراجها.

التحسينات المحددة في المثال هي A من 8 إلى 3، وC من 7 إلى 4، وT من 10 إلى 6. نراجع المرشح مقابل أفضل ما حفظناه، ونحدث السابق عند التحسن معه. لا نغير قيمة عقدة لمجرد ورود طريق آخر متساوٍ، ولا نفترض أن عدد مرات إدخالها يساوي عدد المسارات الأقصر التي سنعرضها.

كومة الأولوية وسجل العقدة المتكرر

المحتوى المخزن في كومتنا زوج من قيمة مسافة وقت الإدخال واسم عقدة. عندما تتحسن المسافة نضيف زوجًا جديدًا، ولا نبحث في الكومة لحذف القديم. يشرح مرجع CP-Algorithms هذا الأسلوب للسجلات المتكررة، مع ضرورة التمييز بين قيمة سجل مستخرج والمسافة الحالية المحفوظة للعقدة نفسها.

إذن وجود A مرتين لا يعني وجود عقدتين باسم A في الرسم. أحد السجلين عرض أقدم بقيمة 8 والآخر عرض أحدث بقيمة 3. ولا تعيد الكومة تعديل العدد الموجود داخل الزوج القديم تلقائيًا عندما يتغير قاموس distance. الاسم يربط السجل بالعقدة، لكنه لا يحول سجلًا محفوظًا في وقت سابق إلى قراءة حية للقيمة الجديدة.

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

[2]

تجاوز C بسبعة وA بثمانية وT بعشرة

بعد خروج T بقيمة 6، يصل سجل C القديم بقيمة 7 بينما المسافة الحالية لـC تساوي 4. ثم يصل A القديم بثمانية ومسافته الحالية 3، ثم T القديم بعشرة ومسافته الحالية 6. كودنا يسجل popped وcurrent_best وstale، ويتجاوز فحص الجيران عندما لا تتساوى قيمة السجل مع القيمة الحالية.

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

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

عرض الرسم بالحجم الكامل

الوزن غير السالب وسبب اختيار الأصغر

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

في المثال خرج B عند 2 ثم A عند 3 ثم C عند 4 ثم T عند 6. العروض القديمة الأكبر لا تقدم مرشحًا أقصر من العقد التي عولجت بقيمها المطابقة. نحتاج الأوزان واتجاه الانتقال في هذه القراءة؛ لو سمحنا بقيمة سالبة فقد يهبط مجموع طريق لاحق بدل بقائه عند الأقل الذي اعتمدنا عليه.

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

سابق واحد وطريق إلى T بكلفة ستة

السابق المحفوظ لـT هو C، وقبل C توجد A، وقبل A توجد B، وقبل B توجد S. بقراءة هذه الروابط إلى الخلف ثم عكسها نحصل على S ثم B ثم A ثم C ثم T. أوزان الانتقالات هي 2 ثم 1 ثم 1 ثم 2، ومجموعها ستة. الطريق أربع حواف، فلا نسمي المسافة ستة عدد انتقالات.

يمكن أيضًا الوصول إلى T بطريق S ثم A ثم T من حافتين فقط، لكن وزنه 8 زائد 7، أي خمسة عشر. وطريق S ثم B ثم C ثم T ثلاث حواف بكلفة تسعة. المقارنة تبين لماذا لا يكفي اختيار عدد حواف أقل عندما يختلف الوزن. نراجع الهدف الحسابي الذي دخل الدالة بدل قراءة قرب الطريق من عدد رموزه في العرض.

المخرج يحفظ سابقًا واحدًا لكل عقدة وصلت إليها، ولا يعيد جميع المسارات التي قد تتعادل في الكلفة. كما أن روابط السوابق ليست قائمة بكل حواف الرسم. إذا احتاج التقرير بدائل متعددة أو سببًا آخر للتفاضل بينها، يجب تعريف تمثيل مناسب لذلك بدل استنتاجه من سابق مفرد وقاموس مسافات فقط.

الصفر والتعادل وتحسن حقيقي

نسمح بوزن صفر لأنه غير سالب. في مثال مستقل يصل S إلى A بوزن صفر، وA إلى B بصفر، ثم B إلى A بصفر أيضًا. لا يسبب رجوع B إلى A تحديثًا مساويًا جديدًا، لأن المرشح صفر يساوي أفضل مسافة عرفناها لـA. دالتنا تحدث فقط عند كلفة أصغر أو عند الوصول الأول، فتمنع إدخال سجلات مساواة بلا تحسن.

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

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

الكود الأصلي وعقد التصريح بالأوزان

الدالة التالية تتوقع قوائم حواف منتهية لهويات نصية غير فارغة، وكل حافة تحمل جارًا مصرحًا به ووزن int غير سالب. ترفض bool والعشريات في الوزن بدل تحويلهما ضمنيًا، وتراجع البداية قبل حساب المسافات. هذه صياغة تعليمية محددة، وليست كل أنواع الرسوم والقيم التي قد تدعمها مكتبة مسارات عامة.

تستعمل الدالة heapq من Python وتعيد distance وprevious وسجل الإخراج. لا تستدعي NetworkX داخلها؛ نستفيد من توثيق السؤال وحدوده ولا ننسب تجربة مكتبة إلى كود لم يشغلها. نقارن popped بالقيمة الحالية قبل فحص الجيران، ونضيف سجلًا جديدًا فقط حين يقدم المرشح تحسنًا، مع تحديث السابق والمسافة معًا.

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

from heapq import heappush, heappop


def weighted_distances(graph, start):
    adjacency = {node: tuple(edges) for node, edges in graph.items()}
    if any(not isinstance(node, str) or not node for node in adjacency):
        raise ValueError("nonempty text vertices required")
    for edges in adjacency.values():
        for neighbor, weight in edges:
            if neighbor not in adjacency:
                raise ValueError("every neighbor must be declared")
            if type(weight) is not int:
                raise TypeError("integer weights required")
            if weight < 0:
                raise ValueError("nonnegative weights required")
    if start not in adjacency:
        raise KeyError(start)
    distance = {start: 0}
    previous = {start: None}
    waiting = [(0, start)]
    trace = []
    while waiting:
        value, node = heappop(waiting)
        stale = value != distance[node]
        trace.append({"node": node, "popped": value,
                      "current_best": distance[node], "stale": stale})
        if stale:
            continue
        for neighbor, weight in adjacency[node]:
            candidate = value + weight
            if neighbor not in distance or candidate < distance[neighbor]:
                distance[neighbor] = candidate
                previous[neighbor] = node
                heappush(waiting, (candidate, neighbor))
    return {"distance": distance, "previous": previous, "trace": tuple(trace)}

المجهول والسالب وأنواع الأرقام

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

أما G في الأصل فمعروفة لكنها خارج الوصول من S، فلا تظهر في قاموس distance. غيابها ليس مسافة صفرًا أو سجلًا قديمًا جرى حذفه. إذا سأل المستهلك عن هدف غير معروف أيضًا، فعليه مراجعة التصريح بالهوية في الرسم ليفصل بين الحالتين، لأن قاموس العقد الواصلة وحده لا يحفظ كل سبب غياب هدف منه.

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

مرجع استرخاء موزون مستقل

للتحقق من المسافات، نبني مرجعًا آخر يراجع الحواف في جولات من دون استعمال الكومة أو السجلات القديمة. يبدأ بمسافة صفر للمصدر، ثم يقارن كل مرشح معروف على حافة ويحفظ الأصغر. نستعمل عدد جولات يكفي للرسوم الصغيرة غير السالبة التي اخترناها، ثم نقارن جميع المسافات بنتيجة دالتنا، لا بقيمة هدف واحد فقط.

نجرب جميع اختيارات الحواف الموجهة بين ثلاث عقد، بحيث تكون الحافة غائبة أو تحمل 0 أو1 أو3. توجد أربعة آلاف وست وتسعون حالة رسم في هذه التجربة. لا نحول هذا العدد إلى برهان لكل حجم أو مجال وزن، لكنه يشمل دورات صفرية وعقدًا غير واصلة وعروضًا متعددة ضمن بيانات منتهية معلنة.

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

سجل الكومة والنسخة وكلفة الحفظ

في الأصل يخرج S وB وA وC وT بسجلات مطابقة، ثم يخرج C وA وT بقيم قديمة. السجل يحفظ ثمانية إخراجات رغم أن خمس عقد فقط قابلة للوصول. هذا لا يعني أننا ضاعفنا عدد العقد في الرسم أو أن المسافات نفسها تحتاج ثماني نهايات؛ اخترنا حفظ ما خرج من الكومة لشرح التحديث والرفض.

وحجم الكومة قد يشمل سجلات أكثر من عدد العقد لأننا لا نحذف القديم وقت التحسن. كما نحفظ الرسم والمسافات والسوابق والتتبع. لذلك لا نصف البرنامج كله بأنه يستعمل مساحة ثابتة من بساطة شرط stale. لم نقس أداءً على شبكة كبيرة أو نثبت أن هذه الصياغة أسرع عمليًا من كل بديل؛ التقرير يوضح عمليات فعلية في حالاتنا الصغيرة.

وعندما نعرض popped وcurrent_best، نذكر أنهما يخصان لحظة إخراج السجل. القيمة current_best في صف قديم ليست العرض الذي كان قائمًا وقت دخوله قبل التحسين. هذا الفرق الزمني داخل الحساب يساعد المراجع على تفسير ظهور 7 مقابل4 أو8 مقابل3، بدل جعل رقمين من مرحلتين مختلفتين تناقضًا في تعريف المسافة.

بطاقة النتيجة وحدود الطريق

يمكن وصف البطاقة بالمصدر S والأوزان الصحيحة غير السالبة والحواف الموجهة المعلنة، ثم المسافات صفر و2 و3 و4 و6 للمصدر وB وA وC وT. نضيف الطريق S ثم B ثم A ثم C ثم T ومجموعه ستة، ونذكر أن G مصرح بها لكنها غير واصلة. ونحفظ سجلات 7 و8 و10 القديمة مع القيم التي جعلتها تتجاوز.

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

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