Dijkstra最短路径算法的优化及其实现

The optimization and Implementation of the Shortest Path Dijkstra Algorithm

王志和 凌云

最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用,对其进行优化很有必要。本文分析了传统的最短路径算法（即Dijkstra算法）的优化途径及现有的优化算法,然后在Dijkstra算法的基础上,采用配对堆结构来实现路径计算过程中优先级队列的一系列操作,经理论分析与实验测试结果对比,可以大大提高该算法的效率和性能。

基于存储结构的Dijkstra算法优化

Optimized Dijkstra Algorithm Based on Storage Structure

李政

在求解最短路径时经常使用经典的Dijkstra算法,但在实际应用中在计算最短路径长度时需要进行大量的数据比较,而当图中两顶点之间的距离是∞时,是没有必要进行比较的。本文从存储结构上讨论如何对Dijkstra算法进行优化,尽量减少数据比较次数。

浅析Dijkstra最短路径算法在消防力量调集中的应用

刘蕊 李峰

文章从我国的火灾形势出发，以优化城市道路交通网中路段的权值为出发点，结合消防工作实际情况的特点，介绍了消防力量调集路径最优指标的选取方案，着重分析了Dijkstra最短路径算法的基本原理，并给出了算法优化方案。优化后的算法能够有效降低Dijkstra算法的时间复杂性，提高运行效率。实例应用表明，该方法兼具灵活性和实用性，能够满足消防灭火救援工作中实现消防力量优化调集的要求。

基于Dijkstra策略的QoS路由算法Fallback

杨云 徐永红 曹立鑫 刘凤玉

Fallback(FB)算法是满足多QoS路径选择的基本算法，文章对FB算法进行了进一步扩充，提出了路径选择的Fallback算法，它不仅满足多QoS。有效地利用了网络通信资源，而且有高的功效。

基于Dijkstra的最短路径改进算法

Improved Algorithm of Shortest Path Based on Dijkstra

罗理 王锋

针对如何利用Dijkstra算法来高效地查找图中任意两结点之间的最短路径这一问题，提出了2种优化方法：其一是应用图中各结点的出入度来简化查找任意两结点之间的最短路径；其二是利用已求出的两点之间的最短路径来快速获得其他结点之间的最短路径。

Dijkstra矩阵算法

Dijkstra＇ s Matrix Algorithm

代西武

介绍了Dijkstra算法，对Dijkstra算法进行改进，提出了计算加权图中任意两点之间最短距离的算法——Dijkstra矩阵算法，给出了Dijkstra矩阵算法在Matlab语言中的实现，对一个具体例子．应用Dijkstra矩阵算法进行了验算．

改进的Dijkstra算法在GIS路径规划中的应用

李宁宁 刘玉树

最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法，利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划，生成满足一定约束条件的最短路径。实际应用分析表明，改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。

使用Dijkstra算法的攻击机初始航迹研究

Research on initial trajectories of attack aircraft based on Dijkstra algorithm

蔡凯 管明露 张天明 孙国志

现代作战条件下，攻击机初始航迹的研究是为了保证攻击机在低空突防攻击时的安全，提高其综合作战能力。Dijkstra算法是图论中求解最短路径的一种算法，具有分析速度快、工程实现能力强的优点。运用改进Dijkstra算法的A＊算法，将攻击机初始航迹规划问题转化成有向图中求最短路径的问题，减少无关顶点的运算，提高查询与规划最短路径的运算效率。侧重于复杂条件下的威胁建模的研究，明确各种威胁模型的系统效能，设置其危险系数，提出针对初始航迹的仿真程序流程图，设计了仿真程序代码。通过具体事例仿真，分析其初期航迹图，验证了算法的有效性与实用性，得到符合实战需要的最优的初始航迹。

基于Dijkstra算法的水平航迹规划

胡晓磊 胡朝晖 江洋溢

战术飞行任务的航迹规划是依靠地形信息和敌情信启、在某些约束条件下，找出作战飞机从起飞点到目标突防生存概率最大、航程最短的飞行轨迹的过程。采用简易方法建立了威胁模型．用Dijkstra算法实现了作战飞机整体最优水平航迹解算．并给出了具体算例，验证了算法的有效性和实用性。

基于CPM原理和Dijkstra算法的SPM网络计划模型及性质

SPM Network Planning Model and Its Characteristics Based on CPM Theories and Dijkstra Algorithm

苏志雄 李星梅 乞建勋

CPM（关键路线法）网络计划适用于分析工序间存在严格紧前关系（任意工序只能在它的所有紧前工序都结束时才能开始）的进度计划。针对工序间不存在严格紧前关系（任意工序只要其紧前工序中的一个结束它就可以开始）的进度计划，以CPM原理和Dijkstra算法为基础，提出SPM（最短路线法）网络计划以及拟机动时间概念，根据不同的建模原理，建立了两个SPM网络计划模型，并给出了其建立方法以及各模型拟机动时间的求法，分析了每个模型的性质，最后通过算例对其中的一类模型进行了验证。