《经典图论算法》迪杰斯特拉算法(Dijkstra)
原创《经典图论算法》迪杰斯特拉算法(Dijkstra)
原创
摘要： 1，迪杰斯特拉算法介绍 2，迪杰斯特拉算法的代码实现 3，迪杰斯特拉算法的堆优化 4，为什么迪杰斯特拉算法不能处理带有负权边的图
1，迪杰斯特拉算法介绍 迪杰斯特拉算法(Dijkstra)也叫狄克斯特拉算法，它使用类似广度优先搜索的方法，解决从一个顶点到其他所有顶点的最短路径问题，它解决的是加权图(不能有负权)的最短路径问题。
从起始点开始，采用贪心算法的策略，每次选择一个没被标记且距离起始点最近的顶点，把它标记下，然后更新和它邻接的顶点 ……，直到所有顶点都计算完为止。
如上图所示，假如计算从上海到其他所有城市的最短时间，上面的时间有可能是开车，有可能是高铁也可能是坐飞机，和真实距离不成正比。
我们从起始点开始，使用一个数组 dis ，数组中 dis[j] 的值表示从起始点到顶点 j 的时间，刚开始的时候，起始点到他自己为 0 ，到其他顶点都为无穷大，如下图所示。
如果想要减少从起始点到 j 的时间，唯一的方式就是需要寻找一个中转站 k 。从起始点到 k 的时间为 dis[k] ，从 k 到 j 的时间为 g[k][j] ，然后判断中转的总时间 dis[k] + g[k][j] 是否小于 dis[j] ，如果中转时间小于 dis[j] ，就更新 dis[j] 。
比如最上面图中，从起始点到南京的时间是 3 小时，如果通过杭州中转，时间就会变成 2 小时。核心代码是下面这行。
dis[j] = min(dis[j], dis[k] + g[k][j]);迪杰斯特拉算法的解题思路如下：
1，从起始点开始计算所有和它相连的点(也就是起始点指向的点)，计算完之后把起始点标记下(表示已经计算过了)。 2，找出离起始点最近且没有被标记过的点 v ，计算所有和 v 相连且没有被标记过的点，计算完之后把 v 标记下。 3，重复上面的步骤 2 ，直到所有顶点都标记完为止。
2，迪杰斯特拉算法的代码实现
迪杰斯特拉算法使用的是贪心的策略，每次都是从未标记的顶点中找到一个离起始点最近的点，用它来更新所有和它连接且未被标记过的点，代码比较简单，我们来看下。
Java 代码：
private void test() {
int[][] g = {{0, 1, 3, 0, 0, 0},// 图的邻接矩阵。
{0, 0, 1, 4, 2, 0},
{0, 0, 0, 5, 5, 0},
{0, 0, 0, 0, 0, 3},
{0, 0, 0, 1, 0, 6},
{0, 0, 0, 0, 0, 0}};
dijkstra(g, 0);
}
/**
* @param g 图的邻接矩阵
* @param start 起始点
*/
public void dijkstra(int[][] g, int start) {
int n = g.length;// 顶点的个数。
int[] dis = new int[n];// 每个点到起始点的距离
// 起始点到其他所有顶点默认给一个非常大的值，
// 要注意下面加的时候防止出现溢出。
Arrays.fill(dis, Integer.MAX_VALUE >> 1);
dis[start] = 0;// 起始点到自己的值是 0 。
boolean visited[] = new boolean[n];// 标记哪些顶点被访问过
for (int i = 0; i < n; i++) {
int k = -1;// 下一个没被标记且离起始点最近的顶点。
int min = Integer.MAX_VALUE; // min 是 k 到起始点的值。
for (int j = 0; j < n; j++) {// 寻找 k。
if (!visited[j] && dis[j] < min) {
min = dis[j];
k = j;
}
}
visited[k] = true;// 标记
for (int j = 0; j < n; j++) {// 核心代码。
// 顶点 j 没有被标记，并且 k 有到 j 的路径，并且这个路径更近，就更新。
if (!visited[j] && g[k][j] != 0 && dis[k] + g[k][j] < dis[j])
dis[j] = dis[k] + g[k][j];
}
}
// 打印数组dis的值，测试使用。
for (int di : dis)
System.out.print(di + ",");
}C++ 代码：
/**
* @param g 图的邻接矩阵
* @param start 起始点
*/
void dijkstra(vector<vector<int>> &g, int start) {
const int n = g.size();// 顶点的个数。
vector<int> dis(n, INT_MAX/2);// 每个点到起始点的距离
dis[start] = 0;// 起始点到自己的值是 0 。
vector<bool> visited(n, false); // 标记哪些顶点被访问过
for (int i = 0; i < n; i++) {
int k = -1;// 下一个没被标记且离起始点最近的顶点。
int min = INT_MAX; // min 是 k 到起始点的值。
for (int j = 0; j < n; j++) {// 寻找 k。
if (!visited[j] && dis[j] < min) {
min = dis[j];
k = j;
}
}
visited[k] = true;// 标记
for (int j = 0; j < n; j++) {// 核心代码。
// 顶点 j 没有被标记，并且 k 有到 j 的路径，并且这个路径更近，就更新。
if (!visited[j] && g[k][j] != 0 && dis[k] + g[k][j] < dis[j])
dis[j] = dis[k] + g[k][j];
}
}
// 打印数组dis的值，测试使用。
for (int di: dis)
cout << di << ",";
}3，迪杰斯特拉算法的堆优化
我们看到上面代码中外面的循环是遍历顶点，里面的循环主要是查找离起始点最近的顶点 v ，然后更新和 v 邻接的顶点。
如果这个图是个稀疏图，边特别少的话，在一个个查找很明显效率不高，所以在这种情况下可以使用最小堆来优化下，每次与顶点 v 邻接的点计算完之后把它加入到堆中，下次循环的时候直接弹出堆顶元素即可，它就是离起始点最近的点。
Java 代码：
/**
* 使用堆优化的算法
*
* @param g 图的邻接矩阵
* @param start 起始点
*/
public void dijkstra(int[][] g, int start) {
int n = g.length;// 顶点的个数。
int[] dis = new int[n];// 每个点到起始点的距离
Arrays.fill(dis, Integer.MAX_VALUE >> 1);
dis[start] = 0;// 起始点到自己的值是 0 。
boolean visited[] = new boolean[n];// 标记哪些顶点被访问过
// 创建堆，根据到起始点的距离排序
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, start});// 起始点到它自己的距离是 0 。
for (int i = 0; i < n; i++) {
if (pq.isEmpty()) break; // 如果堆为空，退出循环
// 每次出队都是离起始点最近且没被标记过的顶点。
int k = pq.poll()[1];
visited[k] = true;// 标记
for (int j = 0; j < n; j++) {// 核心代码。
// 顶点 j 没有被标记，并且 k 有到 j 的路径，并且这个路径更近，就更新。
if (!visited[j] && g[k][j] != 0 && dis[k] + g[k][j] < dis[j]) {
// 如果顶点 j 经过 k 到起始点的距离更近，就更新顶点 j 到
// 起始点的距离，并把它添加到堆中。
dis[j] = dis[k] + g[k][j];
pq.offer(new int[]{dis[j], j});
}
}
}
// 打印数组dis的值，测试使用。
for (int di : dis)
System.out.print(di + ",");
}C++ 代码：
void dijkstra(vector<vector<int>> &g, int start) {
int n = g.size(); // 顶点的个数
vector<int> dis(n, INT_MAX / 2); // 每个点到起始点的距离
dis[start] = 0; // 起始点到自己的值是 0
vector<bool> visited(n, false); // 标记哪些顶点被访问过
// 创建堆，根据到起始点的距离排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, start); // 起始点到它自己的距离是 0
for (int i = 0; i < n; i++) {
// 每次出队都是离起始点最近且没被标记过的顶点
if (pq.empty()) break; // 如果堆为空，退出循环
int k = pq.top().second;
pq.pop();
visited[k] = true; // 标记
for (int j = 0; j < n; j++) { // 核心代码
// 顶点 j 没有被标记，并且 k 有到 j 的路径，并且这个路径更近，就更新
if (!visited[j] && g[k][j] != 0 && dis[k] + g[k][j] < dis[j]) {
// 如果顶点 j 经过 k 到起始点的距离更近，就更新顶点 j 到起始点的距离，并把它添加到堆中
dis[j] = dis[k] + g[k][j];
pq.emplace(dis[j], j);
}
}
}
// 打印数组dis的值，测试使用
for (int di: dis)
cout << di << ",";
cout << endl;
}4，为什么迪杰斯特拉算法不能处理带有负权边的图
为什么通过上述的操作可以保证得到的 dis 值最小？因为这里的图是没有负权边的，值只能越加越大，我们不断选择最小值进行标记然后更新和它邻接的点，即贪心的思路，最终保证起始点到每个顶点的值都是最小的。
如果有负权边在使用 Dijkstra 算法就行不通了，如下图所示，其中有负权边。
最后的结果是起始点到顶点 2 的值是 3 ，但实际上如果选择 0->1->2 这条路径的值是 2 ，会更小，所以有负权边并不适合 Dijkstra 算法。如果图是有环的可不可以使用 Dijkstra 算法呢？实际上只要没有负权边无论有环无环都是可以使用 Dijkstra 算法的。
如果有负权边该怎么解决呢？我们可以使用贝尔曼-福特算法(Bellman–Ford)和最短路径快速算法(Shortest Path Faster Algorithm：简称：SPFA)，这两种算法虽然可以解决带有负权边的图，但不能解决有负权回路的图，关于这两种算法，后面我们也都会介绍。
这个是求最短路径的迪杰斯特拉算法，另外我还写了50多种《经典图论算法》，每种都使用C++和Java两种语言实现，熟练掌握之后无论是参加蓝桥杯，信奥赛，还是其他比赛，或者是面试，都能轻松应对。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
