最短路径Dijkstra算法

最短路径

最短路径的性质:

• 路径是有向的
• 权重不一定等价于距离,权重也可以指时间,花费或者其他
• 并不是所有顶点都是可达的
• 负权重会使得问题更复杂(Dijkstra算法不适用于这种情况)
• 最短路径一般都是简单的,这里算法会忽略构成环的零权重边,找到的最短路径都不会有环
• 最短路径不一定是唯一的
• 可能存在平行边和自环

最短路径树:给出起点s,计算结果是一颗最短路径树(Shortest Path Tree SPT),它包含了顶点s到所有可达顶点的最短路径

数据结构:

• 最短路径树中的边edgeTo[],edgeTo[v]表示s到v的最短路径中的最后一条边
• 到达起点的距离distTo[],distTo[v]表示s到v的已知最短路径长度

Dijkstra 算法

取自<算法>第四版-算法4.9

该算法类似Prim及时算法

    private double[] distTo;          // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo;    // edgeTo[v] = last edge on shortest s->v path
    private IndexMinPQ<Double> pq;	  // priority queue of vertices

	public DijkstraSP(EdgeWeightedDigraph G, int s) { 
		// 起点到各个顶点v的距离
        distTo = new double[G.V()];
        // 起点到各个顶点v最短路径中的最后一条边
        edgeTo = new DirectedEdge[G.V()];

        // 初始化起点s到各个顶点的距离为无穷最大值
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;

        // 从s到顶点v的权重为优先级
        pq = new IndexMinPQ<Double>(G.V());
        // s为起点
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) {
            // 取出顶点v
            int v = pq.delMin();
            // 遍历顶点v的各个边
            for (DirectedEdge e : G.adj(v)) {
                relax(e);
            }
        }
	}

    // 松弛一个顶点,判断起点s到顶点w的最短路径是否是s -> v -> w
    private void relax(DirectedEdge e) {
        // 边e为从顶点v到顶点w的有向边
        int v = e.from(), w = e.to();
        // 如果s到w的距离大于s到v + v到w的距离,则更新该距离,并将顶点w存入优先级队列
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            // 如果队列中已存在顶点w,则需要更新s到顶点w的距离,也即是更新权重
            if (pq.contains(w)) {
                pq.decreaseKey(w, distTo[w]);
            } else {
                pq.insert(w, distTo[w]);
            }               
        }
    }

    // 判断起点s到顶点v是否可达
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

	// 获取起点s到顶点v的最短路径
    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.from()]) {
            path.push(e);
        }
        return path;
    }

空间复杂度:V

时间复杂度:ElogV

给定两点s->t的最短路径:可使用Dijkstra算法并在优先队列中取到t之后终止搜索

任意顶点之间的最短路径:遍历各个顶点构造最短路径树,时间及空间复杂度均为EVlogV

加权无环图

加权无环图:加权有向图中不含有有向环的图

可在线性时间内解决加权无环图中的最短路径问题,比Dijkstra算法更快

• 可在线性时间内解决单点最短路径问题
• 能够处理负权重的边

待补充...

负权重的加权有向图

负权重的加权有向图:可能含有环也可能含有负权重的边的加权有向图

Bellman-Ford算法:时间复杂度EV,空间复杂度V

大佬自行研究去吧,我该curd去了