Click or drag to resize
FloydWarshall Class

The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.

This implementation uses the Floyd-Warshall algorithm. The constructor takes time proportional to V3 in the worst case, where V is the number of vertices. Afterwards, the Dist(), HasPath(), and HasNegativeCycle() methods take constant time; the Path() and GetNegativeCycle() method takes time proportional to the number of edges returned.

Inheritance Hierarchy
SystemObject
  Algs4NetFloydWarshall

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
C#
Copy
public class FloydWarshall

The FloydWarshall type exposes the following members.

Constructors
  NameDescription
Public methodFloydWarshall
Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G. If no such shortest path exists for some pair of vertices, it computes a negative cycle.
Top
Properties
  NameDescription
Public propertyHasNegativeCycle
Is there a negative cycle?
Top
Methods
  NameDescription
Public methodDist
Returns the length of a shortest path from vertex s to vertex t.
Public methodHasPath
Is there a path from the vertex s to vertex t?
Public methodStatic memberMainTest
Demo test the FloydWarshall data type.
Public methodNegativeCycle
Returns a negative cycle, or null if there is no such cycle.
Public methodPath
Returns a shortest path from vertex s to vertex t.
Top
Remarks

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

This class is a C# port from the original Java class FloydWarshall implementation by the respective authors.

See Also