一种计算单源单汇点最短路的新方法

摘要

用ｄｉｊｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ＾２）。本文提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）。两种算法的空间复杂性基本相同。