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.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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