CAJ | 학술논문

为了有效提高市民出行效率，减小城市资源消耗，优化城市环境，在改进型Dijkstra算法的基础上设计并实现城市公交线路查询系统。 Dijkstra算法是图论中求解最短路径问题的一种优秀算法。在Dijkstra算法的基础上，进行对存储结构进行优化、对结点进行分类、对权值进行排序这三大改进，并将改进型Dijkstra算法作为最优公交线路查询算法的核心，以时间最小、费用最小、综合最优这三种需求作为评价标准分别建立数学模型，通过数学模型将搜索两点间的最优路线问题转化成求解两点间的最短路径问题，最后以南昌市的公交路网为例对算法和数学模型进行仿真测试。仿真结果验证算法和数据模型的有效性。
위료유효제고시민출행효솔，감소성시자원소모，우화성시배경，재개진형Dijkstra산법적기출상설계병실현성시공교선로사순계통。 Dijkstra산법시도론중구해최단로경문제적일충우수산법。재Dijkstra산법적기출상，진행대존저결구진행우화、대결점진행분류、대권치진행배서저삼대개진，병장개진형Dijkstra산법작위최우공교선로사순산법적핵심，이시간최소、비용최소、종합최우저삼충수구작위평개표준분별건립수학모형，통과수학모형장수색량점간적최우로선문제전화성구해량점간적최단로경문제，최후이남창시적공교로망위례대산법화수학모형진행방진측시。방진결과험증산법화수거모형적유효성。
In order to improve the efficiency of public travel, reduce the consumption of urban resources and optimize the urban environment, designs and implements the city bus lines inquiry system based on improved Dijkstra algorithm. Dijkstra algorithm is an excellent algorithm to solve the shortest path problems in the field of graph theory. Makes three major improvements on Dijkstra algorithm:optimizes the structure of the storage, classifies the nodes, sorts the weights and takes the improved Dijkstra algorithm as the core algorithm to query the best bus lines of urban public transport. Establishes mathematical models respectively with the evaluation criteria which com-posed by minimum of time, minimum cost and comprehensive optimal. Under these three de-mands, transforms the problem of searching the optimal route between two points into the prob-lem of solving the shortest path between two points through the mathematical models. Takes the improved Dijkstra algorithm and the mathematical models for the simulation test. The simulation results demonstrate the effectiveness of the algorithms and data model.