迪杰斯特拉(Dijkstra)算法
迪杰斯特拉(Dijkstra)算法
迪杰斯特拉算法( 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] 。比如图 1-77 ，从起始点到南京的时间是 3 小时，如果通过杭州中转，时间就会变成 2 小时。核心代码是下面这行。
dis[j] = Math.min(dis[j], dis[k] + g[k][j]);计算过程下图所示。
来看下代码：
public static void main(String[] args) {
int size = 6;// 顶点个数。
boolean visited[] = new boolean[size];// 标记顶点是否被访问过。
int max = 100;// 最大值默认给100。
int[][] g = {{max, 1, 3, max, max, max},// 图的邻接矩阵。
{max, max, 1, 4, 2, max},
{max, max, max, 5, 5, max},
{max, max, max, max, max, 3},
{max, max, max, 1, max, 6},
{max, max, max, max, max, max}};
int[] dis = new int[size];
Arrays.fill(dis, max);// 默认到起始点给个最大值。
dijkstra(g, visited, dis, 0);
}
/**
* @param g 图的邻接矩阵
* @param visited 哪些顶点被标记过
* @param dis 每个顶点到起始点的值
* @param start 起始点
*/
static void dijkstra(int[][] g, boolean visited[], int[] dis, int start) {
dis[start] = 0;// 起始点到自己的值是 0 。
int n = g.length;// 顶点的个数。
int k = -1;// 下一个没被更新且离起始点最近的顶点。
for (int i = 0; i < n; i++) {
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++) {// 核心代码。
if (!visited[j] && dis[k] + g[k][j] < dis[j])
dis[j] = dis[k] + g[k][j];
}
}
for (int i = 0; i < dis.length; i++)// 打印数组dis的值。
System.out.print(dis[i] + ",");
}
我们来看下打印结果：0,1,2,4,3,7, 也就是说从起始点到其他顶点的最短时间分别是 1,2,4,3,7 ，和我们图中分析的完全一样。时间复杂度：O(n^2) ，n 是顶点的个数。
堆优化
我们看到代码中外面的循环是遍历顶点，里面的循环主要是查找最近的顶点，然后更新和他邻接的顶点。如果这个图是个稀疏图，边特别少的话，在一个个查找很明显效率不高，所以在这种情况下可以使用最小堆来优化下，注意使用堆优化的时候图要使用邻接表的表示方式。每次与顶点 v 邻接的计算完之后直接把他加入到堆中，下次循环的时候直接弹出堆顶元素即可，他就是离起始点最近的，时间复杂度可以降为 O((n+e)logn) ，其中 n 是顶点的个数， e 是边的数量，因为出堆和入堆都会涉及到堆的调整，堆调整的时间复杂度都是 O(logn) ，代码大家可以尝试写下。
不能处理带有负权边的图
为什么通过上述的操作可以保证得到的 dis 值最小？因为这里的图是没有负权边的，值只能越加越大，所以这里的最小值不可能在被更新了。我们不断选择最小值进行标记然后更新和它邻接的点，即贪心的思路，最终保证起始点到每个顶点的值都是最小的。如果有负权边在使用 Dijkstra 算法就行不通了，如下图所示。
1，从顶点0开始，把顶点0标记，更新和它邻接的顶点1和2，即1->9，2->3。
2，选择未被标记且最近的顶点2，把顶点2标记，更新和它邻接的顶点3，即3->8。
3，选择未被标记且最近的顶点3，把顶点3标记，与顶点3相连的没有了。
4，选择未被标记且最近的顶点1，把顶点1标记，与顶点1相连的顶点2已经被标记了。最后的结果是起始点到顶点 3 的值是 8 ，但实际上如果选择 0->1->2>3 这条路径的值是 7 ，会更小，所以有负权边并不适合 Dijkstra 算法。如果图是有环的可不可以使用 Dijkstra 算法呢？实际上只要没有负权边无论有环无环都是可以使用 Dijkstra 算法的。
---------------end---------------
腾讯云开发者
