FloydWarshall.cs

usingSystem;
usingDataStructures.Graph;

namespaceAlgorithms.Graph;

/// <summary>
/// Floyd Warshall algorithm on directed weighted graph.
/// </summary>
/// <typeparam name="T">generic type of data in graph.</typeparam>
publicclassFloydWarshall<T>
{
/// <summary>
/// runs the algorithm.
/// </summary>
/// <param name="graph">graph upon which to run.</param>
/// <returns>
/// a 2D array of shortest paths between any two vertices.
/// where there is no path between two vertices - double.PositiveInfinity is placed.
/// </returns>
publicdouble[,]Run(DirectedWeightedGraph<T>graph)
{
vardistances=SetupDistances(graph);
varvertexCount=distances.GetLength(0);
for(vark=0;k<vertexCount;k++)
{
for(vari=0;i<vertexCount;i++)
{
for(varj=0;j<vertexCount;j++)
{
distances[i,j]=distances[i,j]>distances[i,k]+distances[k,j]
?distances[i,k]+distances[k,j]
:distances[i,j];
}
}
}

returndistances;
}

/// <summary>
/// setup adjacency matrix for use by main algorithm run.
/// </summary>
/// <param name="graph">graph to dissect adjacency matrix from.</param>
/// <returns>the adjacency matrix in the format mentioned in Run.</returns>
privatedouble[,]SetupDistances(DirectedWeightedGraph<T>graph)
{
vardistances=newdouble[graph.Count,graph.Count];
for(inti=0;i<distances.GetLength(0);i++)
{
for(varj=0;j<distances.GetLength(0);j++)
{
vardist=graph.AdjacentDistance(graph.Vertices[i]!,graph.Vertices[j]!);
distances[i,j]=dist!=0?dist:double.PositiveInfinity;
}
}

for(vari=0;i<distances.GetLength(0);i++)
{
distances[i,i]=0;
}

returndistances;
}
}