利用无权图的单源最短路算法实现地铁换乘图

本是古典何须时尚 2022-08-22 01:26 161阅读 0赞

//Metro.php
    $MetroVertex = array(
        1 => '体育中心',
        2 => '体育西路',
        3 => '杨箕',
        4 => '东山口',
        5 => '烈士陵园',
        6 => '农讲所',
        7 => '公园前',
        8 => '西门口',
        9 => '陈家祠',
        10 => '长寿路',
        11 => '黄沙',
        12 => '芳村',
        13 => '花地湾',
        14 => '坑口',
        15 => '西朗',
        16 => '嘉禾望岗',
        17 => '黄边',
        18 => '江夏',
        19 => '萧岗',
        20 => '白云文化广场',
        21 => '白云公园',
        22 => '飞翔公园',
        23 => '三元里',
        24 => '广州火车站',
        25 => '越秀公园',
        26 => '纪念堂',
        27 => '海珠广场',
        28 => '市二宫',
        29 => '江南西',
        30 => '昌岗',
        31 => '江泰路',
        32 => '东晓南',
        33 => '南州',
        34 => '洛溪',
        35 => '南浦',
        36 => '会江',
        37 => '石壁',
        38 => '广州南站',
        39 => '天河客运站',
        40 => '五山',
        41 => '华师',
        42 => '岗顶',
        43 => '石牌桥',
        44 => '珠江新城',
        45 => '广州塔',
        46 => '客村',
        47 => '大塘',
        48 => '沥滘',
        49 => '厦滘',
        50 => '大石',
        51 => '汉溪长隆',
        52 => '市桥',
        53 => '番禺广场',
        54 => '机场南',
        55 => '人和',
        56 => '龙归',
        57 => '白云大道北',
        58 => '永泰',
        59 => '同和',
        60 => '京溪南方医院',
        61 => '梅花园',
        62 => '燕塘',
        63 => '广州东',
        64 => '林和西',
        65 => '黄村',
        66 => '车陂',
        67 => '车陂南',
        68 => '万胜围',
        69 => '官洲',
        70 => '大学城北',
        71 => '大学城南',
        72 => '新造',
        73 => '石碁',
        74 => '海傍',
        75 => '低涌',
        76 => '东涌',
        77 => '黄阁汽车城',
        78 => '黄阁',
        79 => '蕉门',
        80 => '金州',
        81 => '滘口',
        82 => '坦尾',
        83 => '中山八',
        84 => '西场',
        85 => '西村',
        86 => '小北',
        87 => '淘金',
        88 => '区庄',
        89 => '动物园',
        90 => '五羊邨',
        91 => '猎德',
        92 => '潭村',
        93 => '员村',
        94 => '科韵路',
        95 => '东圃',
        96 => '三溪',
        97 => '鱼珠',
        98 => '大沙地',
        99 => '大沙东',
        100 => '文冲',
        101 => '浔峰岗',
        102 => '横沙',
        103 => '沙贝',
        104 => '河沙',
        106 => '如意坊',
        108 => '文化公园',
        109 => '一德路',
        111 => '北京路',
        112 => '团一大广场',
        113 => '东湖',
        115 => '黄花岗',
        116 => '沙河顶',
        117 => '沙河',
        118 => '天平架',
        119 => '长湴',
        120 => '凤凰新村',
        121 => '沙园',
        122 => '宝岗大道',
        123 => '晓港',
        124 => '中大',
        125 => '鹭江',
        126 => '赤岗',
        127 => '磨碟沙',
        128 => '新港东',
        129 => '琶洲',
        130 => '体育中心南',
        131 => '天河南',
        132 => '黄埔大道',
        133 => '妇儿中心',
        134 => '花城大道',
        135 => '大剧院',
        136 => '海心沙'
    );
    
    $Line = array();
    $Line['63']['1'] = 1;
    $Line['63']['62'] = 1;
    $Line['63']['64'] = 1;
    $Line['1']['63'] = 1;
    $Line['1']['2'] = 1;
    $Line['2']['1'] = 1;
    $Line['2']['43'] = 1;
    $Line['2']['3'] = 1;
    $Line['2']['44'] = 1;
    $Line['3']['2'] = 1;
    $Line['3']['2'] = 1;
    $Line['3']['89'] = 1;
    $Line['3']['4'] = 1;
    $Line['4']['3'] = 1;
    $Line['4']['5'] = 1;
    $Line['4']['113'] = 1;
    $Line['4']['88'] = 1;
    $Line['5']['4'] = 1;
    $Line['5']['6'] = 1;
    $Line['6']['5'] = 1;
    $Line['6']['7'] = 1;
    $Line['7']['8'] = 1;
    $Line['7']['6'] = 1;
    $Line['7']['26'] = 1;
    $Line['7']['27'] = 1;
    $Line['8']['7'] = 1;
    $Line['8']['9'] = 1;
    $Line['9']['8'] = 1;
    $Line['9']['10'] = 1;
    $Line['10']['9'] = 1;
    $Line['10']['11'] = 1;
    $Line['11']['108'] = 1;
    $Line['11']['106'] = 1;
    $Line['11']['12'] = 1;
    $Line['12']['11'] = 1;
    $Line['12']['13'] = 1;
    $Line['13']['12'] = 1;
    $Line['13']['14'] = 1;
    $Line['14']['13'] = 1;
    $Line['14']['15'] = 1;
    $Line['16']['56'] = 1;
    $Line['16']['57'] = 1;
    $Line['16']['17'] = 1;
    $Line['17']['16'] = 1;
    $Line['17']['18'] = 1;
    $Line['18']['17'] = 1;
    $Line['18']['19'] = 1;
    $Line['19']['18'] = 1;
    $Line['19']['20'] = 1;
    $Line['20']['19'] = 1;
    $Line['20']['21'] = 1;
    $Line['21']['20'] = 1;
    $Line['21']['22'] = 1;
    $Line['22']['21'] = 1;
    $Line['22']['23'] = 1;
    $Line['23']['22'] = 1;
    $Line['23']['24'] = 1;
    $Line['24']['23'] = 1;
    $Line['24']['25'] = 1;
    $Line['24']['85'] = 1;
    $Line['24']['86'] = 1;
    $Line['25']['24'] = 1;
    $Line['25']['26'] = 1;
    $Line['26']['25'] = 1;
    $Line['26']['27'] = 1;
    $Line['27']['26'] = 1;
    $Line['27']['28'] = 1;
    $Line['27']['109'] = 1;
    $Line['27']['111'] = 1;
    $Line['28']['27'] = 1;
    $Line['28']['29'] = 1;
    $Line['29']['28'] = 1;
    $Line['29']['30'] = 1;
    $Line['30']['29'] = 1;
    $Line['30']['31'] = 1;
    $Line['30']['122'] = 1;
    $Line['30']['123'] = 1;
    $Line['31']['30'] = 1;
    $Line['31']['32'] = 1;
    $Line['32']['31'] = 1;
    $Line['32']['33'] = 1;
    $Line['33']['32'] = 1;
    $Line['33']['34'] = 1;
    $Line['34']['35'] = 1;
    $Line['34']['33'] = 1;
    $Line['35']['34'] = 1;
    $Line['35']['36'] = 1;
    $Line['36']['35'] = 1;
    $Line['36']['37'] = 1;
    $Line['37']['36'] = 1;
    $Line['37']['38'] = 1;
    $Line['39']['119'] = 1;
    $Line['39']['62'] = 1;
    $Line['39']['40'] = 1;
    $Line['40']['39'] = 1;
    $Line['40']['41'] = 1;
    $Line['41']['40'] = 1;
    $Line['41']['42'] = 1;
    $Line['42']['41'] = 1;
    $Line['42']['43'] = 1;
    $Line['43']['42'] = 1;
    $Line['43']['2'] = 1;
    $Line['44']['2'] = 1;
    $Line['44']['45'] = 1;
    $Line['44']['45'] = 1;
    $Line['44']['90'] = 1;
    $Line['44']['91'] = 1;
    $Line['45']['44'] = 1;
    $Line['45']['46'] = 1;
    $Line['45']['136'] = 1;
    $Line['46']['45'] = 1;
    $Line['46']['47'] = 1;
    $Line['46']['125'] = 1;
    $Line['46']['126'] = 1;
    $Line['47']['46'] = 1;
    $Line['47']['48'] = 1;
    $Line['48']['47'] = 1;
    $Line['48']['49'] = 1;
    $Line['49']['48'] = 1;
    $Line['49']['50'] = 1;
    $Line['50']['49'] = 1;
    $Line['50']['51'] = 1;
    $Line['51']['50'] = 1;
    $Line['51']['52'] = 1;
    $Line['52']['51'] = 1;
    $Line['52']['53'] = 1;
    $Line['53']['52'] = 1;
    $Line['54']['55'] = 1;
    $Line['55']['54'] = 1;
    $Line['55']['56'] = 1;
    $Line['56']['16'] = 1;
    $Line['57']['16'] = 1;
    $Line['57']['58'] = 1;
    $Line['58']['57'] = 1;
    $Line['58']['59'] = 1;
    $Line['59']['58'] = 1;
    $Line['59']['60'] = 1;
    $Line['60']['59'] = 1;
    $Line['60']['61'] = 1;
    $Line['61']['60'] = 1;
    $Line['61']['62'] = 1;
    $Line['62']['61'] = 1;
    $Line['62']['63'] = 1;
    $Line['62']['118'] = 1;
    $Line['62']['39'] = 1;
    $Line['64']['63'] = 1;
    $Line['64']['130'] = 1;
    $Line['64']['2'] = 1;
    $Line['65']['66'] = 1;
    $Line['66']['65'] = 1;
    $Line['66']['67'] = 1;
    $Line['67']['66'] = 1;
    $Line['67']['68'] = 1;
    $Line['67']['94'] = 1;
    $Line['67']['95'] = 1;
    $Line['68']['67'] = 1;
    $Line['68']['69'] = 1;
    $Line['68']['129'] = 1;
    $Line['69']['68'] = 1;
    $Line['69']['70'] = 1;
    $Line['70']['69'] = 1;
    $Line['70']['71'] = 1;
    $Line['71']['70'] = 1;
    $Line['71']['72'] = 1;
    $Line['72']['71'] = 1;
    $Line['72']['73'] = 1;
    $Line['73']['72'] = 1;
    $Line['73']['74'] = 1;
    $Line['74']['73'] = 1;
    $Line['74']['75'] = 1;
    $Line['75']['74'] = 1;
    $Line['75']['76'] = 1;
    $Line['76']['75'] = 1;
    $Line['76']['77'] = 1;
    $Line['76']['77'] = 1;
    $Line['77']['76'] = 1;
    $Line['77']['78'] = 1;
    $Line['78']['77'] = 1;
    $Line['78']['79'] = 1;
    $Line['79']['78'] = 1;
    $Line['79']['80'] = 1;
    $Line['80']['79'] = 1;
    $Line['81']['82'] = 1;
    $Line['82']['81'] = 1;
    $Line['82']['83'] = 1;
    $Line['82']['104'] = 1;
    $Line['82']['106'] = 1;
    $Line['83']['82'] = 1;
    $Line['83']['84'] = 1;
    $Line['84']['83'] = 1;
    $Line['84']['85'] = 1;
    $Line['85']['84'] = 1;
    $Line['85']['24'] = 1;
    $Line['86']['24'] = 1;
    $Line['86']['87'] = 1;
    $Line['87']['86'] = 1;
    $Line['87']['88'] = 1;
    $Line['88']['87'] = 1;
    $Line['88']['89'] = 1;
    $Line['88']['4'] = 1;
    $Line['88']['115'] = 1;
    $Line['89']['88'] = 1;
    $Line['89']['3'] = 1;
    $Line['90']['3'] = 1;
    $Line['90']['44'] = 1;
    $Line['91']['44'] = 1;
    $Line['91']['92'] = 1;
    $Line['92']['91'] = 1;
    $Line['92']['93'] = 1;
    $Line['93']['92'] = 1;
    $Line['93']['94'] = 1;
    $Line['94']['93'] = 1;
    $Line['94']['67'] = 1;
    $Line['95']['67'] = 1;
    $Line['95']['96'] = 1;
    $Line['96']['95'] = 1;
    $Line['96']['97'] = 1;
    $Line['97']['96'] = 1;
    $Line['97']['98'] = 1;
    $Line['98']['97'] = 1;
    $Line['98']['99'] = 1;
    $Line['99']['98'] = 1;
    $Line['99']['100'] = 1;
    $Line['100']['99'] = 1;
    $Line['101']['102'] = 1;
    $Line['102']['101'] = 1;
    $Line['102']['103'] = 1;
    $Line['103']['102'] = 1;
    $Line['103']['104'] = 1;
    $Line['104']['103'] = 1;
    $Line['104']['82'] = 1;
    $Line['106']['82'] = 1;
    $Line['106']['11'] = 1;
    $Line['108']['11'] = 1;
    $Line['108']['109'] = 1;
    $Line['109']['108'] = 1;
    $Line['109']['27'] = 1;
    $Line['111']['27'] = 1;
    $Line['111']['112'] = 1;
    $Line['112']['111'] = 1;
    $Line['112']['113'] = 1;
    $Line['113']['4'] = 1;
    $Line['115']['88'] = 1;
    $Line['115']['116'] = 1;
    $Line['116']['115'] = 1;
    $Line['116']['117'] = 1;
    $Line['117']['116'] = 1;
    $Line['117']['118'] = 1;
    $Line['118']['117'] = 1;
    $Line['118']['62'] = 1;
    $Line['119']['39'] = 1;
    $Line['120']['121'] = 1;
    $Line['121']['120'] = 1;
    $Line['121']['122'] = 1;
    $Line['122']['121'] = 1;
    $Line['122']['30'] = 1;
    $Line['123']['30'] = 1;
    $Line['123']['124'] = 1;
    $Line['124']['123'] = 1;
    $Line['124']['125'] = 1;
    $Line['125']['124'] = 1;
    $Line['125']['46'] = 1;
    $Line['126']['46'] = 1;
    $Line['126']['127'] = 1;
    $Line['127']['126'] = 1;
    $Line['127']['128'] = 1;
    $Line['128']['127'] = 1;
    $Line['128']['129'] = 1;
    $Line['129']['128'] = 1;
    $Line['129']['68'] = 1;
    $Line['130']['64'] = 1;
    $Line['130']['131'] = 1;
    $Line['131']['130'] = 1;
    $Line['131']['132'] = 1;
    $Line['132']['131'] = 1;
    $Line['132']['133'] = 1;
    $Line['133']['132'] = 1;
    $Line['133']['134'] = 1;
    $Line['134']['133'] = 1;
    $Line['134']['135'] = 1;
    $Line['135']['134'] = 1;
    $Line['135']['136'] = 1;
    $Line['136']['135'] = 1;
    $Line['136']['45'] = 1;

<?php
    require_once(dirname(__FILE__) . '\Metro.php');
    //print_r($Line);
    //初始化$dist,$path数组
    foreach($MetroVertex as $k=>$v){
        $dist[$k] = -1;
        $path[$k] = -1;
    }
    function Unweighted($start,$end,$dist,$path,$Line){
        $Queue = array();
        $Queue[] = $start;
        $dist[$start] = 0;
    
        while(!empty($Queue)){
            $v = array_shift($Queue);
            $temp = $Line[(string)$v];
            foreach($temp as $k=>$value){
                if($dist[(int)$k] == -1){
                    $dist[(int)$k] = $dist[$v] +1;
                    $path[(int)$k] = $v;
                    $Queue[] = $k;
                }
                if((int)$k == $end){
                    $find_arr = array();
                    $find = $end;
                    $find_arr[] = $find;
                    while($find != $start){
                        $find = $path[$find];
                        array_unshift($find_arr,$find);
                    }
                    return $find_arr;
                    exit;
                }
            }
        }
    }
    $find_arr = Unweighted(50,87,$dist,$path,$Line);
    foreach($find_arr as $k=>$v){
        $find_arr[$k] = $MetroVertex[$v];
    }
    echo implode('->',$find_arr);

**//伪代码，无权图的单源最短路算法**

/* 邻接表存储 - 无权图的单源最短路算法 */
         
        /* dist[]和path[]全部初始化为-1 */
        void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
        {
            Queue Q;
            Vertex V;
            PtrToAdjVNode W;
             
            Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
            dist[S] = 0; /* 初始化源点 */
            AddQ (Q, S);
         
            while( !IsEmpty(Q) ){
                V = DeleteQ(Q);
                for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
                    if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
                        dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                        path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                        AddQ(Q, W->AdjV);
                    }
            } /* while结束*/
        }