PHP algorithm design ideas: How to achieve an efficient solution to the shortest path problem of graphs?

PHP algorithm design ideas: How to achieve an efficient solution to the shortest path problem of graphs?

In actual development, we often need to solve the shortest path problem, such as in map navigation, network routing, logistics and distribution and other fields. The shortest path algorithm for graphs is the key to solving this type of problem.

A graph consists of a set of vertices and a set of edges. Vertices represent nodes, and edges represent relationships between nodes. The shortest path problem is to find the shortest path connecting two nodes.

In PHP, we can use a variety of algorithms to solve the shortest path problem, the most famous of which are Dijkstra's algorithm and Bellman-Ford algorithm. Below we introduce the implementation ideas and sample codes of these two algorithms respectively.

1. Dijkstra's algorithm:
   Dijkstra's algorithm is an algorithm widely used to calculate the shortest path in a graph. It uses a greedy strategy to gradually determine the shortest path from the starting node to each other node.

The steps of Dijkstra's algorithm are as follows:
1) Define an array distances, representing the shortest distance from the starting node to other nodes, and the initial value is infinity.
2) Define an array visited, indicating whether the node has been visited, and the initial value is false.
3) Set the shortest distance of the starting node to 0.
4) Repeat the following steps until all nodes have been visited:
a) Select a node closest to the starting node from the unvisited nodes.
b) Mark the node as visited.
c) Update the shortest distance from the adjacent node to the node. If the updated shortest distance is smaller than the previous distance, update the value in the distances array.
5) Finally get the distances array, where distances[i] represents the shortest distance from the starting node to node i.

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

function dijkstra($graph, $startNode) {
    $distances = array();
    $visited = array();

    foreach ($graph as $node => $value) {
        $distances[$node] = INF; // 初始距离设为无穷大
        $visited[$node] = false; // 初始状态为未访问
    }

    $distances[$startNode] = 0; // 起始节点的距离设为0

    while (true) {
        $closestNode = null;

        foreach ($graph[$startNode] as $neighbor => $distance) {
            if (!$visited[$neighbor]) {
                if ($closestNode === null || $distances[$neighbor] < $distances[$closestNode]) {
                    $closestNode = $neighbor;
                }
            }
        }

        if ($closestNode === null) {
            break;
        }

        $visited[$closestNode] = true;

        foreach ($graph[$closestNode] as $key => $value) {
            $distanceToNeighbor = $distances[$closestNode] + $value;
            if ($distanceToNeighbor < $distances[$key]) {
                $distances[$key] = $distanceToNeighbor;
            }
        }
    }

    return $distances;
}

2. Bellman-Ford algorithm:
   The Bellman-Ford algorithm is a classic algorithm for solving the shortest path problem , which can cope with graphs with negative weight edges.

The steps of the Bellman-Ford algorithm are as follows:
1) Define an array distances, representing the shortest distance from the starting node to other nodes, and the initial value is infinity.
2) Set the shortest distance of the starting node to 0.
3) Repeat the following steps until all edges are relaxed:
a) All edges are relaxed, that is, the distance is shortened by the next edge.
b) Update the distances array, and if a shorter path is found, update the shortest distance.
4) Finally, check whether there is a negative weight loop. If it exists, it means that there is an unbounded negative weight path in the graph.

The following is a code example using PHP to implement the Bellman-Ford algorithm:

function bellmanFord($graph, $startNode) {
    $numOfVertices = count($graph);
    $distances = array_fill(0, $numOfVertices, INF);
    $distances[$startNode] = 0;

    for ($i = 0; $i < $numOfVertices - 1; $i++) {
        for ($j = 0; $j < $numOfVertices; $j++) {
            for ($k = 0; $k < $numOfVertices; $k++) {
                if ($graph[$j][$k] != INF && $distances[$j] + $graph[$j][$k] < $distances[$k]) {
                    $distances[$k] = $distances[$j] + $graph[$j][$k];
                }
            }
        }
    }

    for ($j = 0; $j < $numOfVertices; $j++) {
        for ($k = 0; $k < $numOfVertices; $k++) {
            if ($graph[$j][$k] != INF && $distances[$j] + $graph[$j][$k] < $distances[$k]) {
                die("图中存在负权回路");
            }
        }
    }

    return $distances;
}

Summary:
The shortest path problem of graphs is very common in practical applications. By mastering Dijkstra and Bellman-Ford With two algorithms, we can solve this type of problem efficiently. According to the characteristics and requirements of the graph, choosing an appropriate algorithm can improve calculation efficiency and make the program perform better. I hope the introduction in this article will be helpful to everyone.

The above is the detailed content of PHP algorithm design ideas: How to achieve an efficient solution to the shortest path problem of graphs?. For more information, please follow other related articles on the PHP Chinese website!