Algorithms that find the cheapest route between vertices of a weighted graph, such as Bellman-Ford, Floyd-Warshall, Johnson's algorithm, Yen's algorithm and Suurballe's algorithm. An algorithm belongs here when its cited article says it computes shortest paths. It excludes spanning tree and flow algorithms, which have their own groups. A member is placed here by what its own cited article states about it, not by the name of the algorithm or by the uses it is put to today, so each entry sits in the group its source describes it as belonging to.
All Shortest Path Algorithms
Filter Results6 entries
Sources
Warshall's Algorithm (Wikipedia)
Has Member: Warshall's Algorithm, LeadQuote, Has Member: Warshall's Algorithm, Lead
is an algorithm for finding shortest paths in a directed weighted graph
Wikipedia, Bellman-Ford algorithm
Has Member: Bellman-Ford Algorithm, Lead sectionQuote, Has Member: Bellman-Ford Algorithm, Lead section
computes shortest paths from a single source vertex
Wikipedia: Johnson's Algorithm
Wikimedia FoundationHas Member: Johnson's Algorithm, Lead sectionQuote, Has Member: Johnson's Algorithm, Lead section
find the shortest paths between all pairs of vertices
Wikipedia: Yen's algorithm
Has Member: Yen's Algorithm, Lead sectionQuote, Has Member: Yen's Algorithm, Lead section
computes single-source K-shortest loopless paths
Suurballe's Algorithm (Wikipedia)
Has Member: Suurballe's Algorithm, Lead sectionQuote, Has Member: Suurballe's Algorithm, Lead section
finding two disjoint paths in a nonnegatively-weighted directed graph
Wikipedia, Floyd-Warshall algorithm
Has Member: Floyd-Warshall Algorithm, LeadQuote, Has Member: Floyd-Warshall Algorithm, Lead
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).
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.