最短路径问题
最短路径问题
-
单源最短路径
非加权图的最短路径
加权图的最短路径
- 带有负权值的图
- 有向无环图
所有顶点对间的最短路径
单源最短路径
给出一个加权图和图上的一个节点s,找出s到图中每一节点的最短路径。
非加权图的最短路径
采用广度优先搜索,它按层处理一层的所有结点:离起始结点最近的结点最先处理,距离最远的最晚处理。
具体过程:
- 从s到s的最短路径为0;
- 通过搜索s的所有邻接结点就能找到离s距离为1的所有结点;
- 搜索离s距离为1的所有结点的邻接结点就能找到距离为2的节点;
- 重复上述过程,直到所有节点都访问到为止。
存储设计:
数组distance:记录从源点到达每个结点的最短距离。
数组prev:记录要到达此结点,必须到达的前一结点。用于追溯这条路径。
加权图的最短路径
Dijkstra算法:
保存了一个顶点集S。S中的顶点是已经找到了最短路径的顶点。
开始时,顶点集合S只包含源点s一个顶点。
反复执行以下循环,直至顶点集S包含所有的顶点为止:对于在顶点集V - S中的每个顶点,考察新加入顶点集S中的结点是否有边到达V-S。如果存在,则检查这条路径是否比原来已知的路径要短。如果是,则更新源点到此结点的距离和路径;然后,从V – S中寻找一个路径最短的结点,从源点到这个结点已经不可能有更好的路径了,把它加入顶点集S。
带有负权值的图
如果一个图带有负权值的边,Dijkstra算法无法正常工作。
实现:利用一个队列
- 开始时,将源点s放入队列
- 重复以下过程,直到队列为空:
- 出队一个节点v
- 对v的所有邻接点w,如果经过v到w的距离比已知的s到w的距离短,则更新w的距离,并将w入队
有向无环图
描述一项工程或系统进展的有效工具。
AOV网(Activity On Vertex Network)
将所有的工程项目分解为若干个活动(子工程);活动定义在顶点上,顶点之间的有向边表示活动执行的次序。
AOE网(Activity On Edge Network)
将所有的工程项目分解为若干个活动(子工程);活动定义在有向边上,顶点表示事件,有向边的权值表示活动持续的时间,有向边的方向表示事件发生的先后次序。
关键事件和关键路径概念。
所有顶点对间的最短路径
方法一:对每一结点运行Dijkstra最短路径算法。
方法二:Floyd算法。
Floyd算法
一次将每个节点作为中间节点,看看从起始点到中间结点,再从中间节点到终止点的距离是不是比已知的距离短。如是,则替代。
使用n行n列的矩阵A用于计算最短路径。
进行n次迭代。在进行第k次迭代时
路径信息的保存需要一个二维数组prev。prev[i][j]的值表示从i到j的最短路径上的前一结点的序号。