ابحث عن دورة أقصر طول في رسم بياني موجه بأوزان إيجابية

Question

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

أشعر بالفضول لمعرفة ما هو الحل الفعال لهذه المشكلة.

Answer 1

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

تقليديا ، تبدأ path[i][i] = 0 لكل i. ولكن يمكنك بدلاً من ذلك البدء من path[i][i] = INFINITY. لن تؤثر على الخوارزمية نفسها ، حيث لم يتم استخدام تلك الأصفار في الحساب على أي حال (منذ المسار path[i][j] لن يتغير أبدا k == i أو k == j).

فى النهاية، path[i][i] هو طول أقصر دورة تمر i. وبالتالي ، تحتاج إلى العثور على min(path[i][i]) للجميع i. وإذا كنت تريد الدورة نفسها (ليس فقط طولها) ، فيمكنك القيام بذلك تمامًا كما تتم عادةً بالمسارات العادية: عن طريق حفظها k أثناء تنفيذ الخوارزمية.

بالإضافة إلى ذلك ، يمكنك أيضًا الاستخدام خوارزمية ديجكسترا للعثور على أقصر دورة تمر عبر أي عقدة معينة. إذا قمت بتشغيل هذا Dijkstra المعدل لكل عقدة ، فستحصل على نفس النتيجة كما هو الحال مع Floyd-Warshall. وبما أن كل dijkstra O(n^2), ، ستحصل على نفس الشيء O(n^3) التعقيد العام.

Answer 2

رمز الزائفة هو تعديل بسيط لخوارزمية Dijkstra.

for all u in V:
   for all v in V:
      path[u][v] = infinity

for all s in V:
   path[s][s] = 0
   H = makequeue (V) .. using pathvalues in path[s] array as keys
   while H is not empty:
      u = deletemin(H)
      for all edges (u,v) in E:
         if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
            path[s][v] = path[s][u] + l(u,v)
         decreaseKey(H, v)

lengthMinCycle = INT_MAX

for all v in V:
   if path[v][v] < lengthMinCycle & path[v][v] != 0 :
      lengthMinCycle = path[v][v]

if lengthMinCycle == INT_MAX:
   print(“The graph is acyclic.”)

else:
   print(“Length of minimum cycle is ”, lengthMinCycle)

تعقيد الوقت: O (| V |^3)

Answer 3

• أداء DFS
• أثناء DFS ، تابع مسار نوع الحافة
• نوع الحواف Tree Edge, Back Edge, Down Edge و Parent Edge
• تتبع عندما تحصل على ملف Back Edge والحصول على عداد آخر للحصول على الطول.

نرى Algorithms in C++ Part5 - Robert Sedgwick لمزيد من التفاصيل

Answer 4

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

Answer 5

يمكننا أيضًا استخدام Branch and Bound Logorithm لمشكلة البائع المتجول ، حيث يتطابق سؤالك مع TSP.http://lcm.csa.iisc.ernet.in/dsa/node187.html

Answer 6

فيما يلي تعديل بسيط لخوارزمية Floyd - Warshell.

V = 4
INF = 999999


DEF MINIMMYCLELELLENG (الرسم البياني): dist = [[[0]*v for I في النطاق (V)] بالنسبة لـ I في النطاق (V): لـ J في النطاق (V): dist [i] [j] = الرسم البياني [i] [J] ؛ بالنسبة إلى k في النطاق (v): لأني في النطاق (v): بالنسبة إلى j في النطاق (v): dist [i] [j] = min (dist [i] [j] ، dist [i] [k]+ dist [k] [j]) length = inf for i in range (v): for j in range (v): length = min (length ، dist [i] [j]) طول الإرجاع

graph = [ [INF, 1, 1,INF],
        [INF, INF, 1,INF],
        [1, INF, INF, 1],
        [INF, INF, INF, 1] ]
length = minimumCycleLength(graph)
print length