Dijkstra算法及堆优化

简介

Dijkstra（迪杰斯特拉）算法主要用于求解非负权图中单源最短路径问题，即求一个顶点到图中其他顶点之间的最短路径。对于负权图的单源路径问题，一般采用Bellman–Ford（贝尔曼-福特）算法进行求解。对于非负权图，Dijkstra算法是目前已知的最快的单源路径算法，该算法常用于路由算法或者作为其他图算法的子模块。

Dijkstra算法是广度优先搜索BFS算法的扩展，当图中权值均为1即退化为无向图时，可直接采用BFS算法求解。对图和广度优先搜索算法不了解的，可以参考我之前的博客常用数据结构与算法之图。因此，Dijkstra算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法一般采用邻接矩阵的形式存储非负权图，即用一个二维数组edges[i, j]来表示该图。当两个顶点之间有边直接相连，则edges[i, j]为边上的权值；如果两个顶点之间没有边直接相连，edges[i, j]为正无穷大，C#中用int.MaxValue表示。

Dijkstra算法需要设置两个数组：一个数组用来保存已求得最短路径的顶点和对应顶点的最短路径，用vs[]表示。下标表示已求得最短路径的顶点序号，对应的值表示对应顶点的最短路径。另一个数组用来保存起始顶点到其他顶点当前的最短路径，用dist[]表示。

算法步骤

假设从顶点0开始出发，求到其他顶点的最短路径。Dijkstra算法的步骤为：

1、初始化：vs[0]=0，表示顶点1已求出最短路径，因为顶点1的最短路径就是0。除vs[0] = 1之外，其他vs数组元素初始化默认值全为0，表示没有已求出最短路径的其他顶点。之后每求出一个最短路径顶点，就把它加入到vs数组中。dist数组初始化为dist[i] = edges[0, i]，i = 1，2，3，……n-1，n表示图中的顶点数|V|。

2、找出当前dist数组中的最短路径dist[j]，即满足dist[j] = Min( dist[i], 0<i<n )。则vj就是当前求得的从v0出发到vj的一条最短路径的终点，v0-vj的最短路径长度为dist[j]。将vj顶点加入vs数组中，vs[j] = dist[j]。

3、以刚求得最短路径的顶点为中间顶点，更新dist数组从v0到顶点vk的最短路径长度，这叫做松弛。无法直接求顶点0到目标顶点的最短路径dist[k]，就用刚求得最短路径的顶点为中间顶点vj，通过对vj-vk这条出边来松弛v0到顶点vk的最短路径。

然后，继续寻找中间顶点vj到目标顶点vk的最短路径，如果dist[j] + edges[j, k] < dist[k]时，就令dist[k] = dist[j] + edges[j, k]，从而达到更新dist数组的目的。因为，dist[j]是当前dist数组里面最短的一条路径，不可能还经过第三个中间顶点h。由于边权值为正，并且v0-vh之间的路径必定大于v0-vj。这就是采用Dijkstra算法中必须保证边权值为非负的原因，如果存在带负权值的边以上就不成立了。

4、按顺序重复操作2和3共n-1次，直到所有顶点都包含在vs数组中，即v0到其他各顶点的最短路径已全部找到，算法结束。

示例

以上图为例，以顶点1为起始顶点，求顶点1到其他顶点的最短路径。下面是vs数组和dist数组的更新过程：

由于图中的元素序号从1开始，而数组下标索引从0开始。因此，数组中的下标索引加1后才表示对应的顶点序号，对应索引的值表示该顶点的最短距离。从这个过程看出，Dijkstra算法实际上采用了贪心策略（每一步都是最优的），每次从当前dist数组中找出一条最短的路径，然后基于这条最短路径，更新到其他顶点的最短路径长度。下面是用C#实现的Dijkstra算法：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151


using System;
using System.Collections.Generic;

namespace Dijkstra
{
    class Graph
    {
        // 该图对应的邻接矩阵
        public int[,] edges;
        // 顶点数
        int num;

        // 带权图的构造函数，所有权值默认为正无穷大
        public Graph(int num)
        {
            this.num = num;
            edges = new int[num, num];
            for (int i = 0; i < num; i++)
            {
                for (int j = 0; j < num; j++)
                {
                    edges[i, j] = int.MaxValue;
                }
            }
        }

        // 添加边
        public void AddEdge(int v1, int v2, int weight)
        {
            // 因为图的元素从1开始，数组下标从0开始，所以添加时需要减1
            edges[v1 - 1, v2 - 1] = weight;
        }

        // 输出图的邻接矩阵
        public void PrintGraph()
        {
            Console.WriteLine("该图的邻接矩阵为：");
            for (int i = 0; i < num; i++)
            {
                for (int j = 0; j < num; j++)
                {
                    if (edges[i, j] == int.MaxValue)
                    {
                        Console.Write("∞ ");
                    }
                    else
                    {
                        Console.Write(edges[i, j]+" ");
                    }
                }
                Console.WriteLine();
            }
        }

        // Dijkstra算法的具体实现
        // 因为图的元素从1开始，数组下标从0开始，所以算法中的顶点v都需要减1
        public void Dijkstra(int v)
        {
            // 已找到最短路径的顶点数组
            int[] vs = new int[num];
            
            // 顶点v到其他顶点的最短路径数组
            int[] dist = new int[num];
            for (int i = 0; i < num; i++)
            {
                if (i != v-1) // 顶点v到其本身的最短路径长度为0，不需要赋值
                {
                    // 初始化dist数组
                    dist[i] = edges[v-1, i];
                }
            }

            // 需要num-1趟才能把剩下的顶点找到
            for (int i= 1; i < num; i++)
            {
                int minv = 0; // 当前最短路径顶点，默认为0
                int min = int.MaxValue; // 当前最短路径长度，默认为正无穷大

                // 找出具体的当前最短路径长度
                for (int j = 0; j < num; j++)
                {
                    // vs[j] == 0 已找到最短路径的顶点vs[j]为其最短路径长度，
                    // 不与更新后的其他顶点比较最短路径长度。
                    // j != v-1 表示顶点v本身不参与最短路径长度的比较
                    if (vs[j] == 0 && dist[j] < min && j != v-1) 
                    {
                        min = dist[j];
                        minv = j;
                    }
                }

                // 把找到最短路径的顶点和它的最短路径长度加入vs数组
                vs[minv] = min; // 2,1;

                // 在刚才找到最短路径的顶点的基础上，更新dist数组
                for (int k = 0; k < num; k++)
                {
                    // dist[minv]+edges[minv, k]>0 是因为C#中的正无穷大是int内存空间里最大的数，
                    // 如果是正无穷大再加一个正数，就会超出int内存空间变成负数。
                    // dist[minv]+edges[minv, k] < dist[k] 是看松弛后是否比直接到达更近，
                    // 如果是，就更新到该顶点的最短路径长度。
                    if (dist[minv] + edges[minv, k] > 0 && dist[minv] + edges[minv, k] < dist[k])
                    {
                        dist[k] = dist[minv] + edges[minv, k];
                    }
                }
            }

            // 输出vs中的顶点和到该顶点的最短路径长度
            Console.WriteLine("顶点{0}到其他各顶点的最短路径长度为：", v);
            for (int i = 0; i < num; i++)
            {
                Console.Write("{0}:{1}, ", i+1, vs[i]);
            }
        }
    }

    class Client
    {
        public static void Main(string[] args)
        {
            Graph graph = new Graph(5);

            graph.AddEdge(1, 2, 10);
            graph.AddEdge(1, 5, 5);
            graph.AddEdge(2, 3, 1);
            graph.AddEdge(2, 5, 2);
            graph.AddEdge(3, 4, 4);
            graph.AddEdge(4, 1, 7);
            graph.AddEdge(4, 3, 6);
            graph.AddEdge(5, 2, 3);
            graph.AddEdge(5, 3, 9);
            graph.AddEdge(5, 4, 2);

            graph.PrintGraph();
            
            // 其他顶点也可以
            graph.Dijkstra(1);
        }
    }
}

// 输出结果：
// 该图的邻接矩阵为：
// ∞ 10 ∞ ∞ 5 
// ∞ ∞ 1 ∞ 2 
// ∞ ∞ ∞ 4 ∞ 
// 7 ∞ 6 ∞ ∞ 
// ∞ 3 9 2 ∞ 
// 顶点2到其他各顶点的最短路径长度为：
// 1:0, 2:8, 3:9, 4:7, 5:5,

Dijkstra算法的主要部分是一个双重for循环，外层循环内有两个并列的单层循环。任取一个内层循环的基本操作，其执行次数为双重for循环执行的次数。如果图是用邻接矩阵表示，每个循环的次数近似为顶点数，则时间复杂度为O(|V|^2）。但如果图是用邻接表表示，虽然更新dist数组的时间减少了，但是在dist数组中找当前路径的时间复杂度仍为O(|V|)。由于是双重for循环，所以Dijkstra算法的时间复杂度还是O(|V|^2)。

堆优化

上面的Dijkstra算法是没有经过堆优化的版本，时间复杂度为O(|V|^2)，效率比较低。因此，我们需要对Dijkstra算法进行堆优化，是其时间复杂度降为O((|E|+|V|)log|V|)，从而提高Dijkstra算法的效率。堆优化的主要思想是用一个优先级队列来存储当前各顶点的最短路径，由于堆的性质，每次出队的元素都是当前最短路径中的最小元素。此外，通过邻接表来存储非负权图，可以使每次更新最短路径时只需要访问所有的边一次。由于图的邻接表是不唯一的，因此我们先确定上面示例图中对应的邻接表存储结构，如下图所示。

由于C++和JAVA都有对应的优先级队列类型，而C#类库中没有实现好的优先级队列，因此我们自己先用堆实现一个优先级队列。优先级队列不同于普通队列，它不是严格遵循普通队列先进先出FIFO的特点，而是每次只取队列中优先级最高的元素。因此，优先级队列可以看做是一个元素带优先级的队列。优先级队列元素像普通队列元素一样依次进队，只是出队时按优先级的高低依次出队。如果遇到优先级相同的元素，就按进队的先后顺序依次出队。

优先级队列可以用数组和堆来实现，但数组删除和排序的时间复杂度较高，而堆插入和删除最大值的时间复杂度为O(nlogn)，因此通常使用堆来实现优先级队列。在常用数据结构与算法之树与二叉树中讲到，堆是一种特殊的完全二叉树，堆中某个结点的值必须小于等于（或大于等于）其父结点的值，因此根节点的值最大或最小。

每当根节点移除后，剩下的结点重新调整为一个新的堆，直到所有结点全部输出，这天然符合优先级队列元素的输出顺序。与一般的二叉树采用链式存储不同，堆采用的是顺序存储，堆中所有的元素均存放在数组中。下面是用小根堆实现的一个优先级队列：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150


using System;

namespace PriorityQueue
{
    class PriorityQueue<T> where T : IComparable<T>, IEquatable<T>
    {
        // 声明一个存放小根堆的数组
        private T[] minHeap;
        // 数组中的游标
        private int index;

        public int Index { get => index; set => index = value; }

        public PriorityQueue(int num)
        {
            minHeap = new T[num];
        }

        // 判空函数
        public bool isEmpty()
        {
            if (Index == 0)
            {
                return true;
            }
            return false;
        }

        // 交换数组中对应位置的元素
        private void Swap(int i, int j)
        {
            T temp = minHeap[i];
            minHeap[i] = minHeap[j];
            minHeap[j] = temp;
        }

        // 元素进队，即往小根堆中插入元素
        public void Enqueue(T a)
        {
            if (Index == minHeap.Length)
            {
                throw new IndexOutOfRangeException();
            }
            // 元素先直接插入小根堆的末尾
            minHeap[Index] = a;
            Index++;
            // 再自底向上调整小根堆
            SiftUp();
        }

        // 元素出队，每次出队时选择优先级最高的元素。
        // 即返回小根堆的根结点，然后将堆中最后一个元素移动到根结点，再自顶向下调整小根堆
        public T Dequeue()
        {
            if (Index == 0)
            {
                throw new IndexOutOfRangeException();
            }
            T result = minHeap[0];
            minHeap[0] = minHeap[Index - 1];
            Index--;
            SiftDown();
            return result;
        }

        // 修改对应元素
        public void Modify(T a)
        {
            for (int i = 0; i < index; i++)
            {
                if (minHeap[i].Equals(a))
                {
                    minHeap[i] = a;
                    SiftDown();
                    return;
                }
            }
        }

        // 只返回队头元素，不删除该元素
        public T Peek()
        {
            if (Index == 0)
            {
                throw new IndexOutOfRangeException();
            }
            return minHeap[0];
        }

        // 自底向上调整小根堆
        private void SiftUp()
        {
            int i = Index - 1;
            // 由于堆是一棵完全二叉树的顺序存储，以第一个元素从0开始为基准，则第i个结点的左孩子为2i+1，右孩子为2i+2。
            // 当两个整数相除时，/符号得到的结果是一个整数，小数部分直接舍去。
            while (i != 0 && minHeap[i].CompareTo(minHeap[(i - 1) / 2]) < 0)
            {
                Swap(i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }

        // 自顶向下调整小根堆
        private void SiftDown()
        {
            int i = 0;
            while (2 * i + 1 < Index)
            {
                int j = 2 * i + 1;
                if (j + 1 < Index && minHeap[j].CompareTo(minHeap[j + 1]) > 0)
                {
                    j++;
                }
                if (minHeap[i].CompareTo(minHeap[j]) < 0)
                {
                    break;
                }
                Swap(i, j);
                i = j;
            }
        }

        // 按从上到下，从左到右依次输出小根堆中的元素
        public void Print()
        {
            for (int i = 0; i < Index; i++)
            {
                Console.WriteLine(minHeap[i]);
            }
        }
    }

    class Client
    {
        public static void Main(string[] args)
        {
            PriorityQueue<int> pq = new PriorityQueue<int>(5);

            pq.Enqueue(2);
            pq.Enqueue(3);
            pq.Enqueue(4);
            pq.Enqueue(1);
            pq.Enqueue(5);

            pq.Print();
        }
    }
}

// 输出结果：12435

在Dijkstra算法的堆优化中，带权图采用邻接表的存储方式，这样就可以减少边权值的比较次数。邻接表存储是顺序存储和链式存储的结合，这里我们采用链表数组来表示邻接表的存储结构。数组采用的是顺序存储的方式，用来存放顶点表，每一个数组元素就是一个顶点。而链表采用的是链式存储的方式，用来存放每个顶点对应的边表，链表中的元素就表示一个边表结点。Dijkstra算法的堆优化代码如下：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199


using System;
using PriorityQueue;
using System.Diagnostics.CodeAnalysis;

namespace DijkstraHeap
{
    // 边表结点
    class Node: IComparable<Node>, IEquatable<Node>
    {
        // 边表中的顶点
        private int vertex;
        // 顶点表中的顶点到边表顶点对应边上的权值
        private int weight;
        // 边表结点的引用域
        private Node next;

        public int Vertex { get => vertex; set => vertex = value; }
        public int Weight { get => weight; set => weight = value; }
        public Node Next { get => next; set => next = value; }

        public Node(int vertex, int weight)
        {
            this.vertex = vertex;
            this.weight = weight;
        }

        public Node() { }
      
        // 实现泛型比较接口IComparable<Node>
        public int CompareTo(Node other)
        {
            if (this.weight > other.weight)
            {
                return 1;
            }
            if (this.weight < other.weight)
            {
                return -1;
            }
            return 0;
        }
      
        // 实现泛型相等接口IEquatable<Node>
        public bool Equals(Node other)
        {
            if (this.vertex == other.vertex)
            {
                return true;
            }
            return false;
        }
    }

    // 边表
    class EdgeList
    {
        private Node head;

        public Node Head { get => head; set => head = value; }

        public EdgeList()
        {
            head = null;
        }
      
        // 往链表中添加元素
        public void Append(int vertex, int weight)
        {
            Node q = new Node(vertex, weight);
            Node p;

            if (head == null)
            {
                head = q;
            }
            else
            {
                p = head;
                while (p.Next != null)
                {
                    p = p.Next;
                }
                p.Next = q;
            }
        }
      
        // 链表判空
        public bool isEmpty()
        {
            if (head == null)
            {
                return true;
            }
            return false;
        }
    }
  
    // 定义图
    class Graph
    {
        public EdgeList[] graph;
        // 图的顶点数
        int num;

        public Graph(int num)
        {
            this.num = num;
            graph = new EdgeList[num];
            for (int i = 0; i < num; i++)
            {
                graph[i] = new EdgeList();
            }
        }

        public void AddEdge(int v1, int v2, int w)
        {
            // 因为图的元素从1开始，数组下标从0开始，所以算法中的顶点v都需要减1
            graph[v1 - 1].Append(v2 - 1, w);
        }

        public void Dijkstra(int i)
        {
            // 已找到最短路径的顶点数组
            int[] vs = new int[num];
            // 存放顶点v到其他顶点的最短路径
            int[] dists = new int[num];
            // 优先级队列
            PriorityQueue<Node> pq = new PriorityQueue<Node>(num);
            int v;
            int dist;

            Node p = graph[i - 1].Head;
            while (p != null)
            {
                pq.Enqueue(p);
                dists[p.Vertex] = p.Weight;
                p = p.Next;
            }

            while (num > 1)
            {
                Node min = pq.Dequeue();
                v = min.Vertex;
                dist = min.Weight;
                vs[v] = dist;

                Node q = graph[v].Head;
                Node temp = new Node();
                while (q != null)
                {
                    if (dists[q.Vertex] == 0)
                    {
                        pq.Enqueue(q);
                    }
                    if (dist + q.Weight < dists[q.Vertex])
                    {
                        temp.Vertex = q.Vertex;
                        temp.Weight = dist + q.Weight;
                        pq.Modify(temp);
                    }
                    q = q.Next;
                }

                num--;
            }

            // 输出vs中的顶点和到该顶点的最短路径长度
            Console.WriteLine("顶点{0}到其他各顶点的最短路径长度为：", i);
            for (int j = 0; j < num; j++)
            {
                Console.Write("{0}:{1}, ", j + 1, vs[j]);
            }
        }
    }

    class Client
    {
        public static void Main(string[] args)
        {
            Graph graph = new Graph(5);

            graph.AddEdge(1, 2, 10);
            graph.AddEdge(1, 5, 5);
            graph.AddEdge(2, 3, 1);
            graph.AddEdge(2, 5, 2);
            graph.AddEdge(3, 4, 4);
            graph.AddEdge(4, 1, 7);
            graph.AddEdge(4, 3, 6);
            graph.AddEdge(5, 2, 3);
            graph.AddEdge(5, 3, 9);
            graph.AddEdge(5, 4, 2);

            graph.Dijkstra(1);
        }
    }
}

// 顶点2到其他各顶点的最短路径长度为：
// 1:0, 2:8, 3:9, 4:7, 5:5,

Contents

简介

算法步骤

示例

堆优化