The Floyd-Warshall algorithm is a widely used algorithm in graph theory and computer science for finding the shortest paths between all pairs of vertices in a weighted graph. It is named after its inventors, Robert Floyd and Stephen Warshall, who independently proposed it in the early 1960s.
The algorithm works on both directed and undirected graphs, where edges have non-negative weights (can be zero or positive but not negative). The goal is to find the shortest path distance between all pairs of vertices in the graph.
Floyd-Warshall and Dijkstra's algorithm are both used to find the shortest paths in a graph, but they serve different purposes and have different use cases.
They are not direct alternatives to each other; rather, they are used in different scenarios based on the problem requirements and the characteristics of the graph.
open Graphoscope
open Cytoscape.NET
let dwgDiGraph =
let nodes = [|0;1;2;3;4;5|]|>Array.map(fun x -> x,x)
let edges = [|0,1,7.;0,2,12.;1,2,2.;1,3,9.;2,4,10.;4,3,4.;3,5,1.;4,5,5.|]
DiGraph.createFromNodes nodes
|>DiGraph.addEdges edges
let dijDiGraph = Algorithms.FloydWarshall.fromJaggedArray (DiGraph.toMatrix dwgDiGraph)
namespace Graphoscope
namespace Cytoscape
namespace Cytoscape.NET
val dwgDiGraph: DiGraph<int,int,float>
val nodes: (int * int)[]
module Array
from Microsoft.FSharp.Collections
<summary>Contains operations for working with arrays.</summary>
<remarks>
See also <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/arrays">F# Language Guide - Arrays</a>.
</remarks>
val map: mapping: ('T -> 'U) -> array: 'T[] -> 'U[]
<summary>Builds a new array whose elements are the results of applying the given function
to each of the elements of the array.</summary>
<param name="mapping">The function to transform elements of the array.</param>
<param name="array">The input array.</param>
<returns>The array of transformed elements.</returns>
<exception cref="T:System.ArgumentNullException">Thrown when the input array is null.</exception>
<example id="map-1"><code lang="fsharp">
let inputs = [| "a"; "bbb"; "cc" |]
inputs |> Array.map (fun x -> x.Length)
</code>
Evaluates to <c>[| 1; 3; 2 |]</c></example>
val x: int
val edges: (int * int * float)[]
Multiple items
module DiGraph
from Graphoscope
--------------------
type DiGraph =
new: unit -> DiGraph
static member addEdge: edge: ('NodeKey * 'NodeKey * 'EdgeData) -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member addEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member addElement: nk1: 'NodeKey -> nd1: 'NodeData -> nk2: 'NodeKey -> nd2: 'NodeData -> ed: 'EdgeData -> g: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member addNode: nodeKey: 'NodeKey -> nodeData: 'NodeData -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member addNodes: nodes: ('NodeKey * 'NodeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member countEdges: graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> int (requires comparison)
static member countNodes: graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> int (requires comparison)
static member createFromEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> DiGraph<'NodeKey,'NodeKey,'EdgeData> (requires comparison)
static member createFromNodes: nodes: ('NodeKey * 'NodeData)[] -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
...
--------------------
type DiGraph<'NodeKey,'NodeData,'EdgeData (requires comparison)> =
new: unit -> DiGraph<'NodeKey,'NodeData,'EdgeData>
--------------------
new: unit -> DiGraph
--------------------
new: unit -> DiGraph<'NodeKey,'NodeData,'EdgeData>
static member DiGraph.createFromNodes: nodes: ('NodeKey * 'NodeData)[] -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
static member DiGraph.addEdges: edges: ('NodeKey * 'NodeKey * 'EdgeData)[] -> graph: DiGraph<'NodeKey,'NodeData,'EdgeData> -> DiGraph<'NodeKey,'NodeData,'EdgeData> (requires comparison)
val dijDiGraph: float[][]
namespace Graphoscope.Algorithms
Multiple items
type FloydWarshall =
new: unit -> FloydWarshall
static member compute: unit -> int
static member fromArray2D: graph: float[,] -> float[,]
static member fromJaggedArray: graph: float[][] -> float[][]
<summary>
Computes all-pairs shortest paths for a given graph using Floyd-Warshall algorithm.
The ordered array of nodes and 2D Array of distances where each
row and column index corresponds to a node's index in the nodes array.
</summary>
--------------------
new: unit -> Algorithms.FloydWarshall
static member Algorithms.FloydWarshall.fromJaggedArray: graph: float[][] -> float[][]