14.最短路径
2019-10-20 本文已影响0人
哈哈大圣
最短路径Short Path
一、相关概念
最短路径是针对于有权图进行分析
1). 常见应用场景
最短路径的应用.png
本次讨论是单源最短路径(Single Source Shortest Path)，可以一个带权图中一个点到图中任意一个点的最短路径。
2).【松弛操作】
松弛操作.png
如上图所示，从节点0到节点1，节点0的一个邻边就是节点1，但是可以经过邻边节点2再到节点1，这种通过折中的方式到达邻边就是松弛操作。松弛操作是最短路径的求解核心
二、Dijkstra单元最短路径算法
1). 算法前提以及特点
- 所求图中不能有负权边
- 算法复杂度为O(Elog(V)); E为边数，V为点数
2). 算法思想
以一个图例说明算法的思想
Dijkstra单源最短路径算法示例.png
如图，起始点为点0，进行初始化，遍历点0的所有邻边，此时从点0到点1的距离为5 (后续的举例都以点0为参考点)，到点2的距离为2，到点3的距离为6 (将这些值放入索引堆中),由于图中不存在负权边，所以点0到点2最短路径就是2，因为，如果进行松弛操作，发现到点1,点3的距离已经大于2了，由于没有负权边，所以距离不可能大于2；此时再从索引堆中弹出最小的，也就是点2，然后遍历节点2所有没有被标记找到最短路径的节点，此时发现到点1的距离为3，覆盖之前的记录，到点4的距离为7，到点3的距离5，小于之前的6，覆盖掉；按照之前的逻辑，目前邻边最短的就是到点1，距离为3，因为从点4，和点3再中转到点1就不可能小于3了，将点1弹出，然后遍历点1所有没有被标记找到最短路径的节点，只有点4，此时距离点4为4，而且在堆中已经最小，所以点4的最短路径确定，弹出；最后只有点3，访问点3的所有邻边，同样的逻辑，发现已有的距离5最小，则点3确定。
3). 代码实现
-
辅助数据结构IndexMinHeap、Edge参考文章头链接
-
Dijkstra
import java.util.Iterator;
import java.util.Stack;
import java.util.Vector;
/**
* @author Liucheng
* @since 2019-10-20
*/
public class Dijkstra<Weight extends Number & Comparable> {
private WeightedGraph G; // 图的引用
private int s; // 起始点
private Number[] distTo; // distTo[i]存储从起始点s到i的最短路径长度
private IndexMinHeap<Weight> heap; // 寻找最短权值的最小索引堆。
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
private Edge<Weight>[] from; // from[i]记录最短路径中, 到达i点的边是哪一条,可以用来恢复整个最短路径
// 构造函数
public Dijkstra(WeightedGraph graph, int s) {
this.G = graph;
this.s = s;
this.distTo = new Number[graph.V()];
this.heap = new IndexMinHeap<>(graph.V());
this.marked = new boolean[graph.V()];
this.from = new Edge[graph.V()];
this.shortestRoad();
}
// 使用Dijkstra算法计算最短路径
private void shortestRoad() {
// 对起始点s进行初始化,【s -> s】 点为对应的最短路径
this.distTo[s] = 0.0;
this.from[s] = new Edge<>(s, s, (Weight) this.distTo[s]);
this.heap.insert(s, (Weight) this.distTo[s]);
this.marked[s] = true;
// 执行Dihkstra算法
while (!heap.isEmpty()) {
// 取出堆中的最小值，最小值对应节点就是被找到对应最短路径的点
int v = heap.extractMinIndex();
// 从前面的循环中,v点对应的边已经添加到了from数组中，此处标记为true,就确定了s点到v点的最短路径！
marked[v] = true;
// 对v的所有相邻节点进行更新
Iterator iterator = this.G.adj(v).iterator();
while (iterator.hasNext()) {
Edge<Weight> e = (Edge<Weight>)iterator.next();
// 当前访问点的边的另一点
int w = e.other(v);
// 如果从s点到w点的最短路径还没有找到
if (!marked[w]) {
// distTo[v]就是s到v的最短距离
Number curDis = distTo[v].doubleValue() + e.wt().doubleValue();
/* 如果记录最短距离数组中对应的值为空，表示还没有访问到此点；
如果存在，则判断新的路径是否比原来找到的更短*/
if (distTo[w] == null || curDis.doubleValue() < distTo[w].doubleValue()) {
// 更新最短的值
distTo[w] = curDis;
/* 记录当前到达w点的上一节点e,
后续执行可能被更短的路径方式覆盖，也有可能此方式就为最短路径*/
from[w] = e;
if (heap.contain(w)) {
heap.change(w, (Weight)curDis);
} else {
// 对应distTo[w] == null的情况
heap.insert(w, (Weight)curDis);
}
}
}
}
}
}
// 返回从s点到w点的最短路径的长度
public Number shortestPathTo(int w) {
return distTo[w];
}
// 判断从s点到w点是否联通
private boolean hasPathTo(int w) {
return marked[w];
}
// 寻找从s到w的最短路径，将整个路径经过的边存放在vec中
private Vector<Edge<Weight>> shortestPath(int w) {
assert this.hasPathTo(w);
// 通过from数组逆向查找放在栈中
Stack<Edge<Weight>> stack = new Stack<>();
Edge<Weight> weightEdge = this.from[w];
while (weightEdge.v() != this.s) {
stack.push(weightEdge);
weightEdge = from[weightEdge.v()];
}
stack.push(weightEdge);
Vector<Edge<Weight>> vec = new Vector<>(stack.size());
while (!stack.empty()) {
vec.add(stack.pop());
}
return vec;
}
// 打印出从s点到w点的路径
public void showPath(int w) {
assert w >= 0 && w < G.V();
assert hasPathTo(w);
Vector<Edge<Weight>> path = shortestPath(w);
for( int i = 0 ; i < path.size() ; i ++ ){
System.out.print( path.elementAt(i).v() + " -> ");
if( i == path.size()-1 )
System.out.println(path.elementAt(i).w());
}
}
public static void main(String[] args) {
String filename = Thread.currentThread().getContextClassLoader().getResource("testG1.txt").getPath();
int V = 5;
SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
// Dijkstra最短路径算法同样适用于有向图
//SparseGraph<int> g = SparseGraph<int>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
System.out.println("Test Dijkstra:\n");
Dijkstra<Integer> dij = new Dijkstra<Integer>(g,0);
for( int i = 1 ; i < V ; i ++ ){
if(dij.hasPathTo(i)) {
System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
dij.showPath(i);
}
else
System.out.println("No Path to " + i );
System.out.println("----------");
}
}
}
- 测试文件testG1.txt
5 8
0 1 5
0 2 2
0 3 6
1 4 1
2 1 1
2 4 5
2 3 3
3 4 2
- 测试结果
/*
Test Dijkstra:
Shortest Path to 1 : 3.0
0 -> 2 -> 1
----------
Shortest Path to 2 : 2.0
0 -> 2
----------
Shortest Path to 3 : 5.0
0 -> 2 -> 3
----------
Shortest Path to 4 : 4.0
0 -> 2 -> 1 -> 4
----------
*/
三、负权边 Bellman-Ford单源最短路径算法
1). 算法思想以及注意事项
- 不能存在负权环：在一个负权环中持续计算，就没有最短路径了(比如从点1到点2再到点3权值和为-1，每次转一圈就减1)
- 虽然图中有负权边则无法计算出最短路径，但是可以检测是否有负权环；
- 复杂度O(EV)
- 从一点到另外一点的最短路径，最多经过所有的V个顶点，有V-1条边，如果可以经过V及其以上的边，那么图中就一定存在负权环。
算法思想: 利用上述4点的特性，假设最坏的情况就是到每个边的最短路径有(v-1)条边 (不可能成立)，可以对所有的点都进行(v-1)次松弛操作，必然可以找到从原点到该点的最短路径！如果再对每个点进行松弛操作还发现有更短的边，则此图中必有负权边！
2). 代码实现
import java.util.Iterator;
import java.util.Stack;
import java.util.Vector;
/**
* 使用BellmanFord算法求最短路径
* @author Liucheng
* @since 2019-10-20
*/
public class BellmanFord<Weight extends Number & Comparable> {
private WeightedGraph G; // 图的引用
private int s; // 起始点
private Number[] distTo; // distTo[i]存储从起始点s到i的最短路径长度
Edge<Weight>[] from; // from[i]记录最短路径中, 到达i点的边是哪一条,可以用来恢复整个最短路径
boolean hasNegativeCycle; // 标记图中是否有负权环
// 构造函数
public BellmanFord(WeightedGraph graph, int s) {
// 初始化
this.G = graph;
this.s = s;
this.distTo = new Number[G.V()];
this.from = new Edge[G.V()];
this.shortestRoad();
}
// 使用BellmanFord算法求最短路径
private void shortestRoad() {
/*设置distTo[s] = 0,并且让from[s]不为null,
表示初始节点科大且距离为0*/
distTo[s] = 0.0;
from[s] = new Edge<>(s, s, (Weight)(Number)(0.0));
/*Bellman-Ford的过程
进行V-1次循环, 每一次循环求出从起点到其余所有点
最多使用pass步可到达的最短距离*/
for (int pass = 1; pass < G.V(); pass++) {
/*每次循环中对所有的边进行一遍松弛操作
遍历所有边的方式是先遍历所有的顶点,
然后遍历和所有顶点相邻的所有边*/
for (int i = 0; i < G.V(); i++) {
// 使用迭代器遍历和所有顶点相邻的所有边
Iterator iterator = G.adj(i).iterator();
while (iterator.hasNext()) {
Edge<Weight> e = (Edge<Weight>)iterator.next();
/*对于每一个边首先判断e.v()可达
之后看如果e.w()以前没有到达过，显然我们可以更新distTo[e.w()]
或者e.w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离,
即可以进行一次松弛操作, 我们也可以更新distTo[e.w()]*/
if (from[e.v()] != null &&
(from[e.w()] == null ||
distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()
)
) {
distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
from[e.w()] = e;
}
}
}
}
this.hasNegativeCycle = detectNegativeCycle();
}
// 判断图中是否有负权环
private boolean detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
for( Object item : G.adj(i) ){
Edge<Weight> e = (Edge<Weight>)item;
if(from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue())
return true;
}
}
return false;
}
// 返回图中是否有负权环
public boolean negativeCycle() { return hasNegativeCycle; }
// 返回从s点到w点的最短路径长度
public Number shortestPathTo(int w) {
assert w >= 0 && w < G.V();
assert !hasNegativeCycle;
assert hasPathTo(w);
return distTo[w];
}
// 判断从s点到w点是否联通
private boolean hasPathTo(int w) {
return from[w] != null;
}
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
private Vector<Edge<Weight>> shortestPath(int w){
assert w >= 0 && w < G.V() ;
assert !hasNegativeCycle ;
assert hasPathTo(w) ;
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
Edge<Weight> e = from[w];
while( e.v() != this.s ){
s.push(e);
e = from[e.v()];
}
s.push(e);
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
while( !s.empty() ){
e = s.pop();
res.add(e);
}
return res;
}
// 打印出从s点到w点的路径
public void showPath(int w){
assert(w >= 0 && w < G.V());
assert(!hasNegativeCycle);
assert(hasPathTo(w));
Vector<Edge<Weight>> res = shortestPath(w);
for( int i = 0 ; i < res.size() ; i ++ ){
System.out.print(res.elementAt(i).v() + " -> ");
if( i == res.size()-1 )
System.out.println(res.elementAt(i).w());
}
}
}
四、总结
-
Bellman-Ford算法的优化：利用队列数据结构queue-based bellman-ford算法
-
单源最短路径算法
单源最短路径算法.png
确定起始点，到任意其他点
- 所有对最短路径算法
- Folyed算法，处理无负权环的图，O(V^3)
任意两点的最短路径
- 最长路径算法
最长路径算法.png
