استخدام dijkstra في العثور على الحد الأدنى شجرة الامتداد؟

Question

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

تحرير: هذا ليس واجب منزلي، لكنني أحاول فهم سؤال في امتحان ممارسة قديمة.

Answer 1

بدقة، الجواب لا. يجد خوارزمية Dijkstra أقصر مسار بين 2 قمة على الرسم البياني. ومع ذلك، فإن التغيير الصغير جدا في الخوارزمية ينتج خوارزمية أخرى تقوم بتنصي فعال ب MST.

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

Answer 2

الجواب لا. لمعرفة لماذا، دعونا أولا التعبير عن السؤال مثل ذلك:

س: للحصول على رسم بياني متصل وغير مسبهب G = (V, E, w) مع أوزان الحافة غير الوحيدة، هل شكل البريد الفصغر أعلاه من قبل خوارزمية Dijkstra تشكل شجرة الامتداد الحد الأدنى من ز؟

(لاحظ أن الرسوم البيانية غير المعجلة هي فئة خاصة من الرسوم البيانية الموجه الموجهة، لذلك فهي موافق تماما لاستخدام خوارزمية Dijkstra على الرسوم البيانية غير المعجزة. علاوة على ذلك، يتم تعريف MST فقط للرسوم البيانية المتصلة غير المعجزة، وهي تافهة إذا كان الرسم البياني غير مرجح، لذلك نحن يجب تقييد استفسارنا لهذه الرسوم البيانية.)

أ: خوارزمية dijkstra في كل خطوة، يختار الجشع الحافة التالية الأقرب إلى بعض المصدر Vertex S.. وبعد هل هذا حتى يتم توصيل S إلى كل قمة أخرى في الرسم البياني. من الواضح أن السلف الفرعي الذي يتم إنتاجه هو شجرة ممتد G, ، ولكن هل مجموع الأوزان الحافة تصغير؟

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

عكس ذلك: النظر في الرسم البياني غير المعالج G = (V, E, w) أين

V = { a, b, c, d }

E = { (a,b), (a,c), (a,d), (b,d), (c,d) }

w = { ( (a,b) , 5 ) ( (a,c) , 5 ) ( (a,d) , 5 ) ( (b,d) , 1 ) ( (c,d) , 1 ) }

يأخذ a كمصدر قمة.

خوارزمية Dijkstra تأخذ الحواف { (a,b), (a,c), (a,d) }.
وبالتالي، فإن الوزن الكلي لهذه الشجرة الممتدة 5 + 5 + 5 = 15.

خوارزمية بريم تأخذ الحواف { (a,d), (b,d), (c,d) }.
وبالتالي، فإن الوزن الكلي لهذه الشجرة الممتدة 5 + 1 + 1 = 7.

Answer 3

خوارزمية بريم يستخدم نفس المبدأ الأساسي مثل خوارزمية Dijkstra.

Answer 4

سأظل في خوارزمية جشعة مثل Prime's أو Kruskal. أخشى أن Djikstra لن تفعل ذلك، ببساطة لأنه يقلل من التكلفة بين أزواج العقد، وليس للشجرة بأكملها.

Answer 5

بالطبع، من الممكن استخدام Dijkstra لأقل من الأشجار الممتدة:

dijsktra(s):
dist[s] = 0;
while (some vertices are unmarked) {
    v = unmarked vertex with 
    smallest dist;
    Mark v; // v leaves “table”
    for (each w adj to v) {
        dist[w] = min[ dist[w], dist[v] + c(v,w) ];
    }
}

هنا مثال على استخدام Dijkstra للممتدغة:

يمكنك العثور على مزيد من التفسير في أسس كتاب الخوارزميات، الفصل 4، القسم 2.

نأمل أن تكون هذه المساعدة