一、最短路径基础知识
1、最短路径的定义是什么？
- 最短路径(Shortest Path)：两顶点之间权值之和最小的路径(有向图、无向图均适用，不能有
负权环)
image.png
2、最短路径适用于无权图吗？
- 适合：无权图相当于是全部边权值为 1 的有权图
image.png
3、如果有负权边，存在最短路径吗？
- 有负权边，但是没有负权环时，存在最短路径
image.png
4、为什么有负权环时不存在最短路径？
- 经过负权环，路径可以无限短
image.png
5、最短路径的常见算法有哪些？（单源、多源）
image.png
二、Dijkstra 算法
1、Dijkstra 算法是计算单源还是多源？什么情况不能使用？
- Dijkstra 属于单源最短路径算法，用于计算一个顶点到其他所有顶点的最短路径
- 使用前提：不能有
负权边
image.png
2、Dijkstra 算法的等价思考，非常有助于帮助理解算法的核心思想？
- 核心结论(关键信息)：
-
后离开桌面的小石头都是被先离开桌面的小石头拉起来的
image.png
核心结论
3、Dijkstra - 执行过程？
image.png
image.png
image.png
4、什么叫做松弛操作？（感觉这个取名字的思路不错）
-
松弛操作的意思：尝试找出更短的路径
image.png
5、思考：遍历 map 时，希望获取 value 值最小的那个 key 怎么办？
- 最直接的思路
private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
Entry<Vertex<V, E>, E> minEntry = null;
for (Entry<Vertex<V, E>, E> entry : relaxVertices.entrySet()) {
if (minEntry == null) {
minEntry = entry;
} else if (weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
minEntry = entry;
}
}
return minEntry;
}
- 进化版本一：合并 if else
private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
Entry<Vertex<V, E>, E> minEntry = null;
for (Entry<Vertex<V, E>, E> entry : relaxVertices.entrySet()) {
if (minEntry == null || weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
minEntry = entry;
}
}
return minEntry;
}
- 进化版本二：使用迭代器
private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
Iterator<Entry<Vertex<V, E>, E>> iterator = relaxVertices.entrySet().iterator();
if (!iterator.hasNext()) return null;
Entry<Vertex<V, E>, E> minEntry = iterator.next();
while (iterator.hasNext()) {
Entry<Vertex<V, E>, E> entry = iterator.next();
if (weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
minEntry = entry;
}
}
return minEntry;
}
6、Dijkstra 代码实现
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.put(beginVertex, new PathInfo<>(weightManager.zero()));
while (!paths.isEmpty()) {
Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
// minVertex离开桌面
Vertex<V, E> minVertex = minEntry.getKey();
PathInfo<V, E> minPath = minEntry.getValue();
selectedPaths.put(minVertex.value, minPath);
paths.remove(minVertex);
// 对它的minVertex的outEdges进行松弛操作
for (Edge<V, E> edge : minVertex.outEdges) {
// 如果edge.to已经离开桌面，就没必要进行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;
relaxForDijkstra(edge, minPath, paths);
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛
* @param edge 需要进行松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
*/
private void relaxForDijkstra(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());
}
网友评论