加权有向图----单点最短路径问题（Dijkstra算法）

SuperHeroes

发布于 2018-05-30 17:54:47

2.4K0

发布于 2018-05-30 17:54:47

文章被收录于专栏：云霄雨霁云霄雨霁

单点最短路径问题是求解从s到给定顶点v之间总权重最小的那条路径的问题。Dijkstra算法可以解决边的权重非负的最短路径问题。

Dijkstra算法无法判断含负权边的图的最短路径，但Bellman-Ford算法可以。

在实现Dijkstra算法之前，必须先了解边的松弛：

松弛边v->w意味着检查从s到w的最短路径是否是先从s到v，再从v到w。如果是，则根据这个情况更新数据。下面的代码实现了放松一个从给定顶点的指出的所有的边：

private void relax(EdgeWeightedDigraph G,int v) {
    for(DirectedEdge e: G.adj(v)) {
        int w = e.to();
        if(distTo[w]>distTo[v]+e.weight()) {
            distTo[w] = distTo[v]+e.weight();
            edgeTo[w] = e;
        }
    }
}

其中，distTo[]是一个顶点索引数组，保存的是G中路径的长度。对于从s可达的所有顶点w，distTov的值是从s到w的某条路径长度，对于s不可达的所有顶点w，该值为无穷大。

最短路径的API:

public class SP SP(EdgeWeightedDigraph G,int s) 构造函数 double distTo(int v) 顶点s到v的距离，不存在则为无穷大 boolean hasPathTo(int v) 是否存在从顶点s到v的距离 Iterable<DirectedEdge> pathTo(int v) 顶点s到v的路径，不存在则为null

数据结构：

最短路径树中的边：使用一个由顶点索引的父链接数组edgeTo[],其中edgeTov的值为树中连接v和它父节点的边（也是从s到v的最短路径上的最后一条边），通过该数组可以逆推得到最短路径。
到达起点的距离：用一个由顶点索引的数组distTo[]，其中distTov为从s到v的已知最短路径的长度。
顶点优先权队列：保存需要被放松的顶点并确认下一个被放松的顶点。

查询方法（API方法实现）：

public double distTo(int v) {  return distTo[v];  }

public boolean hasPathTo(int v) {  return distTo[v]<Double.POSITIVE_INFINITY;  }

public Iterable<DirectedEdge> pathTo(int v){
	if(!hasPathTo(v))  return null;
	Stack<DirectedEdge>  path = new Stack<DirectedEdge>();
	for(DirectedEdge e = edgeTo[v];e!=null;e = edgeTo[e.form()])
	path.push(e);
	return path;
}

Dijkstra算法能够解决边权重非负的加权有向图的单起点最短路径问题。

Dijkstra算法的实现：

public class DijkstraSP {
    private DirectedEdge[] edgeTo;  //edgeTo用来逆推最短路径
    private double[] distTo;    //distTo[]用来计算最短路径
    private IndexMinPQ<Double> pq;    //用来保存需要被放松的顶点并确认下一个被放松的顶点
	
    public DijkstraSP(EdgeWeightedDigraph G,int s) {
        //初始化
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new IndexMinPQ<Double>(G.V());
        for(int v = 0;v<G.V();v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        //从起始顶点s开始
        pq.insert(s,0.0);    //调用优先权队列的insert()方法
        while(!pq.isEmpty())
            relax(G,pq.delMin());
    }
    private void relax(EdgeWeightedDigraph G,int v) {
        for(DirectedEdge e: G.adj(v)) {
            int w = e.to();
            if(distTo[w]>distTo[v]+e.weight()) {
                distTo[w] = distTo[v]+e.weight();
                edgeTo[w] = e;
                if(pq.contains(w))	pq.change(w, distTo[w]);
                else 	pq.insert(w, distTo[w]);
            }
        }
    }
    //distTo[]、edgeTo[]、pathTo[]方法见上文
}

简单的在上述算法外添加一层循环即可实现任意顶点对之间的最短路径（权重非负）。

下一篇：无环情况下的最短路径算法

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017.12.21，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法