Floyd-Warshall Algorithm

The Floyd-Warshall algorithm, also variously known as Floyd's algorithm, the Roy-Floyd algorithm, the Roy-Warshall algorithm, or the WFI algorithm, is an algorithm for efficiently and simultaneously finding the shortest paths (i.e., graph geodesics) between every pair of vertices in a weighted and potentially directed graph.

The Floyd algorithm is essentially equivalent to the transitive closure algorithm independently discovered by Roy (1959) and Warshall (1962) (Pemmaraju and Skiena 2003), which is the reason it is associated with all three authors.

In Season 4 episode "Black Swan" of the television crime drama NUMB3RS, mathematical genius Charles Eppes proposed using the Floyd-Warshall algorithm to analyze the most recent destinations of a bombing suspect.

---

REFERENCES

Atallah, M. J. (Ed.). "Basic Graph Algorithms." Ch. 6 in Algorithms and Theory of Computation Handbook. Boca Raton, FL: CRC Press, 1998.

Floyd, R. W. "Algorithm 97." Comm. ACM 5-6, 345, 1962.

Larson, R. and Odoni, A. "Shortest Paths between All Pairs of Nodes." §6.2.2 in Urban Operations Research. 1981. http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html.

Loerch, U. "Floyd's Algorithm." Auckland, New Zealand: Dept. Computer Science, University of Auckland, 2000. http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node21.html.

Pemmaraju, S. and Skiena, S. "All-Pairs Shortest Paths" and "Transitive Closure and Reduction." §8.1.2 §8.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 330-331 and 353-356, 2003.

Preiss, B. "Floyd's Algorithm." in Data Structures and Algorithms with Object-Oriented Design Patterns in Java. 1998. http://www.brpreiss.com/books/opus5/html/page570.html.Roy, B. "Transitivité et connexité." C. R. Acad. Sci. Paris 249, 216-218, 1959.

Warshall, S. "A Theorem on Boolean Matrices." J. ACM 9, 11-12, 1962.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشعائر يواصل تحضيراته لتنظيم عمل المواكب الحسينية في زيارة الأربعين

قسم شؤون المعارف يناقش تحضيرات المؤتمر العلمي الأول لمركز تراث البصرة

قسم الشؤون الفكرية يقيم دورة تطويرية لملاكات هيأة المساءلة والعدالة في الأرشفة الإلكترونية

المجمع العلمي ينظم مجلس عزاء في قضاء الهندية

المزيد

الآخبار الصحية

نصائح عملية للحد من التعرق المفرط في الصيف

أطباء يحذرون: مكمل غذائي شائع قد يدمر الجهاز العصبي

تحذير طبي من تأثير جانبي "غير متوقع" لحقن التخسيس

حمامات الثلج قد تكون خطيرة وأحيانا مميتة.. ما السبب؟

المزيد

الآخبار التكنلوجية

أكبر جدارية شمسية في العالم تدخل موسوعة غينيس.. مشروع ضخم

تسارع دوران الأرض يثير القلق.. وتحذيرات من "كوارث محتملة" ؟

"سوذبيز" تطرح أكبر قطعة من المريخ على الأرض في مزاد علني

أوبن أيه آي تعتزم إطلاق متصفح إنترنت يعمل بالذكاء الاصطناعي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength