求解最短路径问题的SLDF算法

摘要

基于结点标号深度的概念，给出了求解单源点最短路径问题的一个新算法—ＳＬＤＦ（ＳｍａｌｅｓｔＬａｂｅｌＤｅｐｔｈＦｉｒｓｔ）算法．此算法的特点是，它具有Ｓｈｉｅｒ＆Ｗｉｔｚｇｅａｌ在［１］中提出的所谓“锐利”（Ｓｈａｒｐ）性质，而且算法的时间复杂性在最坏情况下为Ｏ（ｎｍ），这里ｎ和ｍ分别表示有向图中结点的数目和弧的数目．因此，该算法的实际效率是相当高的．