最短路径是指两个顶点之间权值之和最小的路径, 但是不能有负权环
有权有向图和无向图最短路径
无权有向图无向图路径
有负权边, A 到E 最短路径, A -> B -> E
有负权路径
有负权环, 不存在最短路径
有环的负权路径
最短路径典型应用之一, 路径规划问题
3 个经典算法
单源最短路径
- Dijkstra
- Bellman-Ford
多源路径
- Floyd
Dijkstra
用于计算一个顶点到其他所有顶点的最短路径, 但是不能有负权边
时间复杂度, 可以优化至O(ElogV), E 是边数量, V 是节点数量
假想所有顶点是石头, 边为连着两块石头的绳子, 平放在桌子上
将石头A, 提起, 远离桌面, B, D, C 会依次离开桌面
最后绷直的绳子就是A 到其他小石头的最短路径, 后离开桌面的小石头, 都是被先离开桌面的小石头拉起的
dijkstra想象成石头
石头A提起
执行过程
绿色代表已经离开桌面, 确定了最短路径
红色更新最短路径信息
dijkstra执行过程1
dijkstra执行过程2
dijkstra执行过程3
松弛操作(Relaxation): 更新两个顶点之间最短路径, 找出更短的路径
抽象类
public abstract class Graph<V, E> {
protected WeightManager<E> weightManager;
public Graph() {}
public Graph(WeightManager<E> weightManager) {
this.weightManager = weightManager;
}
public abstract int edgesSize();
public abstract int verticesSize();
public abstract void addVertex(V v);
public abstract void addEdge(V from, V to);
public abstract void addEdge(V from, V to, E weight);
public abstract void removeVertex(V v);
public abstract void removeEdge(V from, V to);
public abstract void bfs(V begin, VertexVisitor<V> visitor);
public abstract void dfs(V begin, VertexVisitor<V> visitor);
public abstract Set<EdgeInfo<V, E>> mst();
public abstract List<V> topologicalSort();
// public abstract Map<V, E> shortestPath(V begin);
public abstract Map<V, PathInfo<V, E>> shortestPath(V begin);
public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();
public interface WeightManager<E> {
int compare(E e1, E e2);
E add(E e1, E e2);
E zero();
}
public interface VertexVisitor<V> {
boolean visit(V v);
}
public static class PathInfo<V, E> {
protected E weight;
protected List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();
public PathInfo() {}
public PathInfo(E weight) {
this.weight = weight;
}
public E getWeight() {
return weight;
}
public void setWeight(E weight) {
this.weight = weight;
}
public List<EdgeInfo<V, E>> getEdgeInfos() {
return edgeInfos;
}
public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
this.edgeInfos = edgeInfos;
}
@Override
public String toString() {
return "PathInfo [weight=" + weight + ", edgeInfos=" + edgeInfos + "]";
}
}
public static class EdgeInfo<V, E> {
private V from;
private V to;
private E weight;
public EdgeInfo(V from, V to, E weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public V getFrom() {
return from;
}
public void setFrom(V from) {
this.from = from;
}
public V getTo() {
return to;
}
public void setTo(V to) {
this.to = to;
}
public E getWeight() {
return weight;
}
public void setWeight(E weight) {
this.weight = weight;
}
@Override
public String toString() {
return "EdgeInfo [from=" + from + ", to=" + to + ", weight=" + weight + "]";
}
}
}
private Map<V, PathInfo<V, E>> dijkstra(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
// 初始化paths
for (Edge<V, E> edge : beginVertex.outEdges) {
PathInfo<V, E> path = new PathInfo<>();
path.weight = edge.weight;
path.edgeInfos.add(edge.info());
paths.put(edge.to, path);
}
while (!paths.isEmpty()) {
Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
Vertex<V, E> minVertex = minEntry.getKey();
PathInfo<V, E> minPath = minEntry.getValue();
selectedPaths.put(minVertex.value, minEntry.getValue());
paths.remove(minVertex);
for (Edge<V, E> edge : minVertex.outEdges) {
// 如果edge.to 已经离开桌面, 就没必要进行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;
relaxDijkstra(edge, minPath, paths);
// 新的最短路径, beginVertex 到edge.from 的最短路径 + edge.weight
// E newWeight = weightManager.add(minEntry.getValue().weight, edge.weight);
// // 以前的最短路径, beginVertex 到edge.to 的最短路径
// PathInfo<V, E> oldPath = paths.get(edge.to);
// if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) continue;
// if (oldPath == null) {
// oldPath = new PathInfo<>();
// paths.put(edge.to, oldPath);
// } else {
// oldPath.edgeInfos.clear();
// }
//
// oldPath.weight = newWeight;
// oldPath.edgeInfos.addAll(minEntry.getValue().edgeInfos);
// oldPath.edgeInfos.add(edge.info());
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛
* @param edge 需要进行松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths
*/
private void relaxDijkstra(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths) {
// 新的最短路径, beginVertex 到edge.from 的最短路径 + edge.weight
E newWeight = weightManager.add(fromPath.weight, edge.weight);
// 以前的最短路径, beginVertex 到edge.to 的最短路径
PathInfo<V, E> oldPath = paths.get(edge.to);
if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to, oldPath);
} else {
oldPath.edgeInfos.clear();
}
oldPath.weight = newWeight;
oldPath.edgeInfos.addAll(fromPath.edgeInfos);
oldPath.edgeInfos.add(edge.info());
}
/**
* 返回paths 中的最小路径
* @param path
* @return
*/
private Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
Iterator<Entry<Vertex<V, E>, PathInfo<V, E>>> it = paths.entrySet().iterator();
Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = it.next();
while (it.hasNext()) {
Entry<Vertex<V, E>, PathInfo<V, E>> entry = it.next();
if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
minEntry = entry;
}
}
return minEntry;
}
Bellman-Ford
支持负权边, 可以检测出是否有负权环
原理: 对所有的边进行V - 1 次松弛操作, 得到所有可能的最短路径
时间复杂度O(EV), E 为边数量, V 是节点数量
例如, 对下图, 所有边尽一次松弛, 找出A 到所有顶点最短路径, 顺序从左到右
A到所有顶点的松弛操作
最坏情况, 恰好每次从右到左对边进行松弛操作, 所有边进行V - 1 次松弛操作, 才能计算出A 到其他所有顶点最短路径
最坏情况松弛
松弛操作
松弛操作
每次松弛顺序DC, DF, BC, ED, EF, BE, AE, AB
执行过程1
执行过程2
正常过程3
private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));
int count = vertices.size() - 1;
for (int i = 0; i < count; i++) {
for (Edge<V, E> edge : edges) {
PathInfo<V, E> pathFrom = selectedPaths.get(edge.from.value);
// if (pathFrom == null) continue;
relax(edge, pathFrom, selectedPaths);
}
}
for (Edge<V, E> edge : edges) {
PathInfo<V, E> pathFrom = selectedPaths.get(edge.from.value);
// if (pathFrom == null) continue;
if (relax(edge, pathFrom, selectedPaths)) {
System.out.println("有负权环");
return null;
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛
* @param edge 需要进行松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths
*/
private boolean relax(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
// 新的最短路径, beginVertex 到edge.from 的最短路径 + edge.weight
E newWeight = weightManager.add(fromPath.weight, edge.weight);
// 以前的最短路径, beginVertex 到edge.to 的最短路径
PathInfo<V, E> oldPath = paths.get(edge.to.value);
if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to.value, oldPath);
} else {
oldPath.edgeInfos.clear();
}
oldPath.weight = newWeight;
oldPath.edgeInfos.addAll(fromPath.edgeInfos);
oldPath.edgeInfos.add(edge.info());
return true;
}
Floyd
多源路径算法, 能够求出任意2 个顶点之间的最短路径, 支持负权边
时间复杂度O(V^3), 效率比执行V 次Dijkstra 算法要好
原理:
从任意顶点i 到任意顶点 j 的最短路径包括
- 直接i 到j
- 从i 经过若干顶点到j
假设dist(i, j)为顶点i 到j 的最短路径距离
对于每一个顶点k, 检查dist(i, k) + dist(k, j) < dist(i, j) 是否成立
如果成立, 证明从i 到k 再到j 的路径比i 直接到j 的路径, 设置dist(i, j) = dist(i, k) + dist(k, j)
遍历所有节点k, dist(i, j) 中记录的便是i 到j 的最短路径的距离
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.value);
if (map == null) {
map = new HashMap<>();
paths.put(edge.from.value, map);
}
PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
pathInfo.edgeInfos.add(edge.info());
map.put(edge.to.value, pathInfo);
}
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);
E newWeight = weightManager.add(path12.weight, path23.weight);
if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0) return;
if (path13 == null) {
path13 = new PathInfo<>();
paths.get(v1).put(v3, path13);
} else {
path13.edgeInfos.clear();
}
path13.weight = newWeight;
path13.edgeInfos.addAll(path12.edgeInfos);
path13.edgeInfos.addAll(path23.edgeInfos);
});
});
});
return paths;
}
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);
}
