算法-21-最短路径（Dijkstra+最优算法+Bellman-Ford）

目录

1、定义

1.1、性质

2、数据结构

2.1、有向边的代码

2.2、加权有向的图的代码

3、核心思想

4、Dijkstra算法

5、求最短路径的最优算法

6、通用最短路径算法---Bellman-Ford

---

1、定义

我们生活中经常会使用地图来查找我们到达目的的路线，而我们希望每次走的都是最短路线，而我们这一节将要学习的就是在一个图中，寻找a点到b点的最短路径。

最短路径： 找到从一个顶点到达另一个顶点的成本最小的路径。

1.1、性质

这里我们使用加权有向图的模型来学习计算最短路径的方法。加权就是在两个顶点之间的边上加上权重，这样我们不仅要找到从a点到b点的路径，还要找到权值最小的那一条。

下图就是一个加权有向图：从0点到6点的最短路径就是0-->2-->7-->3-->6 ，权值之和最小等于：1.51

我们在利用加权有向图模型去求最短路径的时候，需要注意以下几点：

1. 路径是有向的。
2. 权重不一定等价于边的长短。
3. 并不是所有点都是可达的，如果a点到b点没有可达的路径，那么就不存在最短路径，我们后面学习的算法都将建立在这个图所有点都是可达的情况下。
4. 边的负权重将会是计算最短路径变得非常麻烦。
5. 最短路径不一定是唯一的，可能有多条，我们只找到一条就行。

2、数据结构

这里我们的加权有向图在上一节加权无向图的基础上进行一定修改，就可以得到保存加权有向图的数据类型。

DirectedEdge类来存储边、边的权值、边的两个顶点。

EdgeWeightedDigraph 类 中有一个 数据链表，数组用来存储每个顶点，链表用来存储每个顶点指向的边。

2.1、有向边的代码

public class DirectedEdge {private final int v;            // 边的起点private final int w;            // 边的终点private final double weight;    // 边的权重public DirectedEdge(int w, int v, double weight) {this.w = w;this.v = v;this.weight = weight;}public int from() {return v;}public int to() {return w;}public double weight() {return weight;}
}

2.2、加权有向的图的代码

public class EdgeWeightedDigraph {private final int V; // 顶点的数量private int E; // 边的数量private final Bag<DirectedEdge>[] adj; // 邻接表public EdgeWeightedDigraph(int v) {V = v;adj = new Bag[v];for (int i = 0; i < v; i++) {adj[i] = new Bag<>();}}/*** 将边添加到 邻接表中*/public void addEdge(DirectedEdge edge) {int v = edge.from();adj[v].add(edge);E++;}public int V() {return V;}public int E() {return E;}public Iterable<DirectedEdge> adj(int v){return adj[v];}/*** 将有向图中的所有边都存储到一个Bag中并返回*/public Iterable<DirectedEdge> edges(){Bag<DirectedEdge> edges=new Bag<>();for (int i=0;i<V;i++){for (DirectedEdge e:adj[i]){edges.add(e);}}return edges;}
}

3、核心思想

前面一节我们讲了最小生成树的计算方法，它的思想就是找到通往每个顶点的最短边，因为我们找到了通往所有顶点的边，那么这些边也能连成一棵树，这棵树就是最小生成树。

而我们最短路径的思想就是从起点出发， 不断向外延伸，而且我们延伸的路径是权值之和最短了那条。那么怎么找到权值之和最短的那条呢？

因为我们是在有向图中进行的，那么每条边都是有指向的；

1、假设通往 d点有 abc三个点，如果 到从起点s到abc三点的权值之和分别是distTo[a] 、distTo[b]、distTo[c] ；

2、a--->d ,b-->d, c--->d 的权值分别为 weight[a]、 weight[b]、 weight[c]   ；

3、我们需要找到distTo[a] +weight[a]、distTo[b] +weight[b]、distTo[c] +weight[c] 最小的那个，这样是不是我们就找到到d点的最短路径之和了。

4、然后我们需要从d点不断的倒退，倒退到起点s，从s出发，通往所有顶点w,都要取的权值之和最小的那条路径，这样到最后，从s点通往所有的顶点的路径之和都是最短的了。

  private void relax(EdgeWeightedDigraph G, int v) {for (DirectedEdge e : G.adj(v)) { //遍历从v点通往的所有w点int w = e.to();  if (distTo[v] + e.weight() < distTo[w]) { //如果通往w点的路径比之前那个v点通往的路径之和短，那我们就将通往w点的路径换成从这个v点出发。distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;}}}

4、Dijkstra算法

Dijkstra算法在求最短路径的时候有一个前提，那就是这个加权有向不能有权值为负的边，如果有，这个算法就不适用了。

在一幅含有 V 个顶点和 E 条边的加权有向图中，使用 Dijkstra 算法计算根结点 为给定起点的最短路径树所需的空间与 V 成正比，时间与 ElogV 成正比(最坏情况下)。

public class DijkstraSP {private DirectedEdge[] edgeTo; //保存最短路径的所有边private double[] distTo;       //保存通往v点的最短路径的权值之和private IndexMinPQ<Double> pq; //索引优先队列，存放通往各个顶点的最短路径的权值之和，并且每次可以拿到最小的权值之和public DijkstraSP(EdgeWeightedDigraph G, int s) {edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];pq = new IndexMinPQ<>(G.V());for (int i = 0; i < distTo.length; i++) { // 1、先将通往每个顶点的路径权值设为无无穷大distTo[i] = Double.POSITIVE_INFINITY;}distTo[s] = 0.0; // 2、初始化起点，并添加到优先队列中pq.insert(s, 0.0);while (!pq.isEmpty()) { // 3、不断的从优先队列中取路径之和最小的那条。并返回路径通往的v点relax(G, pq.delMin());}}private void relax(EdgeWeightedDigraph G, int v) {for (DirectedEdge e : G.adj(v)) {//遍历从v点通往的所有w点int w = e.to();if (distTo[v] + e.weight() < distTo[w]) {//如果通往w点的路径比之前那个v点通往的路径之和短，那我们就将通往w点的路径换成从这个v点出发。distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if (pq.contains(w))      pq.change(w, distTo[w]);elsepq.insert(w, distTo[w]);}}}/*** 是否有通往v点的最短路径*/public boolean hasPathTo(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}/*** 通往v最短路径的权值之和，如果没有最短路径就会返回无穷大*/public double distTo(int v) {return distTo[v];}/*** 返回从s点到v点的最短路径的所有边*/public Iterable<DirectedEdge> pathTo(int v){if (!hasPathTo(v)) return null;Stack<DirectedEdge> path=new Stack<>();for (DirectedEdge e=edgeTo[v];e!=null;e=edgeTo[e.from()]){path.push(e);}return path;}
}

上面的代码完成了从起点s到所有顶点的最短路径，但如果我们遇到求任意两个顶点之间的最短路径的话，就需要稍微完善以下代码。

public class DijkstraAllPairsSP {private   DijkstraSP[] all;public DijkstraAllPairsSP(EdgeWeightedDigraph G) {all = new DijkstraSP[G.V()];for (int v = 0; v < G.V(); v++) {all[v]=new DijkstraSP(G,v);}}public Iterable<DirectedEdge> path(int s, int v) {return all[s].pathTo(v);}public double dist(int s,int v) {return all[s].distTo(v);}
}

5、求最短路径的最优算法

注意：因为该算法是利用了拓扑排序，所以适用该算法有一个前提，那就是该加权有向图不能有环。

该算法的优点：

• 能够在线性时间内解决单点最短路径问题;   （E+V成正比的时间内）
• 能够处理负权重的边;
• 能够解决相关的问题，例如找出最长的路径。

该算法的缺点：

• 该算法在有环的有向图中无法适用；
• 所得到的最短路径不是起点s到其他顶点的最短路径，而是拓扑排序的顶点到其他顶点的最短路径，如下图起点是0，但是得到的路径起点是5.

对于最短路径问题，基于拓扑 排序的方法比 Dijkstra 算法快的倍数与 Dijkstra 算法中所有优先队列操作的总成本成正比。

public class AcyclicSP {private final DirectedEdge[] edgeTo;private final double[] distTo;public AcyclicSP(EdgeWeightedDigraph G,int s){edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];for (int i = 0; i < distTo.length; i++) {distTo[i]=Double.POSITIVE_INFINITY;}Topological top=new Topological(G);for (int v : top.order()) {relax(G,v);}}private void relax(EdgeWeightedDigraph G, int v) {for (DirectedEdge e : G.adj(v)) {int w=e.to();if (distTo[v] + e.weight() < distTo[w]) {distTo[w]=distTo[v]+e.weight();edgeTo[w]=e;}}}/*** 是否有通往v点的最短路径*/public boolean hasPathTo(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}/*** 通往v最短路径的权值之和，如果没有最短路径就会返回无穷大*/public double distTo(int v) {return distTo[v];}/*** 返回从s点到v点的最短路径的所有边*/public Iterable<DirectedEdge> pathTo(int v){if (!hasPathTo(v)) return null;Stack<DirectedEdge> path=new Stack<>();for (DirectedEdge e=edgeTo[v];e!=null;e=edgeTo[e.from()]){path.push(e);}return path;}
}

6、通用最短路径算法---Bellman-Ford

前面我们学的两个算法，Dijkstra算法不能有负权重环，最优算法则不能有环，这对于任意加权有向图来说，还是存在这一些限制，而且对于给定我们一个加权有向图来说，我们是不知道他们是否符合这些限制条件的。这时候我们就需要一个更加通用的算法来解决所有的特殊情况的加权有向图。

加权有向图中的负权重环是一个总权重(环上的所有边的权重之和)为负的有向环。

当我们在研究含有负权重边的有向图时，如果该图中含有一个权重为负的环，那么最短路径的概念就失去意义了。如下图，除了边 5 → 4 的权重为 -0.66 。这里，环4→7→5→4的权重为:

                                                     0.37+0.28-0.66=-0.01

我们只要围着这个环兜圈子就能得到权重任意短的路径!注意，有向环的所有边的权重并不一定都必须是负的，只要权重之和是负的即可。

现在，假设从 s 到可达的某个顶点 v 的路径上的某个顶点在一个负权重环上。在这种情况下， 从 s 到 v 的最短路径是不可能存在的，因为可以用这个负权重环构造权重任意小的路径。换句话说， 在负权重环存在的情况下，最短路径问题是没有意义的。

所以我们对于带有负权重的边，但不会构成负权重的环的图我们可以适用Bellman-Ford 算法来计算最短路径。

Bellman-Ford 算法：在任意含有 V 个顶点的加权有向图中给定起点 s，从 s 无法到 达任何负权重环，以下算法能够解决其中的单点最短路径问题:将 distTo[s] 初始化为 0，其他 distTo[] 元素初始化为无穷大。以任意顺序放松有向图的所有边，重复 V 轮。

public class BellmanFordSP {private double[] distTo;private DirectedEdge[] edgeTo;private boolean[] onQ;private Queue<Integer> queue;private int cost;private Iterable<DirectedEdge> cycle;public BellmanFordSP(EdgeWeightedDigraph G, int s) {distTo = new double[G.V()];edgeTo = new DirectedEdge[G.V()];onQ = new boolean[G.V()];queue = new Queue<>();for (int i = 0; i < distTo.length; i++) {distTo[i] = Double.POSITIVE_INFINITY;}distTo[s] = 0.0;queue.enqueue(s);onQ[s] = true;while (!queue.isEmpty() && !hasNegativeCycle()) {int v = queue.dequeue();onQ[s] = false;relax(G, v);}}private void relax(EdgeWeightedDigraph G, int v) {for (DirectedEdge e : G.adj(v)) {int w = e.to();if (distTo[v] + e.weight() < distTo[w]) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if (!onQ[w]) {queue.enqueue(w);onQ[w] = true;}}if (cost++ % G.V() == 0) {findNegativeCycle();if (hasNegativeCycle())return;}}}private void findNegativeCycle() {int V = edgeTo.length;EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);for (int v = 0; v < V; v++)if (edgeTo[v] != null)spt.addEdge(edgeTo[v]);DirectedCycle finder = new DirectedCycle(spt);cycle = finder.cycle();}public boolean hasNegativeCycle() {return cycle != null;}public double distTo(int v) {if (hasNegativeCycle())throw new UnsupportedOperationException("Negative cost cycle exists");return distTo[v];}public boolean hasPathTo(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}public Iterable<DirectedEdge> pathTo(int v) {if (hasNegativeCycle())throw new UnsupportedOperationException("Negative cost cycle exists");if (!hasPathTo(v)) return null;Stack<DirectedEdge> path = new Stack<>();for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {path.push(e);}return path;}
}