1. 介绍

Dijsktra算法是大牛Dijsktra于1956年提出，用来解决有向图单源最短路径问题；但是不能解决负权的有向图，若要解决负权图则需要用到Bellman-Ford算法。Dijsktra算法思想：在DFS遍历图的过程中，每一次取出离源点的最近距离的点，将该点标记为已访问，松弛与该点相邻的结点。

有向图记为G=(n,m)，其中，n为顶点数，m为边数；且e[a,b]表示从结点a到结点b的边。d[i]记录源点到结点i的距离，U为未访问的结点集合，V为已访问的结点集合。Dijsktra算法具体步骤如下：

• 从集合U中寻找离源点最近的结点u，并将结点u标记为已访问（从集合U中移到集合V中）

• 松弛与结点uu相邻的未访问结点，更新d数组                                                                                                                                                                                                                                                                                                                  

• 重复上述操作n次，即访问了所有结点，集合U为空

Dijsktra算法的Java实现

/**

 * Dijkstra's Algorithm for finding the shortest path

 *

 * @param adjMatrix adjacency matrix representation of the graph

 * @param source    the source vertex

 * @param dest      the destination vertex

 * @return the cost for the shortest path

 */

public static int dijkstra(int[][] adjMatrix, int source, int dest) {

  int numVertex = adjMatrix.length, minVertex = source;

  // `d` marks the cost for the shortest path, `visit` marks whether has been visited or not

  int[] d = new int[numVertex], visit = new int[numVertex];

  Arrays.fill(d, Integer.MAX_VALUE);

  d[source] = 0;

  for (int cnt = 1; cnt <= numVertex; cnt++) {

    int lowCost = Integer.MAX_VALUE;

    // find the min-vertex which is the nearest among the unvisited vertices

    for (int i = 0; i < numVertex; i++) {

      if (visit[i] == 0 && d[i] < lowCost) {

        lowCost = d[i];

        minVertex = i;

      }

    }

    visit[minVertex] = 1;

    if (minVertex == dest) return d[dest];

    // relax the minVertex's adjacency vertices

    for (int i = 0; i < numVertex; i++) {

      if (visit[i] == 0 && adjMatrix[minVertex][i] != Integer.MAX_VALUE) {

        d[i] = Math.min(d[i], d[minVertex] + adjMatrix[minVertex][i]);

      }

    }

  }

  return d[dest];

}

复杂度分析

• 时间复杂度：重复操作（即最外层for循环）n次，找出minNode操作、松弛操作需遍历所有结点，因此复杂度为O(n2).
• 空间复杂度：开辟两个长度为n的数组d与visit，因此复杂度为T(n).

2. 优化

从上述Java实现中，我们发现：（里层for循环）寻找距离源点最近的未访问结点u，通过遍历整个数组来实现的，缺点是重复访问已经访问过的结点，浪费了时间。首先，我们来看看堆的性质。

堆

堆是一种完全二叉树(complete binary tree)；若其高度为h，则1~h-1层都是满的。如果从左至右从上至下从1开始给结点编号，堆满足：

• 结点ii的父结点编号为i/2
• 结点ii的左右孩子结点编号分别为2∗i, 2∗i+1.

如果结点ii的关键值小于父结点的关键值，则需要进行上浮操作（move up）；如果结点ii的关键值大于父结点的，则需要下沉操作（move down）。为了保持堆的整体有序性，通常下沉操作从根结点开始。

小顶堆优化Dijsktra算法

我们可以用小顶堆来代替d数组，堆顶对应于结点u；取出堆顶，然后删除，如此堆中结点都是未访问的。同时为了记录数组d[i]中索引i值，我们让每个堆结点挂两个值——顶点、源点到该顶点的距离。算法伪代码如下：

Insert(vertex 0, 0)  // 插入源点

FOR i from 1 to n-1:  // 初始化堆

    Insert(vertex i, infinity)



FOR k from 1 to n:

    (i, d) := DeleteMin()

    FOR all edges ij:

        IF d + edge(i,j) < j’s key

            DecreaseKey(vertex j, d + edge(i,j))

1. Insert(vertex i, d)指在堆中插入堆结点(i, d)。
2. DeleteMin()指取出堆顶并删除，时间复杂度为O(logn)O(log⁡n)。
3. DecreaseKey(vertex j, d + edge(i,j))是松弛操作，更新结点(vertex j, d + edge(i,j))，需要进行上浮，时间复杂度为O(logn)O(log⁡n)。

我们需要n次DeleteMin，m次DecreaseKey，优化版的算法时间复杂度为O((n+m)logn)O((n+m)log⁡n).

代码实现

邻接表
每一个邻接表的表项包含两个部分：头结点、表结点，整个邻接表可以用一个头结点数组表示。下面给出其Java实现

public class AdjList {

    private int V = 0;

    private HNode[] adjList =null; //邻接表

    

    /*表结点*/

     class ArcNode {

        int adjvex, weight;

        ArcNode next;

        

        public ArcNode(int adjvex, int weight) {

            this.adjvex = adjvex;

            this.weight = weight;

            next = null;

        }

    }

    

     /*头结点*/

    class HNode {

        int vertex;

        ArcNode firstArc;

        

        public HNode(int vertex) {

            this.vertex = vertex;

            firstArc = null;

        }

    }

    

    /*构造函数*/

    public AdjList(int V) {

        this.V = V;

        adjList = new HNode[V+1];

        for(int i = 1; i <= V; i++) {

            adjList[i] = new HNode(i);

        }

    }

    

    /*添加边*/

    public void addEdge(int start, int end, int weight) {

        ArcNode arc = new ArcNode(end, weight);

        ArcNode temp = adjList[start].firstArc;

        adjList[start].firstArc = arc;

        arc.next = temp;

    }

    

    public int getV() {

        return V;

    }



    public HNode[] getAdjList() {

        return adjList;

    }



}

小顶堆

public class Heap {

    public int size = 0 ;

    public Node[] h = null;     //堆结点

    

    /*记录Node中vertex对应堆的位置*/

    public int[] index = null;  

    

    /*堆结点：

     * 存储结点+源点到该结点的距离

     */

    public class Node {

        int vertex, weight;

        

        public Node(int vertex, int weight) {

            this.vertex = vertex;

            this.weight = weight;

        }

    }

    

    public Heap(int maximum) {

        h = new Node[maximum];

        index = new int[maximum];

    }

    

    /*上浮*/

    public void moveUp(int pos) {

        Node temp = h[pos];

        for (; pos > 1 && h[pos/2].weight > temp.weight; pos/=2) {

            h[pos] = h[pos/2];

            index[h[pos].vertex] = pos;  //更新位置

        }

        h[pos] = temp;

        index[h[pos].vertex] = pos;

    }

    

    /*下沉*/

    public void moveDown( ) {

        Node root = h[1];

        int pos = 1, child = 1;

        for(; pos <= size; pos = child) {

            child = 2*pos;

            if(child < size && h[child+1].weight < h[child].weight)

                child++;

            if(h[child].weight < root.weight) {

                h[pos] = h[child];

                index[h[pos].vertex] = pos;

            } else {

                break;

            }

        }

        h[pos] = root;

        index[h[pos].vertex] = pos;

    }

    

    /*插入操作*/

    public void insert(int v, int w) {

        h[++size] = new Node(v, w);

        moveUp(size);

    }

    

    /*删除堆顶元素*/

    public Node deleteMin( ) {

        Node result = h[1];

        h[1] = h[size--];

        moveDown();

        return result;

    }



}

优化算法

public class ShortestPath {

    private static final int inf = 0xffffff;

    

    public static void dijkstra(AdjList al) {

        int V = al.getV();

        Heap heap = new Heap(V+1);

        heap.insert(1, 0);

        for(int i = 2; i <= V; i++) {

            heap.insert(i, inf);

        }

        

        for(int k =1; k <= V; k++) {

            Heap.Node min = heap.deleteMin();

            if(min.vertex == V) {

                System.out.println(min.weight);

                break;

            }

            AdjList.ArcNode arc = al.getAdjList()[min.vertex].firstArc;

            while(arc != null) {

                if((min.weight+ arc.weight) < heap.h[heap.index[arc.adjvex]].weight) {

                    heap.h[heap.index[arc.adjvex]].weight = min.weight+ arc.weight;

                    heap.moveUp(heap.index[arc.adjvex]);

                }

                arc = arc.next;

            }

        }

    }

    

    /*main方法用于测试*/

    public static void main(String[] args) {

        AdjList al = new AdjList(5);

        al.addEdge(1, 2, 20);

        al.addEdge(2, 3, 30);

        al.addEdge(3, 4, 20);

        al.addEdge(4, 5, 20);

        al.addEdge(1, 5, 100);

        dijkstra(al);

    }

}

3. 参考资料

[1] FRWMM, ALGORITHMS - DIJKSTRA WITH HEAPS.

如需转载，请注明作者及出处.

作者：Treant

出处：http://www.cnblogs.com/en-heng/