最短路径算法-Dijkstra

image.png

<?php

//最短路径算法,核心思路是广度遍历
//一个p(a,b)表示a到b的最短距离路径,m,n是最短路径上的2个点,则p(a,m) p(m,n)一定是a到n的最短路径
//反证法:设q是a到n的最短距离,则有p(a,q) + p(q,n) < p(a,m) + p(m,n)
//p(a,q) + p(q,n) + (n,b) < p(a,m)+ p(m,n) + p(n,b) 即,p(a,q) + p(q,n) + p(n,b) < p(a,b)
//因为p(a,b)是最短距离,q不能比最短距离还短,所以,p(a,m) p(m,n)一定是最短距离
//使用二维数据来表示1个点到其它点之间的距离,为0表示无穷大
//aa = 0 ab = 2 ac = 0 ad = 1 ae = 5 af = 0 ag = 0
define("INT_MAX", 1000000);

$key_alphabet = array(0=>'a', 1=>'b', 2=>'c', 3=>'d', 4=>'e', 5=> 'f', 6=>'g');

$arr = array(
    array(0, 2, 0, 1, 5, 0, 0), //a
    array(2, 0, 4, 0, 0, 0, 0), //b
    array(0, 4, 0, 0, 2, 0, 0), //c
    array(1, 0, 0, 0, 2, 1, 0), //d
    array(5, 0, 2, 2, 0, 0, 4), //e
    array(0, 0, 0, 1, 0, 0, 3), //f
    array(0, 0, 0, 0, 4, 3, 0), //g
);

$ready_array = array(0); //最短路径集合
$future_array = array(1, 2, 3, 4, 5, 6); //未加入最短路径集合
$d = array();
$d_path = $key_alphabet[0] . '->';

//初始化图中节点与源点0的最小距离
for ($i = 1; $i < 7; $i++) {
    if ($arr[0][$i] > 0) {
        $d[$i]['value'] = $arr[0][$i];
        $d[$i]['path'] = $d_path . $key_alphabet[$i];
    } else {
        $d[$i]['value'] = INT_MAX;
        $d[$i]['path'] = '';
    }
}


// n-1次循环完成转移节点任务
for ($j = 1; $j < 7; $j++) {
    // 查找剩余节点中距离源点最近的节点v
    $current_min = INT_MAX;
    $current_min_v = 0;
    
    foreach ($future_array as $k => $v) {
        if ($d[$v]['value'] < $current_min) {
            $current_min = $d[$v]['value'];
            $current_min_v = $v;
        }
    }
    
    //$d_path .= $key_alphabet[$current_min_v] . '->';
    //ab  ac ad ae af ag 报存最短路径
    //$d[$current_min_v]['path'] = $d_path;
    $d[$current_min_v]['value'] = $current_min;

    //array_push($d_path, $d_path.$key_alphabet[$current_min_v] .'->');
    
    //从V中更新顶点到U中
    array_push($ready_array, $current_min_v);
    array_splice($future_array, array_search($current_min_v, $future_array), 1);
//var_dump($future_array);
    //更新
    foreach ($future_array as $k => $u) {
        if ($arr[$current_min_v][$u] != 0 && $d[$u]['value'] > $d[$current_min_v]['value'] + $arr[$current_min_v][$u]) {
            $d[$u]['value'] = $d[$current_min_v]['value'] + $arr[$current_min_v][$u];
            $d[$u]['path'] = $d[$current_min_v]['path'] . '->' . $key_alphabet[$u];
        }
    }
}





var_dump($d);
//打印最短路径

function print_short_path($d, $begin)
{
echo  $begin . "为起点的图的最短路径为:";
for ($i = 0; $i< 7; $i++) {
if($d[$i]!=INT_MAX)
echo  $d[$i] ."=" . $d[$i];
else {
echo $d[$i] . "是无最短路径的";
}
}
}

//print_short_path($d, 6);




//var_dump('最短路径是: ' . $d_path );
//var_dump("最短路径是: " . $d[6]);


// foreach ($ready_array as $k => $u) {
//  var_dump($k . '=>' . $key_alphabet[$u]);
// }


获得a点到各个点的最短路径和距离

array(6) {

  [1]=>

  array(2) {

    ["value"]=>

    int(2)

    ["path"]=>

    string(4) "a->b"

  }

  [2]=>

  array(2) {

    ["value"]=>

    int(5)

    ["path"]=>

    string(10) "a->d->e->c"

  }

  [3]=>

  array(2) {

    ["value"]=>

    int(1)

    ["path"]=>

    string(4) "a->d"

  }

  [4]=>

  array(2) {

    ["value"]=>

    int(3)

    ["path"]=>

    string(7) "a->d->e"

  }

  [5]=>

  array(2) {

    ["value"]=>

    int(2)

    ["path"]=>

    string(7) "a->d->f"

  }

  [6]=>

  array(2) {

    ["value"]=>

    int(5)

    ["path"]=>

    string(10) "a->d->f->g"

  }

}