设为有向图，其中
是节点的集合，
是边的集合。把某个节点作为初始点
，另一个作为终点
而特殊对待。各边
上赋有成本
，且都取实数值。在最短路径问题中，成本
解释为边
的长度。试给出最短路径问题的一个多项式时间算法，并分析其复杂性。
解：
最短路径问题的一个经典多项式时间算法是迪杰斯特拉(Dijkstra)算法。下面是算法的描述及其时间复杂度分析。
算法描述
迪杰斯特拉算法用于找到图中从单一源点到所有其他节点的最短路径。如果图中边的权重都是非负的，那么这个算法是有效的。
1.初始化:
-
创建一个集合
，用于存放已经找到最短路径的节点。
-
对于所有节点
.设置两个值:
-
: 从源点
到节点
的最短路径的长度(初始时，除了源点
设为0外，其余都设为
)。
-
: 前驱节点，用于重建最短路径(初始时都设为null)。
2.主循环(直到包含所有
中的节点):
a.在所有不在 中的节点
中，找到
最小的节点，记为
。
b.将节点 加入集合
。
c.对于每个邻接节点 (即存在边
):
- 如果
.则更新
和
。
3.算法结束， 即是从
到
的最短路径长度。
复杂度分析
迪杰斯特拉算法的复杂度主要取决于节点的处理和边的松弛操作。
-
节点处理:在最坏情况下，算法需要处理所有节点，因此这部分的时间复杂度是
。
-
边的松弛操作:在最坏情况下，每条边可能都需要被松弛(更新)。在一个完全图中，边的数量是
，因此这部分的时间复杂度是
。
根据不同的数据结构实现，迪杰斯特拉算法的总时间复杂度有不同的表现:
1.使用简单数组:
-
选择最小节点的操作是
。
-
总复杂度是
。
2.使用二叉堆:
-
选择最小节点的操作是
，每次松弛操作也是
-
总复杂度是
。
3.使用斐波那契堆:
-
选择最小节点的操作是
-
总复杂度是
。
注意事项
负权边:迪杰斯特拉算法不适用于带有负权边的图。如果图中存在负权边，应该使用贝尔曼-福特(Bellman-Ford) 算法，它的时间复杂度为，但可以处理负权边并检测负权环。
网友评论