Dijkstra's - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

【算法】最短路径查找—Dijkstra算法 Dijkstra(迪杰斯特拉)算法理解图论-轻松上手-Dijkstra（迪杰斯特拉）算法演示图论最短距离(Shortest Path)算法动画演示-Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德)

详解

【数据结构】图（最短路径Dijkstra算法）的JAVA代码实现

使用条件

所有的边权 >= 0
解释：Dijkstra算法可以很好地解决无负权图的最短路径问题，但如果出现了负权边，Dijkstra算法就会失效。例如下图中，若A为源点，首先会将点B和点C的dis值变为-1和1，接着由于点B的dist值最小，因此用点B去更新其未访问的邻接点(虽然并没有)。在这之后点B标记为已访问，于是将无法被从点C出发的边CB更新，因此最后dist(B)就是-1，但显然A到B的最短路径应该是A -> C -> B，即-4。

标准写法

public class Dijkstra<T> {

    // 源点的下标
    private int srcIndex;
    // 当前图
    private AdjacencyList<T> adjList;
    // 标记结点是否已经被访问
    private boolean[] visited;
    // 结点到源点的最短距离
    private int[] distTo;
    // 在已选集合中的结点的父结点
    private int[] parent;
    // 构造优先队列
    PriorityQueue<DijkstraNode> pq;

    public Dijkstra(int srcIndex, AdjacencyList<T> adjList) {
        this.srcIndex = srcIndex;
        this.adjList = adjList;
        this.visited = new boolean[adjList.size()];
        Arrays.fill(visited, false);
        this.distTo = new int[adjList.size()];
        // 初始化结点到源点的最短距离为无穷大
        Arrays.fill(distTo, Integer.MAX_VALUE);
        this.parent = new int[adjList.size()];
        // 初始化父结点都是-1
        Arrays.fill(parent, -1);
        pq = new PriorityQueue<>();
    }

    public void dijkstra() {
        if (adjList == null || adjList.getNodes().size() == 0) {
            return;
        }
        // 源点到源点自己的距离为0
        distTo[srcIndex] = 0;
        // 源点被访问
        visited[srcIndex] = true;
        // 源点的父结点就是自己
        parent[srcIndex] = srcIndex;
        // 从源点开始
        pq.add(new DijkstraNode(srcIndex, 0));
        while (!pq.isEmpty()) {
            // 获取当前优先队列中结点到源点距离最短的结点
            DijkstraNode node = pq.poll();
            if (node == null) {
                return;
            }
            // 结点被访问
            visited[node.getIndex()] = true;
            // 把当前与结点的相邻的结点都加入到优先队列
            ArrayList<AdjListNode> list = adjList.getNodes().get(node.getIndex()).getRoot();
            for (int i = 0; i < list.size(); i++) {
                // 排除已经访问过的结点
                // 更新结点到源点距离的最短距离 或 直接加入到优先队列
                if (!visited[list.get(i).getIndex()] && distTo[list.get(i).getIndex()] > list.get(i).getWeight()) {
                    DijkstraNode newNode = new DijkstraNode(list.get(i).getIndex(), list.get(i).getWeight());
                    pq.remove(newNode);
                    pq.add(newNode);
                    // 更新最短距离
                    distTo[list.get(i).getIndex()] = list.get(i).getWeight();
                    // 更新父结点
                    parent[list.get(i).getIndex()] = node.getIndex();
                }
            }
        }
    }

    public void print(int index) {
        if (index >= parent.length || parent[index] <= 0) {
            System.out.print("无最短路径！");
            return;
        }
        String result = " -> " + adjList.getNodes().get(index).getData().toString();
        while (parent[index] > 0) {
            result = " -> " + adjList.getNodes().get(parent[index]).getData() + result;
            index = parent[index];
        }
        result = adjList.getNodes().get(parent[index]).getData() + result;
        System.out.println(result);
    }
}

性能比较

PQ Implementation	insert	deleteMin	decreaseKey	Total
Array	1	V	1	1
AVL Tree	logV	logV	logV	O(ElogV)
d-way Heap	dlog(d)V	dlog(d)V	log(d)V	O(Elog(E/V)V)
Fibonacci Heap	1	logV	1	O(E + VlogV))

要点

维护一个集合，每次需要找到最小的距离，优先队列或AVL树搜索的时间复杂度是0(logn)
E条边，V个结点，时间复杂度是