PHP アルゴリズム設計のヒント: 単一ソースの最短パス問題を解決するためにダイクストラのアルゴリズムを使用する方法

PHP アルゴリズム設計のヒント: ダイクストラのアルゴリズムを使用して単一ソースの最短パス問題を解決するにはどうすればよいですか?

はじめに:

コンピューターサイエンスにおいて、ダイクストラのアルゴリズムは、グラフ内の単一のソース点から他のすべての点までの最短経路問題を解くために使用される古典的なアルゴリズムです。実際の開発では、最短の輸送ルートや 2 つの場所間の最適なナビゲーション パスを見つけるなど、Web サイトやアプリケーションの最短経路の問題に対処する必要があることがよくあります。この記事では、PHP を使用してダイクストラのアルゴリズムを実装する方法と、具体的なコード例を紹介します。

1. ダイクストラ アルゴリズムの概要

ダイクストラ アルゴリズムは、重み付き有向グラフにおける単一ソース最短経路問題を解くために使用される貪欲なアルゴリズムです。このアルゴリズムの基本的な考え方は、ソース ポイントから開始して、ソース ポイントから他の頂点までの最短パスを徐々に決定することです。アルゴリズムの実行中、距離配列を維持することによって、各頂点の最短パス距離と先行頂点が継続的に更新されます。

アルゴリズムの手順は次のとおりです。

1. 距離配列を初期化し、ソース ポイントの距離を 0 に設定し、他のポイントの距離を無限大に設定します。
2. 距離配列の最小値を現在のノードとして選択し、そのノードを訪問済みとしてマークします。
3. 現在のノードの隣接ノードの最短パス距離を更新します。より短いパスが見つかった場合は、距離配列と先行頂点を更新します。
4. すべてのノードにアクセスするか、距離配列に更新可能な値がなくなるまで、手順 2 と 3 を繰り返します。

2. ダイクストラ アルゴリズムの PHP 実装

以下は、PHP を使用してダイクストラ アルゴリズムを実装するコード例です:

<?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] . "
";
}
?>

上記のコードは、最初に無限を定義します。定数 INF、次にダイクストラ関数が実装されます。この関数は、隣接行列で表されるグラフとソース点をパラメータとして受け取り、ソース点から各頂点までの最短距離を保持する配列を返します。

メイン プログラムでは、隣接行列で表されるグラフを使用してダイクストラ関数をテストします。最後に、各頂点からソース ポイントまでの最短距離がループ トラバーサルによって出力されます。

結論:

この記事では、PHP を使用してダイクストラのアルゴリズムを実装し、単一ソースの最短パス問題を解決する方法を紹介し、具体的なコード例を示します。ダイクストラのアルゴリズムは、最短経路問題を解くために一般的に使用されるアルゴリズムの 1 つであり、多くの実際的な問題に適用できます。この記事の内容がダイクストラのアルゴリズムの理解と応用に役立つことを願っています。

以上がPHP アルゴリズム設計のヒント: 単一ソースの最短パス問題を解決するためにダイクストラのアルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。