最短路径-PHP简单实现

$list = [

[1,3,10],

[1,5,30],

[1,6,100],

[2,3,5],

[3,4,50],

[4,6,10],

[5,6,60],

[5,4,20]

];

$point_num = 6;

$a = []; //总数组

$b = []; //当前最短路径

$c = []; //已经遍历的顶点

$max_v = 10000;

for ($i=1; $i <=$point_num ; $i++) {

    for ($j=1; $j <=$point_num ; $j++) {

        $a[$i][$j] = $max_v;

    }

}

foreach ($list as $v) {

    $a[$v[0]][$v[1]] = $v[2];

}

//计算顶点1到各个顶点的最短路径

$b = $a[1];

$c[] = 1;

cal($a, $b, $c, $max_v);

function cal($a, $b, $c, $max_v){

    $min_k = find_min($b, $c);

    if ($min_k == -1) {

        var_dump($b);exit;

    }

    $c[] = $min_k;

    $tmp = $a[$min_k];

    foreach ($tmp as $k => $v) {

        if ($v == $max_v) {

            continue;

        }

        if ($v + $b[$min_k] < $b[$k]) {

            $b[$k] = $v + $b[$min_k];

        }

    }

    cal($a, $b, $c, $max_v);

}

function find_min($b, $c){

    $min_k = -1;

    foreach ($b as $k => $v) {

        if (in_array($k, $c)) {

            continue;

        }

        if ($min_k == -1) {

            $min_k = $k;

            continue;

        }

        if ($v < $b[$min_k]) {

            $min_k = $k;

            continue;

        }

    }

    return $min_k;

}