一种改进的最短路径算法

摘要

求最短路径，是一个应用很广泛的问题，求最短路径的算法有很多，公认较好的算法是由Dijkstra于195g年提出的标号法。但是算法实验表明，标号法有需要改进的地方：①算法的退出机制对有向图有可能无效，甚至会陷入死循环；②标号法没有涉及最短路径上顶点的邻接点问题；③标号法没有涉及多个顶点同时获得p标号的问题。针对上述问题，本文对标号法进行了改进。算法实验表明，改进的标号法能够有效解决上述问题。