41. الرسوم البيانية الموزونة ومشكلة أقصر مسار

في العديد من سيناريوهات العالم الحقيقي، ترتبط الحواف في الرسم البياني بتكاليف مصاحبة (أوزان). مشكلة أقصر مسار حاسمة هنا.

التعريف

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

لماذا يفشل BFS هنا

تذكر أن BFS تجد أقصر مسار من حيث عدد الحواف. في الرسم البياني الموزون، لا يعني وجود عدد أقل من الحواف أن المسار 'أقصر' (أرخص). قد يكون مسار بثلاث حواف قصيرة أرخص من مسار بحافتين طويلتين جداً.

نحن بحاجة إلى خوارزميات متخصصة تأخذ الأوزان في الحسبان، مثل خوارزمية Dijkstra's.