最短路徑是指兩個(gè)頂點(diǎn)之間權(quán)值之和最小的路徑, 但是不能有負(fù)權(quán)環(huán)
有權(quán)有向圖和無向圖最短路徑
無權(quán)有向圖無向圖路徑
有負(fù)權(quán)邊, A 到E 最短路徑, A -> B -> E
有負(fù)權(quán)路徑
有負(fù)權(quán)環(huán), 不存在最短路徑
有環(huán)的負(fù)權(quán)路徑
最短路徑典型應(yīng)用之一, 路徑規(guī)劃問題
3 個(gè)經(jīng)典算法
單源最短路徑
- Dijkstra
- Bellman-Ford
多源路徑
- Floyd
Dijkstra
用于計(jì)算一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑, 但是不能有負(fù)權(quán)邊
時(shí)間復(fù)雜度, 可以優(yōu)化至O(ElogV), E 是邊數(shù)量, V 是節(jié)點(diǎn)數(shù)量
假想所有頂點(diǎn)是石頭, 邊為連著兩塊石頭的繩子, 平放在桌子上
將石頭A, 提起, 遠(yuǎn)離桌面, B, D, C 會(huì)依次離開桌面
最后繃直的繩子就是A 到其他小石頭的最短路徑, 后離開桌面的小石頭, 都是被先離開桌面的小石頭拉起的
dijkstra想象成石頭
石頭A提起
執(zhí)行過程
綠色代表已經(jīng)離開桌面, 確定了最短路徑
紅色更新最短路徑信息
dijkstra執(zhí)行過程1
dijkstra執(zhí)行過程2
dijkstra執(zhí)行過程3
松弛操作(Relaxation): 更新兩個(gè)頂點(diǎn)之間最短路徑, 找出更短的路徑
抽象類
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 已經(jīng)離開桌面, 就沒必要進(jìn)行松弛操作
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 需要進(jìn)行松弛的邊
* @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
支持負(fù)權(quán)邊, 可以檢測(cè)出是否有負(fù)權(quán)環(huán)
原理: 對(duì)所有的邊進(jìn)行V - 1 次松弛操作, 得到所有可能的最短路徑
時(shí)間復(fù)雜度O(EV), E 為邊數(shù)量, V 是節(jié)點(diǎn)數(shù)量
例如, 對(duì)下圖, 所有邊盡一次松弛, 找出A 到所有頂點(diǎn)最短路徑, 順序從左到右
A到所有頂點(diǎn)的松弛操作
最壞情況, 恰好每次從右到左對(duì)邊進(jìn)行松弛操作, 所有邊進(jìn)行V - 1 次松弛操作, 才能計(jì)算出A 到其他所有頂點(diǎn)最短路徑
最壞情況松弛
松弛操作
松弛操作
每次松弛順序DC, DF, BC, ED, EF, BE, AE, AB
執(zhí)行過程1
執(zhí)行過程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("有負(fù)權(quán)環(huán)");
return null;
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛
* @param edge 需要進(jìn)行松弛的邊
* @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 個(gè)頂點(diǎn)之間的最短路徑, 支持負(fù)權(quán)邊
時(shí)間復(fù)雜度O(V^3), 效率比執(zhí)行V 次Dijkstra 算法要好
原理:
從任意頂點(diǎn)i 到任意頂點(diǎn) j 的最短路徑包括
- 直接i 到j(luò)
- 從i 經(jīng)過若干頂點(diǎn)到j(luò)
假設(shè)dist(i, j)為頂點(diǎn)i 到j(luò) 的最短路徑距離
對(duì)于每一個(gè)頂點(diǎn)k, 檢查dist(i, k) + dist(k, j) < dist(i, j) 是否成立
如果成立, 證明從i 到k 再到j(luò) 的路徑比i 直接到j(luò) 的路徑, 設(shè)置dist(i, j) = dist(i, k) + dist(k, j)
遍歷所有節(jié)點(diǎn)k, dist(i, j) 中記錄的便是i 到j(luò) 的最短路徑的距離
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);
}
