خوارزمية سايدل

خوارزمية سايدل هي خوارزمية صممها رايموند سايدل عام 1992 لحل مشكلة أقصر مسار بين جميع الأزواج في الرسوم البيانية غير الموجهة وغير الموزونة والمتصلة. ^{[ 1 ]} وهي تحل المشكلة في${\displaystyle O(V^{\omega }\log V)}$الوقت المتوقع لرسم بياني مع${\displaystyle V}$الرؤوس، حيث${\displaystyle \omega <2.373}$هو الأس في التعقيد${\displaystyle O(n^{\أوميغا })}$ل${\displaystyle n\times n}$ضرب المصفوفات . إذا اقتصر البحث على المسافات بين كل زوج من الرؤوس، فيمكن تحقيق نفس الحد الزمني في أسوأ الحالات. على الرغم من أن الخوارزمية مصممة للرسوم البيانية المتصلة، إلا أنه يمكن تطبيقها بشكل فردي على كل مكون متصل من الرسم البياني بنفس وقت التشغيل الإجمالي. هناك استثناء لوقت التشغيل المتوقع المذكور أعلاه لحساب المسارات: إذا${\displaystyle \omega =2}$يصبح وقت التشغيل المتوقع${\displaystyle O(V^{2}\log ^{2}V)}$.

جوهر الخوارزمية هو إجراء يحسب طول أقصر المسارات بين أي زوج من الرؤوس. في أسوأ الحالات، يمكن القيام بذلك في${\displaystyle O(V^{\omega }\log V)}$بعد حساب الأطوال، يمكن إعادة بناء المسارات باستخدام خوارزمية لاس فيغاس التي يُتوقع أن يكون وقت تشغيلها هو${\displaystyle O(V^{\omega }\log V)}$ل${\displaystyle \omega >2}$و${\displaystyle O(V^{2}\log ^{2}V)}$ل${\displaystyle \omega =2}$.

دالة apd ( A , n : int ): """حساب أطوال أقصر المسارات.""" إذا كان كل ( A [ i ][ j ] لـ i في النطاق ( n ) لـ j في النطاق ( n ) إذا كان i != j ): إرجاع A Z = A ** 2 B = matrix ( [ [ 1 إذا كان i != j و ( A [ i ][ j ] == 1 أو Z [ i ][ j ] > 0 ) وإلا 0 لـ j في النطاق ( n )] لـ i في النطاق ( n ) ] ) T = apd ( B , n ) X = T * A degree = [ sum ( A [ i ][ j ] لـ j في النطاق ( n )) لـ i في النطاق ( n )] D = matrix ( [ [ 2 * T [ i ][ j ] إذا كان X [ i ][ j ] >= T [ i ][ j ] * degree [ j ] وإلا 2 * T [ i ][ j ] - 1 لـ j في النطاق ( n ) ] لـ i في النطاق ( ن ) ] ) إرجاع D

خوارزميات للرسوم البيانية غير الموجهة والموجهة ذات الأوزان من مجموعة محدودة${\displaystyle \{1,\ldots ,M,+\infty \}}$توجد أيضًا خوارزمية أخرى. أفضل خوارزمية معروفة للحالة الموجهة هي تلك التي تعمل في وقت محدد.${\displaystyle {\tilde {O}}(M^{1/(4-\أوميغا )}V^{2+1/(4-\أوميغا )})}$بواسطة زويك عام ١٩٩٨. ^{[ ٢ ]} تستخدم هذه الخوارزمية ضرب المصفوفات المستطيلة بدلاً من ضرب المصفوفات المربعة . يمكن الحصول على حدود عليا أفضل باستخدام أفضل خوارزمية متاحة لضرب المصفوفات المستطيلة بدلاً من تحقيق الضرب المستطيل عبر عمليات ضرب متعددة للمصفوفات المربعة. أفضل خوارزمية معروفة للحالة غير الموجهة هي في وقت${\displaystyle {\tilde {O}}(MV^{\omega })}$بواسطة شوشان وزويك في عام 1999. ^{[ 3 ]} كان التنفيذ الأصلي لهذه الخوارزمية خاطئًا وتم تصحيحه بواسطة إيريناكيس وويليامسون وسوبراماني في عام 2016. ^{[ 4 ]}