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

الخلاصة السريعة

في مثالنا تعالج الرؤوس بترتيب A ثم B ثم D ثم C. تعطي معالجة B قيمة 4 إلى D. وعند معالجة C تظهر قيمة 1 إلى B عبر A→C→B، لكن B لا يعالج ثانية، فلا تنتقل هذه القيمة إلى D. الطريق A→C→B→D مجموعه 5 − 4 + 2 = 3، وهو أصغر من 4. الرسم بلا دورة؛ غياب الدورة وحده لا يحل المشكلة.

• تعالج ديكسترا مسألة أقصر الطرق من بداية محددة مع أوزان حواف غير سالبة؛ الصفر مسموح. اختيار الرأس غير المعالج ذي أقل قيمة معروفة يتيح تثبيت قيمته تحت هذا الشرط. [1]
• نبدأ من A، وحوافنا A→B بوزن 2، و A→C بوزن 5، و C→B بوزن−4، و B→D بوزن 2 فقط. الأوزان مجردة، ولا توجد دورة أو حواف عكسية تلقائية.
• في التتبع الذي يعالج كل رأس مرة، يأتي الترتيب A ثم B ثم D ثم C. تخفض C القيمة المسجلة إلى B من 2 إلى 1 بعد معالجته؛ وتبقى القيمة إلى D عند 4 لأننا لا نعالج B ثانية.
• إلى D يوجد طريقان فقط:A→B→D بمجموع 2 + 2 = 4، و A→C→B→D بمجموع 5 − 4 + 2 = 3. لذلك الأقل 3، رغم نتيجة التتبع 4.
• إذا غيرنا C→B إلى 0، صار الطريق عبر C إلى D بمجموع 7، وبقي الأفضل 4. وإذا صار الوزن−1، صار ذلك الطريق 6، وبقي الأفضل 4 أيضًا. قد ينجح مثال ذو حافة سالبة، لكن هذا لا يعيد شرط الأوزان غير السالبة.
• إضافة E بلا حواف تجعله غير قابل للوصول من A؛ لا نعطيه قيمة 0. كما أن كون الرسم الأصلي بلا دورة لا يجعل نتيجته 4 صحيحة. افحص الأوزان وطريقة المعالجة، ولا تستبدل شرطًا بآخر.

ثبت معنى الوزن والبداية وطريقة المعالجة

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

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

رؤوس المثال A و B و C و D. نبدأ من A، والحواف الوحيدة A→B بوزن 2، و A→C بوزن 5، و C→B بوزن−4، و B→D بوزن 2. نحسب وزن الطريق بجمع أوزان حوافه، ونبحث عن الأقل مجموعًا، لا الأقل عددًا من الأسهم.

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

تتبع ما يحدث عندما تعالج B قبل C

قبل أي معالجة قيمة A تساوي 0، وبقية القيم∞. بعد معالجة A، تسجل A→B القيمة 2، وتسجل A→C القيمة 5، وتبقى D عند∞. الرأس غير المعالج صاحب أصغر قيمة هو B عند 2، لذا يأتي دوره.

من B نفحص B→D بوزن 2، فنسجل إلى D مقدار 2 + 2 = 4. أصبحت القيمتان المرشحتان للرأسين غير المعالجين D عند 4 و C عند 5. نختار D أولًا لأنه الأقل. ولا تخرج من D أي حافة لتغير سجلًا آخر.

بعد ذلك نعالج C وقيمته 5. الحافة C→B بوزن−4 تعطي 5 − 4 = 1، وهي أصغر من القيمة السابقة 2 إلى B. نحدث سجل B إلى 1، لكن B سبق أن عولج ولا نعالجه مرة ثانية في هذه النسخة، فلا نفحص B→D انطلاقًا من 1.

يعرض الجدول السجلات بعد كل معالجة. ترتيب A و B و D و C لا يتضمن تعادلًا في القيم عند الاختيار. تنتهي سجلات B و C و D بالقيم 1 و 5 و 4؛ تحسن B المتأخر لا يعني أن كل السجلات الأخرى حصلت على ذلك التحسن.

احصر الطرق الفعلية لتعرف أن 3 هي الأقل

من A إلى B يوجد طريق مباشر A→B وزنه 2، وطريق A→C→B وزنه 5 − 4 = 1. ومن A إلى C لا يوجد سوى A→C بوزن 5. لا توجد حواف أخرى يمكن أن تولد طرقًا إضافية أو عودة إلى بداية سابقة.

إلى D يجب المرور بـ B، لأن الحافة الداخلة الوحيدة إليه B→D. إذن الطريقان هما A→B→D بوزن 2 + 2 = 4، و A→C→B→D بوزن 5 − 4 + 2 = 3. حصر الطريقين ومقارنة 3 و 4 يثبت أن الأقل 3.

الجدول يسجل كل طريق متاح إلى كل وجهة غير A وأقل وزن. الصورة الداخلية تميز A→C→B→D باعتباره الطريق الأقل إلى D، وتبقي A→B باهتًا كخيار أصلي غير داخل في هذا الطريق. الأوزان لم تتغير بين الصورتين.

موضع الخلل محدد: تحسين B من 2 إلى 1 يتطلب نقل الأثر عبر B→D حتى تتحسن D من 4 إلى 3. التتبع المعلن لا يفعل ذلك لأنه لا يعود لمعالجة B. ولو استخرجنا طريقًا من سجلات سابقة تتحسن لاحقًا، فلا يكفي ذلك لتصديق الرقم 4؛ نراجع مجموع حواف الطريق نفسه.

الصفر مسموح، والحافة السالبة لا تفشل كل مثال

في تعديل مستقل نجعل وزن C→B يساوي 0، ونترك بقية الأوزان 2 و 5 و 2 كما هي. الطريق A→C→B يصبح 5، فلا يحسن A→B ذي الوزن 2. وإلى D يصبح الطريق عبر C بمجموع 5 + 0 + 2 = 7، بينما الطريق عبر B مباشرة مجموع 4. يعطي التتبع 4، وهي الأقل فعلًا.

الصفر يحقق شرط الأوزان غير السالبة. اشتراط أن تكون كل الأوزان أكبر من 0 يستبعد هذه الحالة دون حاجة؛ غير السالب لا يعني الموجب حصرًا.

وفي تعديل آخر نجعل C→B يساوي−1. يصبح الطريق A→C→B وزنه 5 − 1 = 4، فلا يحسن القيمة 2. وإلى D يصبح الطريق عبر C بمجموع 5 − 1 + 2 = 6، فيبقى الطريق A→B→D ذو الوزن 4 هو الأقل. ينجح التتبع في هذا المثال المعدل رغم وجود حافة سالبة.

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

الرأس غير المتاح وغياب الدورة سؤالان مختلفان

إذا أضفنا E بلا حواف إلى الرسم الأصلي، فلن يوجد طريق من A إلى E. يبدأ سجل E عند∞ ويبقى كذلك، ويمكن التوقف عند عدم وجود رأس غير معالج ذي قيمة منتهية. [1]

الرمز∞ يميز عدم وجود قيمة طريق متاحة هنا؛ لا يعني أن الرأس E يبعد صفرًا عن A، ولا يعطي وزنًا حقيقيًا نقيسه. إضافة E لا تصلح الخطأ إلى D؛ الطريق إلى D ذو الوزن 3 ما زال موجودًا في الحواف الأصلية.

ولا نحتاج إلى دورة سالبة لكي يحدث الخطأ الذي شرحناه. رسمنا بلا أي دورة، لكن C→B خفض قيمة B بعد معالجته. ترتيب الرؤوس واتجاه الأسهم ووجود الحافة السالبة كافٍ لإظهار ذلك في الأرقام المعلنة.

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