Class FloydWarshall

java.lang.Object

topics.dynamic.floyd.FloydWarshall

public class FloydWarshall
extends Object

Floyd-Warshall (All-Pairs Shortest Path)

Computes the shortest paths between all pairs of nodes in a directed graph using Dynamic Programming.

Relaxation Process

The algorithm performs n iterations. In each iteration k, it checks for every pair (i, j) if passing through node k offers a shorter path than the one currently known.

• Time Complexity: O(N³)
• Space Complexity: O(N²)

Author:

vicegd

Field Summary

Fields

Modifier and Type	Field	Description
static final int	INF

Constructor Summary

Constructors

Constructor	Description
FloydWarshall()

Method Summary

Modifier and Type	Method	Description
void	compute(int[][] dist, int[][] next)	Executes the Floyd-Warshall algorithm.
String	reconstructPath(int[][] next, int i, int j, String[] nodeNames)	Recursively reconstructs the shortest path between two nodes.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

INF

public static final int INF

See Also:

• Constant Field Values

Constructor Details

FloydWarshall

public FloydWarshall()

Method Details

compute

public void compute(int[][] dist,
 int[][] next)

Executes the Floyd-Warshall algorithm.

Parameters:

dist - Distance matrix. Will be updated with minimum path costs.

next - Predecessor matrix to reconstruct the paths.

reconstructPath

public String reconstructPath(int[][] next,
 int i,
 int j,
 String[] nodeNames)

Recursively reconstructs the shortest path between two nodes.

Parameters:

next - Predecessor matrix.

i - Source node index.

j - Destination node index.

nodeNames - Array of node identifiers.

Returns:

Formatted string representing the optimal path.