数据结构之图最短路径
1. 最短路径（Shortest Path）两顶点之间权值之和最小的路径。无权图相当于每条边的权值都是1。不能有负权环。有向图的最短路径：从顶点A出发到达其它顶点的最短路径如下表：无法到达的顶点以∞表示无向图的最短路径：也是以A顶点为起点到达其它顶点的最短路径：无权图的最短路径：即把每条边的权值都作为1来看：负权边：只有不存在负权环时才有最短路径。-负权环：不存在最短路径，如果一种绕环，路径值可以
·
1. 最短路径（Shortest Path）
两顶点之间权值之和最小的路径。无权图相当于每条边的权值都是1。
不能有负权环。
-
有向图的最短路径：
从顶点A出发到达其它顶点的最短路径如下表：无法到达的顶点以∞表示
-
无向图的最短路径：
也是以A顶点为起点到达其它顶点的最短路径：
-
无权图的最短路径：
即把每条边的权值都作为1来看：
-
负权边：只有不存在负权环时才有最短路径。
-负权环：不存在最短路径，如果一种绕环，路径值可以达到无穷小。
1.1 Dijkstra（迪杰斯特拉算法）
单源最短路径算法，计算一个顶点到其它所有顶点的路径。不能有负权边
时间复杂度O(ElogV)，E边数量，V节点数量，
1.1.1 思想
-
幻想下图中每个顶点为一个石头，石头放置在一个水平的平面上，中间的边使用绳子相互连接起来，以权值作为绳子的长度。
-
此时以垂直的拉起“石头”A，因为有绳子的存在，其它的“石头”一定会被拉起。
-
首先被拉动是一定是距离A最近的B，其次是顶点D。
-
这时，因为B~C的距离+上A ~B的距离，大于A ~E的距离，因为拉起的是C而不是E。
-
依次，等到所有“石头”都被拉起之后，每个垂直的线就是A到所有顶点的最短路径。
-
下图中，红色的是被选中的最短路径的边。
-
最后的结果
1.1.2 松弛操作
更新两个顶点之间的最短路径。
依然引入上方的思想，以石头被拉起为例子：
- 当我们拉起石头B，石头B带起石头C起来时：
A->C的最短路径为：A->B->C = 60； - 但当我们拉起石头D，石头D带起石头C起来时：
A->C的最短路径为：A->B->C = 50； - 上方过程就是松弛操作。
1.1.3 执行流程
- 开始执行：将所有A可以直达的顶点，放入到一个集合
paths中，无法到达用∞表示：
- 判断可以直达的B顶点，可以确定A~B的最短路径，将B顶点和最小路径值加入到
selecedPaths集合中，表示已经确定的最短路径。
- 判断B直接可达的顶点C，此时只有一条A->B->C。
- 判断顶点D：因为没有第二条可以到达顶点D的路径，所引也可以确定A~D的最短路径。
- 因为出现了可以到达顶点C的其它路径A->D->C，判断原先的路径大小与新的路径大小，即松弛操作：
- 判断顶点E：
1.1.4 初代代码实现
- 父类
/**
* 最短路径
* @return
*/
public abstract Map<V,E> shortestPath(V begin);
- 实现
@Override
public Map<V, E> shortestPath(V begin) {
return dijkstra(begin);
}
/**
* 最短路径 dijkstra
* @param begin
* @return
*/
private Map<V, E> dijkstra(V begin){
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
// 已经确定的最短路径集合 v - 节点值 ；E - 权值
Map<V, E> selectedPaths = new HashMap<>();
// 等待确认的集合，存储等待进行松弛的值
Map<Vertex<V, E>, E> paths = new HashMap<>();
// 初始化 paths 将begin的出度直接连的顶点加入到其中
for (Edge<V, E> edge : beginVertex.outEdges) {
paths.put(edge.to, edge.weight);
}
while (!paths.isEmpty()){
// 获取可以直接到达且权值最小的的顶点
Map.Entry<Vertex<V, E>, E> minEntry = getMinPath(paths);
Vertex<V, E> minVertex = minEntry.getKey();
// 加入到确定的路径中
selectedPaths.put(minVertex.v, minEntry.getValue());
// 删除等待确认的
paths.remove(minVertex);
// 松弛
for (Edge<V, E> edge : minVertex.outEdges) {
// 如果已经确定最短路径，不需要再进行松弛
if (selectedPaths.containsKey(edge.to.v)) continue;
E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
E oldWeight = paths.get(edge.to);
if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0){
paths.put(edge.to, newWeight);
}
}
}
// 删除到达起点的路径
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 获取当前最短路径
* @param paths
* @return
*/
private Map.Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> paths){
// 获取迭代器
Iterator<Map.Entry<Vertex<V, E>, E>> iterator = paths.entrySet().iterator();
Map.Entry<Vertex<V, E>, E> minEntry = iterator.next();
while (iterator.hasNext()){
Map.Entry<Vertex<V, E>, E> entry = iterator.next();
if (weightManager.compare(minEntry.getValue(),entry.getValue()) > 0){
minEntry = entry;
}
}
return minEntry;
}
1.1.5 代码优化
1.0 版本中只能返回顶点值和最小值，优化添加路径。
- 修改父类
/**
* 包含路径信息的最短路径
* @param begin
* @return
*/
public abstract Map<V,PathInfo<V, E>> shortestPathHaveInfo(V begin);
@Override
public Map<V, PathInfo<V, E>> shortestPathHaveInfo(V begin) {
return dijkstraHaveInfo(begin);
}
/**
* 路径信息封装
* @param <V>
* @param <E>
*/
public static class PathInfo<V, E>{
// 总权值信息
private E weight;
// 路径信息
List<EdgeInfo<V,E>> edges = new LinkedList<>();
public E getWeight() {
return weight;
}
public void setWeight(E weight) {
this.weight = weight;
}
public List<EdgeInfo<V, E>> getEdges() {
return edges;
}
public void setEdges(List<EdgeInfo<V, E>> edges) {
this.edges = edges;
}
@Override
public String toString() {
return "PathInfo{" +
"weight=" + weight +
", edges=" + edges +
'}';
}
}
- 封装松弛操作
/**
* 松弛
* @param edge 松弛的边
* @param fromPath 边的起点最短路径信息
* @param paths 其它待松弛的最短路径的信息
*/
private void relax(Edge<V, E> edge,PathInfo<V, E> fromPath ,Map<Vertex<V, E>, PathInfo<V, E>> paths){
E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
PathInfo<V, E> oldPath = paths.get(edge.to);
// 不符合松弛条件，忽略
if (oldPath != null && weightManager.compare(newWeight, oldPath.getWeight()) >= 0) return;
// 以前不存在该路径
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to, oldPath);
}else {
// 清空之前的路径信息
oldPath.getEdges().clear();
}
oldPath.setWeight(newWeight);
// 将之前已经选中的和当前选中的都加入到pathInfo
oldPath.getEdges().addAll(fromPath.edges);
oldPath.getEdges().add(edge.info());
paths.put(edge.to, oldPath);
}
- 实现
/**
* 最短路径 dijkstra ，包含路径信息
* @param begin
* @return
*/
private Map<V,PathInfo<V, E>> dijkstraHaveInfo(V begin){
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
// 已经确定的最短路径集合 v - 节点值 ；E - 权值
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
// 等待确认的集合，存储等待进行松弛的值
Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
// 初始化 paths 将begin的出度直接连的顶点加入到其中
for (Edge<V, E> edge : beginVertex.outEdges) {
PathInfo<V, E> pathInfo = new PathInfo<>();
// 将边和权值信息加入到 pathInfo 中
pathInfo.getEdges().add(edge.info());
pathInfo.setWeight(edge.weight);
paths.put(edge.to, pathInfo);
}
while (!paths.isEmpty()){
// 获取可以直接到达且权值最小的的顶点
Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPathHaveInfo(paths);
Vertex<V, E> minVertex = minEntry.getKey();
// 加入到确定的路径中
selectedPaths.put(minVertex.v, minEntry.getValue());
// 删除等待确认的
paths.remove(minVertex);
// 松弛
for (Edge<V, E> edge : minVertex.outEdges) {
// 如果已经确定最短路径，不需要再进行松弛
if (selectedPaths.containsKey(edge.to.v)) continue;
// 松弛
relax(edge, minPath, paths);
}
}
// 删除到达起点的路径
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 获取当前最短路径，包含路径信息
* @param paths
* @return
*/
private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPathHaveInfo(Map<Vertex<V, E>, PathInfo<V, E>> paths){
// 获取迭代器
Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
while (iterator.hasNext()){
Map.Entry<Vertex<V, E>, PathInfo<V, E>>entry = iterator.next();
if (weightManager.compare(minEntry.getValue().getWeight(), entry.getValue().getWeight()) > 0){
minEntry = entry;
}
}
return minEntry;
}
1.2 Bellman-Ford（贝尔曼-福特算法）
单源最短路径，支持负权边，能够检测出负权环。时间复杂度为：
O(EV)，E是边数量，V是顶点数量。
1.2.1 核心思想
对所有的边都进行V - 1次松弛操作（V是顶点数量）。
但对某边进行松弛操作的前提是需要知道开始顶点到当前边起点的最短路径。
- 最高效率：
下图是一个特殊的图：
最好的状态就是，从边A~B进行松弛操作：
- 对
A~B松弛操作，可以得出最短路径为**-3**； - 再对
B~C进行松弛操作，最短路径为A~B~C：-2； - 依次进行松弛，只需要对每条边进行依次松弛操作就可以求出最短路径。
- 最低效率：
下图是一个特殊的图：
如果从A~E开始进行松弛操作:
-
先对
D~E进行松弛操作，因为无法得到A~D的最短路径，因此松弛失败； -
再对
C~D进行松弛操作，也是因为无法得到A~C的最短路径，松弛也失败。 -
依次的进行松弛，必须要松弛到
A~B时松弛操作才能松弛成功；
-
再返回对
D~E进行松弛，依然无法得到A~D，松弛失败； -
因为已知
A~B的最短路径，所引这次A~C松弛成功；
-
依次的松弛下去，最少要对顶点
E松弛四次才能够成功计算出所有的最短路径。
1.2.2 执行流程
使用当前算法对下图计算从顶点A到各个顶点的最短路径，假设每次的松弛顺序都是（HashSet虽然不能保证对加入的元素有序的进行遍历，但在不执行添加和删除的操作下能够保证每次的遍历顺序是一致的）：D~C、D~F、B~C、E~D、E~F、B~E、A~E、A~B。
-
第一轮松弛操作：
-
D~C：松弛失败； -
D~F：松弛失败； -
B~C：松弛失败； -
E~D：松弛失败； -
E~F：松弛失败； -
B~E：松弛失败； -
A~E：松弛成功，最短路径为A~E：8； -
A~B：松弛成功，最短路径为A~B：10；
第一轮结果：
-
第二轮松弛操作：
-
D~C：松弛失败； -
D~F：松弛失败； -
B~C：松弛成功，最短路径为A~B~C：18； -
E~D：松弛成功，最短路径为A~E~D：15； -
E~F：松弛成功，最短路径为A~E~F：11； -
B~E：松弛成功，最短路径为A~B~E：5； -
A~E：松弛失败，最短路径为A~B~E：5； -
A~B：松弛失败，最短路径为A~B：10；
第二轮结果：
- 第三轮松弛操作：
- 第四轮松弛操作：
-可以看出，执行了V-1( 5 - 1 = 4)次松弛操作之后，可以得出所有的最短路径。
1.2.3 代码实现
@Override
public Map<V, PathInfo<V, E>> shortestPathHaveInfo(V begin) {
return bellmanFord(begin);
}
/**
* 最短路径 bellman-ford ，包含路径信息
* @param begin
* @return
*/
private Map<V,PathInfo<V, E>> bellmanFord(V begin){
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
// 已经确定的最短路径集合 :
// v - 节点值
// k- PathInfo<V, E>:
// k - 最短路径，
// v - 路径权值；
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
// 初始化当前顶点到自己的权值大小。
PathInfo<V, E> beginPath = new PathInfo<>();
beginPath.setWeight(weightManager.zero());
selectedPaths.put(begin,beginPath);
// 最多执行多少轮松弛
int count = vertices.size() - 1;
for (int i = 0; i < count; i++) {
for (Edge<V, E> edge : edges) {
// 获取当前路径起点已经存在的路径信息，如果不存在则不能进行松弛。
PathInfo<V, E> fromPath = selectedPaths.get(edge.from.v);
if (fromPath == null) continue;
// 传入当前边，起点路径信息，等待返回信息
relaxOfBellmanFord(edge, fromPath, selectedPaths);
}
}
// 如果已经完毕 v - 1 轮松弛操作，但依然可以对某些边进行松弛，就表示无法得出最短路径
// 即存在负权环。
for (Edge<V, E> edge : edges) {
PathInfo<V, E> fromPath = selectedPaths.get(edge.from.v);
if (fromPath == null) continue;
if (relaxOfBellmanFord(edge, fromPath, selectedPaths)) {
System.out.println("有负权环");
return null;
}
}
// 删除到自己的权值和路径相关
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛
* @param edge 需要进行松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
*/
private boolean relaxOfBellmanFord(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
// 计算新的权值
E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
// 获取之前的路径信息
PathInfo<V, E> oldPath = paths.get(edge.to.v);
// 如果路径不为空，并且新权值大于之前的权值，不需要松弛
if (oldPath != null
&& weightManager.compare(newWeight, oldPath.getWeight()) >= 0) return false;
// 保证oldPath不为空
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to.v, oldPath);
} else { // 清空原有的路径信息
oldPath.getEdges().clear();
}
// 重新添加路径 和 权值
oldPath.setWeight(newWeight);
oldPath.getEdges().addAll(fromPath.getEdges());
oldPath.getEdges().add(edge.info());
return true;
}
1.3 Floyd（弗洛伊德算法）
多源最短路径，能够求出任意两个顶点之间的最短路径，支持负权边。
时间复杂度O(V3 )，比执行V次Djikstra效率高。V是顶点数量。
1.3.1 核心思想
- 从顶点
i到顶点j的最短路径存在两种可能：
- 直接
i到j就是最短路径； - 从
i到其它的顶点k在而到达顶点j是最短路径。
- 此时我们检测，从
i到j的记录，与i到k再k到j的距离来判断哪个距离小，将距离小的再赋值给i到j。 - 当遍历完所有的节点后，
i到j的距离就是最短路径。
1.3.2 代码实现
- 修改父类：
/**
* 多源最短路径
* @return
*/
public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();
Map<V, Map<V, PathInfo<V, E>>>解释：
- 最外层
Map的k：最短路径起点； - 最外层
Map的v：以k为起点到达所有顶点的路径信息； - 内层
Mapk：终点； - 内存
Mapv：路径信息；
- 实现
@Override
public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
// 初始化
for (Edge<V, E> edge : edges) {
// 获取当前边起点的值
Map<V, PathInfo<V, E>> map = paths.get(edge.from.v);
// 如果为空，就新建一个map并且放到要返回的集合中
if (map == null) {
map = new HashMap<>();
paths.put(edge.from.v, map);
}
// 将该边的权值 和 起点顶点信息加入到map中
PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
pathInfo.getEdges().add(edge.info());
map.put(edge.to.v, pathInfo);
}
// 三层循环遍历
// v2 = k
// v1 = i
// v3 = j
vertices.forEach((V v2, Vertex<V, E> vertex2) -> {
vertices.forEach((V v1, Vertex<V, E> vertex1) -> {
vertices.forEach((V v3, Vertex<V, E> vertex3) -> {
// 如果其中有顶点相同就退出当前循环，不需要处理
if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
// 分别获取三条最短路径
// v1 -> v2
PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
if (path12 == null) return;
// v2 -> v3
PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
if (path23 == null) return;
// v1 -> v3
PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);
// 获取 i -> k + k -> j 权值
E newWeight = weightManager.add(path12.getWeight(), path23.getWeight());
// 如果是新值大或者是原先的值为空，就不要处理
if (path13 != null &&
weightManager.compare(newWeight, path13.getWeight()) >= 0) return;
if (path13 == null) { // 如果原先的值不存在，就新建一个变量，加入到map中
path13 = new PathInfo<V, E>();
paths.get(v1).put(v3, path13);
} else { // 清空原先存储的路径信息
path13.getEdges().clear();
}
// 重新赋值权值
path13.setWeight(newWeight);
// 设置心得最短路径：将 i -> k + k -> j 赋值给 i -> j
path13.getEdges().addAll(path12.getEdges());
path13.getEdges().addAll(path23.getEdges());
});
});
});
return paths;
}
/**
* 获取当前map中存储的最短路径
* @param from 起点
* @param to 终点
* @param paths map
* @return
*/
private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths) {
Map<V, PathInfo<V, E>> map = paths.get(from);
return map == null ? null : map.get(to);
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
6
0- 0
已为社区贡献2条内容
所有评论(0)