Dijkstra算法

2017-12-20 22:22:55

Dijkstra算法是用来计算单源最短路径（Single-Source Shortest Paths，SSSP）的一种常用算法，该算法要求所有的权值为非负值。即从单个源点出发，到所有结点的最短路。该算法同时适用于有向图和无向图。

输入：图的邻接矩阵或者是邻接表以及源点。

输出：源点到其他各个点的最短路径。

算法实现过程：Dijkstra算法维护了一组结点集合S，从源结点s到该集合中的每个点的最短路径已经被找到。算法重复从结点集V-S中选择最短路径估计最小的结点u，将u添加到S中，同时对u的所有边进行松弛操作。

清除所有点的标号

设d[s]=0,其他d[i]=INF

循环n次{

　　在所有未标记结点中，选出d值最小的结点x

　　给结点x标记

　　对于从x出发的所有边（x，y），更新d[y] = min{d[y], d[x] + w(x,y)}

}

算法时间复杂度：

 n 2 {displaystyle n^{2}} 的稀疏图来说，我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为 O ( ( m + n ) l o g n ) {displaystyle O((m+n)logn)} ，斐波纳契堆能稍微提高一些性能，让算法运行时间达到 O ( m + n l o g n ) {displaystyle O(m+nlogn)} 。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。

Java实现：

edges动态数组中保存的是边的详细信息，G中保存的只是边的编号。有了编号后再去edges中获得边的详细信息。其实就是邻接表的一种实现，这样在“遍历从x出发的所有边（x，y）更新d[y]”就可以写成“for（int i=0；i<G[u].size();i++） 执行每条边的松弛操作”。由于采用了邻接表的方式，所以使用聚合分析的时候松弛操作的执行次数是m次。这里使用的二叉堆的优先队列，每次更新都要花费logn，因此这里的消耗为mlogn。另外获取当前队首元素的时候也会消耗logn的维护时间，该项操作总共执行了n次，这里的消耗为nlogn。综上，总的时间消耗为（m+n）logn。

package dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Dijkstra {
    int n;
    int m;
    final Integer maxn = 20;
    final int INF = 1 << 20;
    // 存放各个边的信息
    ArrayList<Edge> edges=new ArrayList<>();
    // 存放结点i的邻接边的存放下标
    ArrayList<Integer>[] G = new ArrayList[maxn];
    // 标记是否访问过
    boolean visited[] = new boolean[maxn];
    // s到各个点的距离
    int d[] = new int[maxn];
    // 最短路径的上一个结点
    int p[] = new int[maxn];

    void init(int n) {
        this.n = n;
        for (int i = 0; i < n; i++) {
            G[i] = new ArrayList<>();
        }
        edges.clear();
    }

    void addEdge(int from, int to, int dist) {
        edges.add(new Edge(from, to, dist));
        m = edges.size();
        G[from].add(m - 1);
    }

    void dijkstra(int s) {
        PriorityQueue<QueueNode> Q = new PriorityQueue<>(new Comparator<QueueNode>() {
            @Override
            public int compare(QueueNode o1, QueueNode o2) {
                return o1.d - o2.d;
            }
        });
        Arrays.fill(d, INF);
        d[s] = 0;
        Arrays.fill(visited, false);
        Arrays.fill(p, -1);
        Q.add(new QueueNode(0, s));
        while (!Q.isEmpty()) {
            QueueNode x = Q.poll();
            int u = x.u;
            if(visited[u]) continue;
            visited[u]=true;
            for (int i = 0; i < G[u].size(); i++) {
                Edge e = edges.get(G[u].get(i));
                if (d[e.to] > d[u] + e.dist) {
                    d[e.to] = d[u] + e.dist;
                    p[e.to]=u;
                    Q.add(new QueueNode(d[e.to], e.to));
                }
            }
        }
    }

    void printPath(int e) {
        if (p[e] != -1) {
            printPath(p[e]);
        }
        System.out.print(e+" ");
    }

    public static void main(String[] args) {
        Dijkstra dj=new Dijkstra();
        dj.init(5);
        dj.addEdge(0,1,10);
        dj.addEdge(0,3,30);
        dj.addEdge(0,4,100);
        dj.addEdge(1,2,50);
        dj.addEdge(2,4,10);
        dj.addEdge(3,2,20);
        dj.addEdge(3,4,60);
        dj.dijkstra(0);
        dj.printPath(2);
    }

}

class Edge {
    int from, to, dist;

    Edge(int u, int v, int d) {
        this.from = u;
        this.to = v;
        this.dist = d;
    }
}

class QueueNode {
    int d, u;

    QueueNode(int d, int u) {
        this.d = d;
        this.u = u;
    }
}