English
English
In graph theory, the shortest path problem is a classic algorithmic problem that involves finding the shortest path between two vertices in a directed or undirected graph. The Floyd-Warshall algorithm is a classic dynamic programming algorithm used to solve this problem. This article will explain how to implement the Floyd-Warshall algorithm in PHP in detail.
The Floyd-Warshall algorithm is an algorithm that solves the shortest path problem by iteratively comparing the shortest path lengths between all pairs of vertices in a graph. It uses a two-dimensional array to store the shortest path lengths between vertices, updating this array with each iteration. Eventually, we can obtain the shortest paths between all vertices.
First, we need to create an N x N two-dimensional array, where N is the number of vertices in the graph. Each element of the array represents the distance between two vertices. If there is no edge between two vertices, the distance is set to infinity. Here's the PHP code implementation:
function floydWarshall($graph) {
$n = count($graph);
$dist = $graph;
for ($k = 0; $k < $n; $k++) {
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($dist[$i][$k] + $dist[$k][$j] < $dist[$i][$j]) {
$dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j];
}
}
}
}
return $dist;
}
Next, we define an example graph to test our algorithm. We use an adjacency matrix to represent the structure of the graph, storing the distances between vertices in a two-dimensional array. Here's the example code:
$graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
];
In the example graph above, INF represents no edge between two vertices, and we assign it a very large value. Now, we can call the floydWarshall function to compute the shortest path array.
$result = floydWarshall($graph);
Running the code above will yield the following results:
0 5 8 9 INF 0 3 4 INF INF 0 1 INF INF INF 0
The result above shows the shortest path lengths between all vertices in the graph. The value INF indicates that there is no path between two vertices.
This article introduced how to implement the Floyd-Warshall algorithm in PHP to solve the shortest path problem in graphs. By using dynamic programming, we can find the shortest path lengths between all vertices in a graph with a time complexity of O(N^3). By applying algorithm design techniques effectively, we can efficiently use this algorithm to solve real-world problems.
