Floyd–Warshall algorithm

In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph.

Class: All-pairs shortest path problem
Comment: enIn computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph.
Data: Graph (data structure)
Depiction
Has abstract: enIn computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph.
Is primary topic of: Floyd–Warshall algorithm
Label: enFloyd–Warshall algorithm
Link from a Wikipage to an external page: docs.juliahub.com/Graphs/VJ6vx/1.7.0/algorithms/shortestpaths/%23Graphs.floyd_warshall_shortest_paths-Union%7BTuple%7BAbstractGraph%7BU%7D%7D,%20Tuple%7BT%7D,%20Tuple%7BU%7D,%20Tuple%7BAbstractGraph%7BU%7D,%20AbstractMatrix%7BT%7D%7D%7D%20where%20%7BU%3C:Integer,%20T%3C:Real%7D; www.mathworks.com/matlabcentral/fileexchange/10922; www.nuget.org/packages/QuickGraphPCL/3.6.61114.2; metacpan.org/module/Graph; commons.apache.org/sandbox/commons-graph/; www.boost.org/libs/graph/doc/; cran.r-project.org/web/packages/Rfast/index.html; cran.r-project.org/web/packages/e1071/index.html; www-m9.ma.tum.de/graph-algorithms/spp-floyd-warshall/index_en.html; www.codeplex.com/quickgraph; docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html%23scipy.sparse.csgraph.floyd_warshall; www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html%23visualization
Link from a Wikipage to another Wikipage: Adjacency matrix; Algorithm; All-pairs shortest path problem; Bernard Roy; Big theta; C++; Category:Articles with example pseudocode; Category:Dynamic programming; Category:Graph algorithms; Category:Graph distance; Category:Polynomial-time problems; Category:Routing algorithms; Computational complexity theory; Computer science; C Sharp (programming language); Cycle (graph theory); Cytoscape; Dense graph; Deterministic finite automaton; Dijkstra's algorithm; Dynamic programming; Fast matrix multiplication; Fibonacci heap; File:Floyd-Warshall example.svg; Finite automaton; Gauss–Jordan elimination; Graph (data structure); Invertible matrix; Java (programming language); JavaScript; Johnson's algorithm; Julia (programming language); Kleene's algorithm; Logical conjunction; Logical disjunction; MATLAB; Matrix (mathematics); NetworkX; Pathfinder network; Perl; Programming language; Python (programming language); Real number; Recursion; Regular expression; Regular language; Robert W. Floyd; R programming language; Schulze method; SciPy; Shortest path problem; Shortest-path tree; Sparse graph; Stephen Warshall; Transitive closure; Weighted graph; Widest path problem
SameAs: 8mfF; Algorithme de Floyd-Warshall; Algorithmus von Floyd und Warshall; Algoritma Floyd-Warshall; Algoritmo de Floyd-Warshall; Algoritmo de Floyd-Warshall; Algoritmo di Floyd-Warshall; Algorytm Floyda-Warshalla; Floydův–Warshallův algoritmus; Floyd-Warshall algoritması; Floyd–Warshall-algoritmus; Floyd-Warshall算法; m.01hj8z; Q1047576; Q25420208; Thuật toán Floyd–Warshall; Алгоритм Воршала; Алгоритм Флойда — Воршелла; Алгоритм Флойда — Уоршелла; Флојд-Воршалов алгоритам; אלגוריתם פלויד-וורשאל; الگوریتم فلوید-وارشال; خوارزمية فلويد-مارشل; ফ্লয়েড ওয়ারশ্যালের অ্যালগরিদম; ขั้นตอนวิธีของฟลอยด์-วอร์แชล; ワーシャル–フロイド法; 플로이드-워셜 알고리즘
Subject: Category:Articles with example pseudocode; Category:Dynamic programming; Category:Graph algorithms; Category:Graph distance; Category:Polynomial-time problems; Category:Routing algorithms
Thumbnail
WasDerivedFrom: Floyd–Warshall algorithm?oldid=1113259725&ns=0
WikiPageLength: 22363
Wikipage page ID: 230401
Wikipage revision ID: 1113259725
WikiPageUsesTemplate: Template:Clear; Template:Commons category; Template:Infobox Algorithm; Template:Math; Template:Mvar; Template:Optimization algorithms; Template:Redirect; Template:Reflist; Template:Short description; Template:Tree search algorithm; Template:Uncited section

Floyd–Warshall algorithm

Backlinks

About

Resources

Support

Follow us