求最短路径树的一个新算法

本义考虑在一个具有ｎ个结点和ｍ条弧的网络中，求出从一个指定的结点到其余所有结点的最短路径，或者找到一条具有负长度环路的问题。文中基于结点标号深度的概念，给出了一个计算复杂性的界为Ｏ（ｎｍ）并且具有“尖列刀（ｓｈａｒｐ）性质的求最短路径树的新算法。此外，我们还讨论了负长度环路的探测问题，并给出了一个具有“时间尖刮”（ｔｉｍｅ－ｓｈａｒｐ）性质的检测负长度环路的方法。