改进型Dijkstra算法的最短路径求解  

作　　者：金婷[1] 方欢[1] 方贤文[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232000

出　　处：《软件导刊》2016年第2期129-131,共3页Software Guide

基　　金：大学生创新创业训练项目(AH201410361251)

摘　　要：最短路径问题一直是图论中的研究热点。为寻找有向图中任意两点之间存在的所有最短路径,从Dijkstra算法入手,分析其最短路径实现原理,发现其局限性,即多条路径求解是唯一的;对算法作出改进,在Dijkstra算法基础上引入前置邻结点,对每个顶点增加前置邻结点属性,并进行实时记录和更新,使改进后的算法能够求解多条路径问题。利用Java语言编程实现算法思想,通过简单的界面显示验证了算法的正确性。

关 键 词：DIJKSTRA算法 前置邻结点 多条最短路径 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]