Dijsktra算法介绍

Dijsktra算法是大牛Dijsktra于1956年提出，用来解决有向图单源最短路径问题。但不能解决负权的有向图，若要解决负权图则需要用 到Bellman-Ford算法。算法思想是，在dfs遍历图的过程中，每一次取出离源点的最近距离的点，将该点标记为已访问，松弛与该点相邻的节点。约 定：对有向图(n, m)，n为顶点数，m为边数，d[i]记录源点到节点i的距离，U为未访问的节点集合，V为已访问的节点集合。具体步骤如下：

1. 在U中寻找离源点最近的节点minNode，并将节点minNode标记为已访问（从集合U中移到集合V中）
   

   d[minNode]=mini∈Ud[i]
2. 松弛与minNode相邻的未访问节点，更新d数组
   
   
   d[i]i∈U=min{d[i] , d[minNode]+edge[minNode][i]}
   
   
   

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

代码实现

visit数组记录节点访问情况

void dijkstra(int n)  {  	int lowcost, minNode;  	int d[n], visit[n];		/*初始化d数组*/	for(int i = 0; i < n; i++) {  		d[i] = inf;  		visit[i] = 0;  	}  	d[0] = 0;  		/*重复操作n次*/	for(int count = 1; count <= n; count++) {  		lowcost = inf;             				//找出minNode		for(int i = 0; i < n-1; i++) {  			if(!visit[i] && d[i] < lowcost) {  				lowcost=d[i];  				minNode=i;  			}  		}				visit[minNode]=1;		   				//松弛操作		for(int i=0; i<n; i++) {  			if(!visit[i])  				d[i]=min(d[i],d[minNode]+edge[minNode][i]);  		} 	}}

复杂度分析

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

算法优化

我们可以观察到最外层的循坏没法再做优化，因为操作就是得重复n次才能访问到所有节点；只有针对里层的两个操作进行优化了：

• 找出minNode操作通过遍历来查找，缺点是效率太慢了，并且有一些节点是已访问的。因此，我们可以用小顶堆来维护d数组，堆顶对应就是minNode；取出堆顶，然后删除，如此堆中节点都是未访问的。
• 通过建立有向图的邻接表，松弛操作不需要遍历所有节点

堆的性质

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

• 节点i的父节点编号为i/2.

• 节点i的左右孩子节点编号分别为2∗i, 2∗i+1.

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

小顶堆优化Dijsktra算法

为了同时记录数组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(log n)。
   
3. DecreaseKey(vertex j, d + edge(i,j))是松弛操作，更新节点(vertex j, d + edge(i,j))，需要进行上浮，时间复杂度为O(log n)。

我们需要n次DeleteMin，m次DecreaseKey，优化版的算法时间复杂度为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);	}}

参考资料

[1] FRWMM, ALGORITHMS - DIJKSTRA WITH HEAPS.