PHP algorithm design tips: How to use Dijkstra's algorithm to solve the single-source shortest path problem?

PHP algorithm design tips: How to use Dijkstra's algorithm to solve the single-source shortest path problem?

Introduction:

In computer science, Dijkstra's algorithm is a classic algorithm used to solve the shortest path problem from a single source point to all other points in the graph. In actual development, we often need to deal with the shortest path problem in websites or applications, such as finding the shortest transportation route or the optimal navigation path between two places. This article will introduce how to use PHP to implement Dijkstra's algorithm and give specific code examples.

1. Introduction to Dijkstra algorithm

Dijkstra algorithm is a greedy algorithm used to solve the single-source shortest path problem in weighted directed graphs. The basic idea of ​​this algorithm is to start from the source point and gradually determine the shortest path from the source point to each other vertex. During the execution of the algorithm, the shortest path distance and predecessor vertices of each vertex are continuously updated by maintaining a distance array.

The algorithm steps are as follows:

1. Initialize the distance array, set the distance of the source point to 0, and set the distance of other points to infinity.
2. Select the smallest value in the distance array as the current node and mark the node as visited.
3. Update the shortest path distance of the adjacent nodes of the current node. If a shorter path is found, update the distance array and predecessor vertices.
4. Repeat steps 2 and 3 until all nodes have been visited or there are no updateable values ​​in the distance array.

2. PHP implementation of Dijkstra algorithm

The following is a code example of using PHP to implement Dijkstra algorithm:

<?php
// 定义无穷大常量
define('INF', PHP_INT_MAX);

function dijkstra($graph, $source) {
    $numVertices = count($graph);
    
    // 初始化距离数组和标记数组
    $dist = array_fill(0, $numVertices, INF);
    $visited = array_fill(0, $numVertices, false);
    
    // 源点到源点的距离为0
    $dist[$source] = 0;
    
    // 更新距离数组和前驱顶点
    for ($i = 0; $i < $numVertices - 1; $i++) {
        // 找到距离数组中最小的值
        $minDist = INF;
        $minIndex = -1;
        
        for ($j = 0; $j < $numVertices; $j++) {
            if (!$visited[$j] && $dist[$j] <= $minDist) {
                $minDist = $dist[$j];
                $minIndex = $j;  
            }
        }
        
        // 将最小值标记为已访问
        $visited[$minIndex] = true;
        
        // 更新邻接节点的距离和前驱顶点
        for ($k = 0; $k < $numVertices; $k++) {
            if (!$visited[$k] && $graph[$minIndex][$k] && 
                $dist[$minIndex] !== INF && 
                $dist[$minIndex] + $graph[$minIndex][$k] < $dist[$k]) {
                $dist[$k] = $dist[$minIndex] + $graph[$minIndex][$k];
            }
        }
    }
    
    return $dist;
}

// 图的邻接矩阵表示
$graph = array(
    array(0, 4, 0, 0, 0, 0, 0, 8, 0),
    array(4, 0, 8, 0, 0, 0, 0, 11, 0),
    array(0, 8, 0, 7, 0, 4, 0, 0, 2),
    array(0, 0, 7, 0, 9, 14, 0, 0, 0),
    array(0, 0, 0, 9, 0, 10, 0, 0, 0),
    array(0, 0, 4, 14, 10, 0, 2, 0, 0),
    array(0, 0, 0, 0, 0, 2, 0, 1, 6),
    array(8, 11, 0, 0, 0, 0, 1, 0, 7),
    array(0, 0, 2, 0, 0, 0, 6, 7, 0)
);

$source = 0; // 源点

$dist = dijkstra($graph, $source);

echo "顶点        最短距离
";
for ($i = 0; $i < count($dist); $i++) {
    echo $i . "        " . $dist[$i] . "
";
}
?>

The above code first defines an infinite constant INF, Then the dijkstra function is implemented, which receives a graph represented by an adjacency matrix and a source point as parameters, and returns an array holding the shortest distance from the source point to each other vertex.

In the main program, a graph represented by an adjacency matrix is ​​used to test the dijkstra function. Finally, the shortest distance from each vertex to the source point is output through loop traversal.

Conclusion:

This article introduces how to use PHP to implement Dijkstra's algorithm to solve the single-source shortest path problem, and gives specific code examples. Dijkstra's algorithm is one of the commonly used algorithms for solving shortest path problems and can be applied to many practical problems. I hope the content of this article will be helpful for understanding and applying Dijkstra's algorithm.

The above is the detailed content of PHP algorithm design tips: How to use Dijkstra's algorithm to solve the single-source shortest path problem?. For more information, please follow other related articles on the PHP Chinese website!