最短路径¶

BFS¶

可以找到边数最少的路径，不考虑权值。

Dijkstra¶

Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解非负权图上单源最短路径的算法。

松弛操作使用 IndexMinPQ；也可以用普通的优先队列 + vis 数组，新值直接插入队列即可，靠 vis 数组保证每个结点只访问一次。

public class DijkstraSP {
    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) {
        for (DirectedEdge e : G.edges()) {
            if (e.weight() < 0)
                throw new IllegalArgumentException("edge " + e + " has negative weight");
        }

        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];

        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // relax vertices in order of distance from s
        pq = new IndexMinPQ<Double>(G.V());
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) {
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }

    // relax edge e and update pq if changed
    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else                pq.insert(w, distTo[w]);
        }
    }

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

时间复杂度：\(O(E \log V)\)
空间复杂度：\(O(V)\)

Bellman-Ford¶

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

从起点开始，松弛一个顶点后，继续松弛它周围的顶点，直到所有点都不能再松弛。如果图中有负环的话，每绕一圈总路径长度都会变小，就无限循环了。如果图的顶点数为 V，路径长度最大就 V-1（所有点都经过一次），使用 cnt[v] 记录从起点到 v 经过的边数，如果大于 V-1 说明有负环。

public class BellmanFordSP {
    private double[] distTo;       // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
    private boolean[] onQueue;     // onQueue[v] = is v currently on the queue?
    private Queue<Integer> queue;  // queue of vertices to relax
    private int[] cnt;             // cnt[v] = number of edges from the source vertex to v
    private boolean hasNegativeCycle;

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo  = new double[G.V()];
        edgeTo  = new DirectedEdge[G.V()];
        onQueue = new boolean[G.V()];
        cnt     = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // Bellman-Ford algorithm
        queue = new Queue<Integer>();
        queue.enqueue(s);
        onQueue[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle) {
            int v = queue.dequeue();
            onQueue[v] = false;
            relax(G, v);
        }
    }

    // relax vertex v and put other endpoints on queue if changed
    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;
                cnt[w] = cnt[v] + 1;
                if (cnt[w] >= G.V()) {
                    hasNegativeCycle = true;
                    return;
                }
                if (!onQueue[w]) {
                    queue.enqueue(w);
                    onQueue[w] = true;
                }
            }
        }
    }

    public Iterable<DirectedEdge> pathTo(int v) {
        if (hasNegativeCycle)
            throw new UnsupportedOperationException("Negative cost cycle exists");
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }
}

通常情况下，每个边仅被松弛一次，时间复杂度：\(O(V+E)\)
最坏时间复杂度：\(O(VE)\)
空间复杂度：\(O(V)\)

相关文章
算法考试
最小生成树